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

Late request for additional functions



Olin (and others):

I was looking at iterative bignum algorithms for calculating pi and other
things last week.  In such algorithms, one would like to say: stop the
general iteration if two approximations a and b, each of length n bits,
agree to at least their most significant n/2 bits (then you execute a
cleanup operation).  One would like to do this without actually subtracting
the two numbers, which generally leads to n bits of garbage.  This is a fairly
common operation in iterative algorithms for integer division, square root, 
etc., and algebraic-geometric mean (AGM) algorithms.

So I propose two new functions (modulo naming)

(least-significant-bit-difference a b) => a number or #f
(most-significant-bit-difference a b)  => a number or #f

The first function would return the location (index) of the least
significant bit that was different between the two integers, or #f
if a and b are equal.

The second function would return the location (index) of the most
significant bit that was different between the two integers, or #f
if one of a and b is nonnegative and the other is negative.

Brad