Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #4760 > unrolled thread

implementation of unsigned addition on one's complement machines

Back to article view | Back to comp.arch

Contents

  implementation of unsigned addition on one's complement machines Luca Forlizzi <luca.forlizzi@gmail.com> - 2011-11-14 07:08 -0800
    Re: implementation of unsigned addition on one's complement machines torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-11-14 17:55 +0100
      Re: implementation of unsigned addition on one's complement machines torbenm@diku.dk (Torben Ægidius Mogensen) - 2011-11-15 10:29 +0100
        Re: implementation of unsigned addition on one's complement machines Luca Forlizzi <luca.forlizzi@gmail.com> - 2011-11-15 02:12 -0800
          Re: implementation of unsigned addition on one's complement machines nmm1@cam.ac.uk - 2011-11-15 10:28 +0000
            Re: implementation of unsigned addition on one's complement machines Luca Forlizzi <luca.forlizzi@gmail.com> - 2011-11-15 03:07 -0800
              Re: implementation of unsigned addition on one's complement machines nmm1@cam.ac.uk - 2011-11-15 11:13 +0000
                Re: implementation of unsigned addition on one's complement machines anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-11-15 17:33 +0000
                  Re: implementation of unsigned addition on one's complement machines nmm1@cam.ac.uk - 2011-11-15 18:14 +0000
                    Re: implementation of unsigned addition on one's complement machines anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-11-16 09:34 +0000
          Re: implementation of unsigned addition on one's complement machines Michael S <already5chosen@yahoo.com> - 2011-11-16 09:04 -0800
            Re: implementation of unsigned addition on one's complement machines nmm1@cam.ac.uk - 2011-11-16 17:31 +0000
            Re: implementation of unsigned addition on one's complement machines Robert Wessel <robertwessel2@yahoo.com> - 2011-11-16 11:54 -0600
      Re: implementation of unsigned addition on one's complement machines Luca Forlizzi <luca.forlizzi@gmail.com> - 2011-11-15 03:11 -0800
    Re: implementation of unsigned addition on one's complement machines anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-11-15 17:26 +0000
      Re: implementation of unsigned addition on one's complement machines Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-11-15 23:12 +0100
        Re: implementation of unsigned addition on one's complement machines Kai Harrekilde-Petersen <khp@harrekilde.dk> - 2011-11-15 23:25 +0100

#4760 — implementation of unsigned addition on one's complement machines

Hello,
 this is my first post in this group so I would like to greet
everyone.
I have a question about one's complement arithmetic, and it has been
suggested to me that since comp.arch.arithmetic is dead, this might be
the right place to ask.

In 2's complement, the same add/sub hardware instruction compute the
correct result for both signed and unsigned addition (although on
MIPS, for instance, there are separate instructions so that signed add
can generate overflow).
How unsigned addition is implemented in one's complement CPUs? the
instrucitons performing add in one's complement do not produce the
correct result for unsigned addition. Do such CPUs have distinct add
instructions for signed and unsigned operands?


Luca Forlizzi

[toc] | [next] | [standalone]

#4761

Luca Forlizzi <luca.forlizzi@gmail.com> writes:


> How unsigned addition is implemented in one's complement CPUs?

I can't find unsigned addition in the Univac 1100 instruction set (which
uses one's complement as default and supports sign+magnitude as well).

So I suspect the answer is "It isn't".

	Torben

[toc] | [prev] | [next] | [standalone]

#4764

torbenm@diku.dk (Torben Ægidius Mogensen) writes:

> Luca Forlizzi <luca.forlizzi@gmail.com> writes:
>
>> How unsigned addition is implemented in one's complement CPUs?
>
> I can't find unsigned addition in the Univac 1100 instruction set (which
> uses one's complement as default and supports sign+magnitude as well).
>
> So I suspect the answer is "It isn't".

However, if you don't overflow, ones-complement addition works fine for
unsigned addition.  The difference between ones-complement addition and
unsigned addition is that, if the addition has a carry out, this is
added back in to the lsb.  So if this never happens, you are O.K.

	Torben

