Whence 2s-complement
Author Message
Whence 2s-complement

Can anybody present illuminate for me the mystery-shrouded etymolgoy of the
term twos-complement, referring to the most widespread computer method of
storing negative vs. positive binary numbers in memory?  Please?  As well as
satisfying my curiosity, the answer will probably reveal an important part
of the history of computer evolution (or not).

Wed, 23 Aug 2000 03:00:00 GMT
Whence 2s-complement

Quote:
>Can anybody present illuminate for me the mystery-shrouded etymolgoy of the
>term twos-complement, ...

textbook on computer arithmetic than to flood the Internet at great expense.

Quote:
>comp newsgroups.  ...

Well, then, you shouldn't be posting to all the comp newsgroups, should you?

Sun, 27 Aug 2000 03:00:00 GMT
Whence 2s-complement

Note I trimmed the followups to what appeared to be a more
relevant subset.

: Can anybody present illuminate for me the mystery-shrouded etymolgoy of the
: term twos-complement, referring to the most widespread computer method of
: storing negative vs. positive binary numbers in memory?

Not so "mystery shrouded", if you were a "New Math Victim",
_or_ stayed awake during a college-level "Foundations of Arithmetic"
course. First you need to understand "complement arithmetic". The usual
analogy is to the odometer on a car. If you have a five-digit odometer,
then adding "99999" is equivalent to subtracting "1". That's because
"99999" is the "complement" of "1" for this system. Going back to
your Latin class, you see that "complement" refers to "filling up" and
is related to "completion". 99999+1 "completes" one trip around the
entire set of numbers that the five-digit odometer can represent.
This sort of thing is well-known to used-car dealers like Mathilda's
father (Roald Dahl, never mind) who know they can set _back_ the
mileage on a car by using an electric drill to the run the odometer
forward.

You can easily get this sort of complement by subtracting
'1' from 100000, but that rather begs the question, since we got
here while trying to subtract. You can _also_ get it by taking
the complement of each _digit_ ('00001' -> '99998') and adding
'1'. This is known in many math texts as "ten's complement", because
the scheme works on radix (base) ten numbers, regardless of the
number of digits so "one-hundred-thousands complement", while arguably
more accurate in this particular case, is not helpful.

Some folks are bothered by the "magic" implied by step:
"and then add one". They like to treat each digit exactly the same.
Unfortunately, this means they don't get the answers they expect.
"Ah, but we can fix it". What we can do is take the "nines complement"
("00001" -> "99998", I bet you can guess where the name comes from),
do the addition and then, _if_ a "carry" falls off the end, feed it back
into the least-significant digit. Example: "43-1" becomes "00043"+"99998"
which is 00041 plus a carry out of the top. Add that carry in and
it becomes 42, which is of course, the answer.

Most computers today use binary, rather than decimal, arithmetic,
translate pretty naturally. "9's complement" becomes "one's complement"
while "10's complement" becomes "two's complement". Each has its
benefits and problems.

Two's complement has the odd property that a given size of
number can hold one more negative number than positive. For example,
a 16-bit number can hold any integer from -32768 to +32767. If you try
to take the negative of -32768, you end up back at -32768. This mightily
disturbs some folks.

One's complement has the odd property that there are _two_
zeroes, "000...000" and "111...111". Not only that, but one of them is
negative, which some _other_ people find even more disturbing than
having an extra non-zero negative number. It gets even more annoying
when you find that the usual "first cut" at building a one's-complement
adder is _far_ more likely to yield the negative-zero than the positive
one, and some one's complement machines don't count their own "-0" as
"zero" for purposes of some tests.

The benefits of the two systems mainly lie in the lack of
the problems of the other system. The one "killer" benefit of two's
complement is that it is just slightly easier to do "multi-precision"
arithmetic in. That term refers to the use of "small" arithmetic
circuitry to do larger problems (such as when we add numbers a digit
at a time for as many digits as we need). On the original computers
with rather large words, this was no big deal, but as mini-computers
and then microprocessors came out, pretty much _any_ reasonable-sized
numbers (over 2 digits) required multiple-precision arithmetic
(e.g. using an 8-bit adder twice to generate a 16-bit result). Of
course, rare is the programmer under 40 who even remembers the
days when not all computers were binary, two's-complement machines
with word-size an even power of two (4,8,16,32...)

One place where one's complemnt turns up, to the bafflement
of younger programmers, is in the checksums used in TCP/IP. There
are some advantages in having a method which "dosn't care" whether
the least significant byte of a 16-bit number is stored before
or after the most significant byte, but I suspect the fact that
it is easier to "fake" one's-complement on a two's-complement machine
than vice-versa had something to do with it too. Even machines whose
"native tongue" was "sign-magnitude" (as we use on paper) tended
to support some form of complemnet arithmetic too.

