Wed, 22 Sep 1993 20:21:34 GMT

Related articles |
---|

Multiprecision Integer Math Package bert@netcom.com (1993-09-22) |

Re: Multiprecision Integer Math Package daveg@thymus.synaptics.com (Dave Gillespie) (1993-09-22) |

Re: Multiprecision Integer Math Package bothner@cygnus.com (1993-09-26) |

Newsgroups: | comp.compilers |

From: | Dave Gillespie <daveg@thymus.synaptics.com> |

Keywords: | C, arithmetic |

Organization: | Compilers Central |

References: | 93-09-090 |

Date: | Wed, 22 Sep 1993 20:21:34 GMT |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.