[toc] | [prev] | [next] | [standalone]

#4765

On 15 Nov, 10:29, torb...@diku.dk (Torben Ægidius Mogensen) wrote:
> torb...@diku.dk (Torben Ægidius Mogensen) writes:
>
> > Luca Forlizzi <luca.forli...@gmail.com> writes:
>
> >> How unsigned addition is implemented in one's complement CPUs?
>
> > I can't find unsigned addition in the Univac 1100 instruction set (which
> > uses one's complement as default and supports sign+magnitude as well).
>
> > So I suspect the answer is "It isn't".
>
> However, if you don't overflow, ones-complement addition works fine for
> unsigned addition.  The difference between ones-complement addition and
> unsigned addition is that, if the addition has a carry out, this is
> added back in to the lsb.  So if this never happens, you are O.K.
>
>         Torben

you are right, thanks for pointing it out. This indeed solve the
problem in some cases. However not in the case I have in mind, i.e.,
how to implement C language unsigned arithmetic in one's complement
CPUs.
As you probably know, in C unsigned arithmetic is modular. This is
easily implemented in two's complement by ignoring the carry out of
addition.
So, either a one's complement CPU also has an add instruction that
does not add back the carry out, or the unsigned add operation has to
be implemented by a sequence of operation. In the latter case, I would
expect signed arithmetic in C to be faster than the unsigned one.

[toc] | [prev] | [next] | [standalone]

#4766

In article <49f2f40a-cf50-4f49-89ee-4d4e9ad56472@cc2g2000vbb.googlegroups.com>,
Luca Forlizzi  <luca.forlizzi@gmail.com> wrote:
>
>As you probably know, in C unsigned arithmetic is modular. This is
>easily implemented in two's complement by ignoring the carry out of
>addition.

Division and remainder aren't.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#4767

On 15 Nov, 11:28, n...@cam.ac.uk wrote:
> In article <49f2f40a-cf50-4f49-89ee-4d4e9ad56...@cc2g2000vbb.googlegroups.com>,
> Luca Forlizzi  <luca.forli...@gmail.com> wrote:
>
>
>
> >As you probably know, in C unsigned arithmetic is modular. This is
> >easily implemented in two's complement by ignoring the carry out of
> >addition.
>
> Division and remainder aren't.

excuse me, do you mean that they are not modular or that the can not
be
implemented by ignoring the carry out?

I would believe you in the latter case.
In the former, it seems to me that section 6.2.5 par.9 of the C
standard refers to all
operations. But since I know you as a regular on clc, it is well
possible that you know something more than me, in which case I ask you
to explain why 6.2.5 does not apply.

Luca

[toc] | [prev] | [next] | [standalone]

#4769

In article <8503c9bb-07c6-4bae-ad8c-64f52322006c@g21g2000yqc.googlegroups.com>,
Luca Forlizzi  <luca.forlizzi@gmail.com> wrote:
>>
>> >As you probably know, in C unsigned arithmetic is modular. This is
>> >easily implemented in two's complement by ignoring the carry out of
>> >addition.
>>
>> Division and remainder aren't.
>
>excuse me, do you mean that they are not modular or that the can not
>be implemented by ignoring the carry out?

There is no carry-out involved except, debatably, when dividing
-(1+maxint) by -1 on a two's complete system.  They aren't modular,
and that occasionally causes trouble.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#4776

nmm1@cam.ac.uk writes:
>In article <8503c9bb-07c6-4bae-ad8c-64f52322006c@g21g2000yqc.googlegroups.com>,
>Luca Forlizzi  <luca.forlizzi@gmail.com> wrote:
>>>
>>> >As you probably know, in C unsigned arithmetic is modular. This is
>>> >easily implemented in two's complement by ignoring the carry out of
>>> >addition.
>>>
>>> Division and remainder aren't.
>>
>>excuse me, do you mean that they are not modular or that the can not
>>be implemented by ignoring the carry out?
>
>There is no carry-out involved except, debatably, when dividing
>-(1+maxint) by -1 on a two's complete system.