: satisfying my curiosity, the answer will probably reveal an important part
: of the history of computer evolution (or not).

There is not much truly useless knowledge, at least at
this basic level. I'd claim that knowing this sort of thing will
still be slightly useful long after the ability to debug a
CONFIG.SYS has gone the way of knowing the names of the Lares and
Penates or the exchange rate for Green Stamps.

Mike

Sun, 27 Aug 2000 03:00:00 GMT
Whence 2s-complement

Quote:

> Can anybody present illuminate for me the mystery-shrouded etymolgoy of the
> term twos-complement, referring to the most widespread computer method of
> storing negative vs. positive binary numbers in memory?  Please?  As well as
> satisfying my curiosity, the answer will probably reveal an important part
> of the history of computer evolution (or not).

The 2's Complement is formed by taking the Boolean Complement, or 1's

The 3's Complement is the 2's Complement + 1, etc.

The 9's Complement, used to do subtraction in BCD, is the 1's Complement + 8.

*****

1's complement was used in some machines (e.g. CDC) because it is (was)
faster to compute.  You don't have to propagate the carries.

*****

2's complement is much more elegant.  There is really no such thing as a
"sign bit" in 2's Complement.  The high order bit simply has a negative
"place value".

I.e. In 16 bit 2's Complement the place values are from lowest to highest:

2**0 (1)
2**1 (2)
2**2 (4)
...
2**14 (16384)
-(2**15) (-32768)

This makes addition "insensitive" (there is a mathematical term for this)
to the sign of the arguments.

Arithemetic overflow occurs when the Carry into the high order bit is not
equivalent to the Carry out of the high order bit.

*****

In the language Common LISP, integers have arbitrary precision (the may be
huge in magnitude).  There are also a number of functions for bit
manipulation, such as testing the value of a bit, or extracting bits;
while the language doesn't specify what REAL arithemetic is used for the
implementation, it does require that the implementation return results
from these bit accessing instructions AS IF the implementation were 2's
complement.

d

Fri, 15 Sep 2000 03:00:00 GMT
Whence 2s-complement

Quote:

>> Can anybody present illuminate for me the mystery-shrouded etymolgoy of the
>> term twos-complement, referring to the most widespread computer method of
>> storing negative vs. positive binary numbers in memory?  Please?  As well as
>> satisfying my curiosity, the answer will probably reveal an important part
>> of the history of computer evolution (or not).
>The 2's Complement is formed by taking the Boolean Complement, or 1's
>The 3's Complement is the 2's Complement + 1, etc.
>The 9's Complement, used to do subtraction in BCD, is the 1's Complement + 8.

That is a little confused.  The nines complement of a decimal number
is formed by subtracting each digit from 9.  The tens-complement is
formed by adding 1 to the nines complement.  In general for a base N
number representation, we can talk of the (N-1)s complement, formed
by subtracting each digit from N-1, and the Ns complement formed by
adding 1 to the (N-1)s complement.

Back in prehistoric times (or precomputer times), some mechanical
calculators represented negative numbers as nines complement, some as
tens complements, and some as sign magnitude.

If you take the odometer on your car, and say it is set to 0.  Then
if you wind it backwards by 1 count, that would result in 999999,
which is the nines complement way of representing -1.  So nines
complement is relatively natural way of representing negative decimal
numbers, by analogy with winding a counter backwards.  Similarly,
twos complement is a relatively natural way of representing negative
binary numbers.  [Please don't actually wind the odometer backwards -
it might be against the law.]

Fri, 15 Sep 2000 03:00:00 GMT
Whence 2s-complement

<<<deletia regareding 8's complement... among other things>>>

Quote:
> That is a little confused.  The nines complement of a decimal number
> is formed by subtracting each digit from 9.  The tens-complement is
> formed by adding 1 to the nines complement.  In general for a base N
> number representation, we can talk of the (N-1)s complement, formed
> by subtracting each digit from N-1, and the Ns complement formed by
> adding 1 to the (N-1)s complement.

> Back in prehistoric times (or precomputer times), some mechanical
> calculators represented negative numbers as nines complement, some as
> tens complements, and some as sign magnitude.

