[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Arithmetic issues



Thanks very much for the reference! It looks very useful.

In an implementation written in C (i.e., without access to the carry flag) running on a 32-bit processor, it might make sense to use 16-bit fixnums to make it easy to check for overflow and the need for bignums.

This is not really necessary. See "Hacker's Delight" by Henry S. Warren, who gives algorithms for checking for overflow in the basic arithmetic operations for signed and unsigned arithmetic.

I didn't say it was necessary, I said it made it easy. In this case, easy means quick.

Let's consider the case of multiplication. If a double-width result is available, Warren suggests a check for overflow using only shifts and a single compare (which can well predicted). If it is not, he suggests a check using integer division (which may be slow) and more comparisons (which are more difficult to predict).

Of course, in a sense, you have access to the carry flag because "long long" is at least 64-bits.


I'm no C expert, but somehow I doubt that this is true. (I first wrote "strictly true", but I guess it's either true or false.)

What I meant was that if you put two unsigned 32-bit longs in unsigned 64-bit long longs and add them, the 33rd bit of the result will be equal to the carry flag.

Regards,

Alan
--
Dr Alan Watson
Centro de Radioastronomía y Astrofísica
Universidad Astronómico Nacional de México