That's not a division of unsigned numbers.  I don't think you can
produce an overflow with division (or remainder) of unsigned numbers
in C, so your mentioning of division does not contribute anything but
noise to the discussion.  Btw, wouldn't a C standards bigot write
(-maxint)-1 instead of -(1+maxint)?

- anton
-- 
M. Anton Ertl                    Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html

[toc] | [prev] | [next] | [standalone]

#4777

In article <2011Nov15.183339@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>>>
>>>> >As you probably know, in C unsigned arithmetic is modular. This is
>>>> >easily implemented in two's complement by ignoring the carry out of
>>>> >addition.
>>>>
>>>> Division and remainder aren't.
>>>
>>>excuse me, do you mean that they are not modular or that the can not
>>>be implemented by ignoring the carry out?
>>
>>There is no carry-out involved except, debatably, when dividing
>>-(1+maxint) by -1 on a two's complete system.
>
>That's not a division of unsigned numbers.  I don't think you can
>produce an overflow with division (or remainder) of unsigned numbers
>in C, so your mentioning of division does not contribute anything but
>noise to the discussion.  Btw, wouldn't a C standards bigot write
>(-maxint)-1 instead of -(1+maxint)?

Curious.  You are usually both reasonably polite and reasonably
clueful but, in that post, you are neither.

Consider 3-bit unsigned integers, for simplicity.  7/5 = 3 in
true modular arithmetic.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#4786

nmm1@cam.ac.uk writes:
>In article <2011Nov15.183339@mips.complang.tuwien.ac.at>,
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>>>>
>>>>> >As you probably know, in C unsigned arithmetic is modular. This is
>>>>> >easily implemented in two's complement by ignoring the carry out of
>>>>> >addition.
>>>>>
>>>>> Division and remainder aren't.
...
>Consider 3-bit unsigned integers, for simplicity.  7/5 = 3 in
>true modular arithmetic.

Ok, 3*5=7 (mod 8)

However, with this concept of division, the concept of remainder is
meaningless.

- anton
-- 
M. Anton Ertl                    Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html

[toc] | [prev] | [next] | [standalone]

#4790

On Nov 15, 12:12 pm, Luca Forlizzi <luca.forli...@gmail.com> wrote:
> On 15 Nov, 10:29, torb...@diku.dk (Torben Ægidius Mogensen) wrote:
>
> As you probably know, in C unsigned arithmetic is modular. This is
> easily implemented in two's complement by ignoring the carry out of
> addition.

One's complement addition is also modular, with modulo=2**wordsize-1.
Does C standard specify that modulo of unsigned addition/subtraction
has to be power of 2?

[toc] | [prev] | [next] | [standalone]

#4791

In article <fc4566bd-ea00-4112-b5de-5bdf998d857b@g7g2000vbd.googlegroups.com>,
Michael S  <already5chosen@yahoo.com> wrote:
>On Nov 15, 12:12 pm, Luca Forlizzi <luca.forli...@gmail.com> wrote:
>>
>> As you probably know, in C unsigned arithmetic is modular. This is
>> easily implemented in two's complement by ignoring the carry out of
>> addition.
>
>One's complement addition is also modular, with modulo=2**wordsize-1.
>Does C standard specify that modulo of unsigned addition/subtraction
>has to be power of 2?

Yes.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#4792

On Wed, 16 Nov 2011 09:04:26 -0800 (PST), Michael S
<already5chosen@yahoo.com> wrote:

>On Nov 15, 12:12 pm, Luca Forlizzi <luca.forli...@gmail.com> wrote:
>> On 15 Nov, 10:29, torb...@diku.dk (Torben Ægidius Mogensen) wrote:
>>
>> As you probably know, in C unsigned arithmetic is modular. This is
>> easily implemented in two's complement by ignoring the carry out of
>> addition.
>
>One's complement addition is also modular, with modulo=2**wordsize-1.
>Does C standard specify that modulo of unsigned addition/subtraction
>has to be power of 2?



