wulf@uvacs.CS.VIRGINIA.EDU (Bill Wulf) (05/30/88)
I must admit to being a bit overwhelmed by the number and diversity of articles that have appeared in response to my querry about machines with negative addresses. First, thanks to all. Second, apologies for not responding to them; I just started a new job at NSF and have been pretty busy -- just reading them on weekends has been the best I could do. Third, I want to correct one rampent mis-impression. Unsigned is NOT required for multi-precision arithmetic. This is hardly the forum for a lecture on arithmetic, but, just to set the framework -- as we all know, our familiar positional notation is simply a shorthand for a polynomial. Eg, 123 == 1*10**2 + 2*10**1 + 3+10**0 the numeral in "123" are simply the coefficients of the polynomial, and their position is used as an abbreviation for the "10**n". Now, a multi-precision number can be thought of in the same way. That is, each word can be viewed as a coefficient in a polynomial of the form w2 w1 w0 == w2*(2**32)**2 + w1*(2**32)**1 + w0*(2**32)**0 NOW -- no one ever said that these coefficients must be positive!!! Perfectly reasonable, consistent number systems can be defined where some of the numerals denote negative values. Consider a ternary number system where the numerals are 1 == 1 0 == 0 M == -1 SO, for example, 1M0 == 1*9 + (-1)*3 + 0*1 == 6, and decimal is strange ------- ------- 0 0 1 1 2 1M 3 10 4 11 5 1MM 6 1M0 7 1M1 8 10M 9 100 etc. So, you see, while it may seem a bit strange, unsigned arithmetic is not necessary for multi-precision arithmetic. Bill
brooks@lll-crg.llnl.gov (Eugene D. Brooks III) (06/01/88)
In article <2433@uvacs.CS.VIRGINIA.EDU> wulf@uvacs.CS.VIRGINIA.EDU (Bill Wulf) writes: >This is hardly the forum for a lecture on arithmetic, but, >just to set the framework -- as we all know, our familiar >positional notation is simply a shorthand for a polynomial. Bill, I am sure that you might eventually convince the computer industry to drop unsigned integer arithmetic, and even cause the insertion of the "strange" data type in C, but it will probably be long after you are dead and buried. Is it really worth it?
cik@l.cc.purdue.edu (Herman Rubin) (06/06/88)
In article <2433@uvacs.CS.VIRGINIA.EDU>, wulf@uvacs.CS.VIRGINIA.EDU (Bill Wulf) writes: > Now, a multi-precision number can be thought of in the same way. > That is, each word can be viewed as a coefficient in a polynomial > of the form > > w2 w1 w0 == w2*(2**32)**2 + w1*(2**32)**1 + w0*(2**32)**0 > > NOW -- no one ever said that these coefficients must be positive!!! (much deleted) What Bill says is correct; one can do multiple precision arithmetic without unsigned arithmetic. It is not too difficult to do it in sign-magnitude arithmetic, and a method has been proposed many years ago to use both signs and allow a little stretch to avoid carry propagation. Since not everyone is familiar with this, in base 10 the digits would go from -5 to 4, but carry would extend the range to -6 to 5. Note that this loses a bit due to ambiguities. However, every computer I have seen since the IBM 70x(x) series does not compute double products of signed numbers in such a useful manner! They all produce the product as a signed number followed by an unsigned number. Now if the unsigned number has its leading bit a forced 0, one can do as Bill suggests for multiple precision. The great majority of computers do not have this feature. In that case, one must resort to slightly less than half word arithmetic or other kludges. product with the least significant part unsigned. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907 Phone: (317)494-6054 hrubin@l.cc.purdue.edu (ARPA or UUCP) or hrubin@purccvm.bitnet
dgc@sonia.math.ucla.edu (David G. Cantor) (06/07/88)
In article <792@l.cc.purdue.edu> cik@l.cc.purdue.edu (Herman Rubin) writes:
. . . one can do multiple precision arithmetic without unsigned
arithmetic. It is not too difficult to do it in sign-magnitude
arithmetic, and a method has been proposed many years ago
to use both signs and allow a little stretch to avoid carry
propagation. Since not everyone is familiar with this, in base
10 the digits would go from -5 to 4, but carry would extend the
range to -6 to 5. Note that this loses a bit due to ambiguities.
However, every computer I have seen since the IBM 70x(x) series
does not compute double products of signed numbers in such a
useful manner! They all produce the product as a signed number
followed by an unsigned number. Now if the unsigned number has
its leading bit a forced 0, one can do as Bill suggests for
multiple precision. The great majority of computers do not have
this feature. In that case, one must resort to slightly less
than half word arithmetic or other kludges. product with the
least significant part unsigned.
------------------------------------------------------------------------
It is very easy to correrct for this:
What most computers do is take two n-bit two's-complement numbers and
form a 2n-bit two's-complement number. What you want to do is to
take the the latter number and rewrite is as 2 n-bit two's-complement
numbers, say a and b, so that it equals a*2^n + b. This is
easily done:
Split the 2n-bit number into the two n-bit numbers a and b by taking
the left and right halves, respectively. Then if the right half b is
negative (has a leading 1) subtract 1 from the left half a.
dgc
David G. Cantor
Internet: dgc@math.ucla.edu
UUCP: ...!{ihnp4, randvax, sdcrdcf, ucbvax}!ucla-cs!dgc