Re: Multiprecision Integer Math Package

The concept of implementing big integers in C++ is not new. The GNU C++
library, for example, includes arbitrary-precision Integer and Rational
classes. (Note that this is a true C++ implementation, distinct from the
GNU "gmp" package written in C.)


> There are some specific nitty-gritty issues currently being raised
> about how to evaulate a/b or a%b when a and/or b are negative integers.
> ANSI C does not define a standard behavior, and most compilers seem
> to evaluate floor(a/b), for example, since this is what most CPUs
> return. From a mathematical point of view, this is not necessarily
> the most sensible behavior -- you would usually want to round a/b
> towards zero.


I think you may have this backwards: Most CPU's I've seen round toward
zero, which produces an irregularity at zero. The "floor(a/b)"
implementation is more consistent and useful. For example, you can use
"theta % 360" to convert an angle "theta" to its equivalent in the range
0..359 degrees, but only if "%" is based on flooring division. Otherwise
negative angles will produce "-1 % 360 = -1" instead of "-1 % 360 = 359".
As another example, if you want to round "x" to the nearest multiple of
10, you can use "10 * ((x+5)/10)" only if "/" is based on floor; otherwise
this formula will return 0 when "x" is -9.


The main relevance of this issue to compilers is that "x / 16" can be
optimized to "x >> 4" only if "/" uses flooring division. Since most
CPUs' divide instructions use truncation, C compilers are left with a
quandary when it comes time to optimize divisions by powers of two. Even
though the C standard says the direction of rounding is undefined for
negative "x", C users still expect the compiler to get the same answer for
"x / 16" as for "x / y" when "y" happens to be 16.


Another related issue is what to do about bitwise operations on negative
integers. The GNU library defines "x & y" as the bitwise AND of the
absolute values, with the sign of "x". This is similar to the truncating
divide, where you divide the magnitudes and then attach a sign based on
the signs of the inputs. Common Lisp instead defines that a negative
integer acts like a two's complement integer with infinitely many leading
ones. This is arguably more mathematically clean, since it doesn't
involve an arbitrary choice of sign.


Common Lisp compilers often choose to store integer variables as machine
"int"s if they can prove the variables will always be small enough to fit;
Lisp's definition of bitwise AND means that the machine's AND instruction
will work correctly for such variables. The GNU definition of bitwise AND
does not have this property, and also is not commutative, thus seriously
restricting the ability of the compiler to optimize it.


-- Dave
--

Return to the comp.compilers page.
Search the comp.compilers archives again.