From C99:

"6.2.6.2 Integer types

For unsigned integer types other than unsigned char, the bits of the
object representation shall be divided into two groups: value bits and
padding bits (there need not be any of the latter). If there are N
value bits, each bit shall represent a different power of 2 between 1
and 2N-1, so that objects of that type shall be capable of
representing values from 0 to 2N - 1 using a pure binary
representation; this shall be known as the value representation. The
values of any padding bits are unspecified."

C89 did not specify this quite as explicitly, although it hints at it.

[toc] | [prev] | [next] | [standalone]

#4768

On 14 Nov, 17:55, torb...@diku.dk (Torben  gidius Mogensen) wrote:
> Luca Forlizzi <luca.forli...@gmail.com> writes:
> > How unsigned addition is implemented in one's complement CPUs?
>
> I can't find unsigned addition in the Univac 1100 instruction set (which
> uses one's complement as default and supports sign+magnitude as well).
>
> So I suspect the answer is "It isn't".
>
>         Torben

I have done a quick research using wikipaedia, also the PDP1, CDC6600
and CDC 160 are one's complement machines and seem not to have add
instructions for unsigned numbers.
This confirms your suspect. Thanks a lot

[toc] | [prev] | [next] | [standalone]

#4775

Luca Forlizzi <luca.forlizzi@gmail.com> writes:
>How unsigned addition is implemented in one's complement CPUs? the
>instrucitons performing add in one's complement do not produce the
>correct result for unsigned addition. Do such CPUs have distinct add
>instructions for signed and unsigned operands?

If they want to use all the bits for unsigned numbers, then a separate
unsigned addition (and subtraction) is needed.  However, you can
define the positive subset of the signed integers supported by the
machine to be the unsigned numbers; then you can use the ordinary
(signed) addition for these "unsigned" numbers; but you don't get
wrap-around on overflows then.

I wonder how C's guaranteed wraparound on unsigned overflow is
implemented on such machines.

- anton
-- 
M. Anton Ertl                    Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html

[toc] | [prev] | [next] | [standalone]

#4778

Anton Ertl wrote:
> If they want to use all the bits for unsigned numbers, then a separate
> unsigned addition (and subtraction) is needed.  However, you can
> define the positive subset of the signed integers supported by the
> machine to be the unsigned numbers; then you can use the ordinary
> (signed) addition for these "unsigned" numbers; but you don't get
> wrap-around on overflows then.
>
> I wonder how C's guaranteed wraparound on unsigned overflow is
> implemented on such machines.

The easiest might be to reduce the size of unsigned values by an 
additional bit, then follow each add with a mask?

Terje
-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#4780

Terje Mathisen <"terje.mathisen at tmsw.no"> writes:

> Anton Ertl wrote:
>> If they want to use all the bits for unsigned numbers, then a separate
>> unsigned addition (and subtraction) is needed.  However, you can
>> define the positive subset of the signed integers supported by the
>> machine to be the unsigned numbers; then you can use the ordinary
>> (signed) addition for these "unsigned" numbers; but you don't get
>> wrap-around on overflows then.
>>
>> I wonder how C's guaranteed wraparound on unsigned overflow is
>> implemented on such machines.
>
> The easiest might be to reduce the size of unsigned values by an
> additional bit, then follow each add with a mask?

I would be surprised if they do - I guess there must be a simple way of
doing this, since the VHDL standard has been designed so it could be run
on both 1-complement and 2-complement hardware: integer range is limited
to +/-(2**31-1) for this particular reason (at least this is the reason
that is written in textbooks about VHDL).


Kai
-- 
Kai Harrekilde-Petersen <khp(at)harrekilde(dot)dk>

[toc] | [prev] | [standalone]

Back to top | Article view | comp.arch

csiph-web