> If you take the odometer on your car, and say it is set to 0.  Then
> if you wind it backwards by 1 count, that would result in 999999,
> which is the nines complement way of representing -1.  So nines
> complement is relatively natural way of representing negative decimal
> numbers, by analogy with winding a counter backwards.  Similarly,
> twos complement is a relatively natural way of representing negative
> binary numbers.  [Please don't actually wind the odometer backwards -
> it might be against the law.]

Actually the odometer uses 10's complement, not 9's complement.  In a base
10 system, one gets 9's complement by subtracting the original number from
an all 9's number of equal number of digits.  This can be done on a digit
by digit basis, as NO carry is involved.  Thus 9's complement of '31' is
'99' - '31', or '68'.  This system leads to a numbering system that has
two zeros ('00' and '99').  To get 10's complement, which has a continuous
range, one needs to add back in the 1.  Then the 10's complement to '31'
is '69', and their sum is '100' (zeros in the digits, with a single carry
out).  This is similar to 1's and 2's complement for binary numbers.  It
has many of the same properties, like more negative numbers than positive
(non-zero) numbers.  In the two digit system, '50' is a full scale
negative number (value of -50), and has no positive partner.

Commonly BCD machines (like the IBM 1620) used sign-magnitude arithmetic
with a seperate sign "flag".  While this was pleasing to the eye,
arithmetic has strange consequences.  With differing signs, it was
possible to effect a 'recomplement' sequence that changed the
(preliminary) result with the wrong sign from 10's complement back to the
proper sign-magnitude form.  This made the operation last longer, and
wasn't always welcome.  Adding a negative number could take longer than
subtracting a positive number (basically equivalent operations) if one
needed the 'recomplement' operation.

In some software floating point operations, the exponent was expressed as
'excess 50' notation, which is basically 10's complement with the sign
reversed.  This allowed a range of exponents (-50 to +49) to be expressed
without the use of a 'flag' bit and allowed the sign of the number number
to use the flag.  Today, IBM floating point numbers do a similar goodie in
their excess 64 exponents (but in binary).

Some of this belongs in folklore groups, given the historical reference.

--

Fri, 15 Sep 2000 03:00:00 GMT
Whence 2s-complement

Quote:

> >> Can anybody present illuminate for me the mystery-shrouded etymolgoy of the
> >> term twos-complement, referring to the most widespread computer method of
> >> storing negative vs. positive binary numbers in memory?  Please?  As
well as
> >> satisfying my curiosity, the answer will probably reveal an important part
> >> of the history of computer evolution (or not).

> >The 2's Complement is formed by taking the Boolean Complement, or 1's

> >The 3's Complement is the 2's Complement + 1, etc.

> >The 9's Complement, used to do subtraction in BCD, is the 1's Complement + 8.

> That is a little confused.  The nines complement of a decimal number

Actually I said Binary Coded Decimal number, but it is confused, since I
can't remember how to do it.

Quote:
> ... and the Ns complement formed by
> adding 1 to the (N-1)s complement.

... or 2 to the (N-2)s complement, etc. I think this is what I said.

i.e. adding 8 to the (9-8)s complement.

d

Fri, 15 Sep 2000 03:00:00 GMT
Whence 2s-complement

Quote:

>> >> Can anybody present illuminate for me the mystery-shrouded etymolgoy of the>> >> term twos-complement, referring to the most widespread computer method of
>> >> storing negative vs. positive binary numbers in memory?  Please?  As
>well as
>> >> satisfying my curiosity, the answer will probably reveal an important part
>> >> of the history of computer evolution (or not).

>> >The 2's Complement is formed by taking the Boolean Complement, or 1's

>> >The 3's Complement is the 2's Complement + 1, etc.

>> >The 9's Complement, used to do subtraction in BCD, is the 1's Complement + 8.>>
>> That is a little confused.  The nines complement of a decimal number

>Actually I said Binary Coded Decimal number, but it is confused, since I
>can't remember how to do it.

As far as complements are concerned you should consider it as a decimal
system.

Quote:
>> ... and the Ns complement formed by
>> adding 1 to the (N-1)s complement.

That's only valid for base N numbers.

Quote:
>... or 2 to the (N-2)s complement, etc. I think this is what I said.

No, that is incorrect. For base N it is only meaningful to talk about
N-1's complement and N's complement. N-2's complement is meaningless.
In binary you can talk about 1's complement and 2's complement. In base 10
2's complement in base 10 is meaningless nonsense.

Quote:
>i.e. adding 8 to the (9-8)s complement.

Except that this doesn't work.

--
-----------------------------------------

-----------------------------------------

Sun, 17 Sep 2000 03:00:00 GMT

 Page 1 of 1 [ 8 post ]

Relevant Pages