[Haskell] for large x, log (x::Integer) :: Double

[Steve Schafer]

On Wed, 30 Jun 2004 06:47:49 -0700 (PDT), Hal Daume III <hdaume at ISI.EDU>
wrote:

>i'm looking for an accurate way to take the log of a very large integer, 
>for example:

The standard algorithm works along these lines:

(Assume for the purposes of discussion that your numbers are represented
in some kind of binary notation.)

0) Call your integer i.

1) Compute d, the smallest power of 2 that is greater than i.

2) Compute the floating-point quotient q = i / d. This will be a value
between 0.5 and 1.0. 

3) Compute n, the base-2 log of d. (This is trivial, since d is a power
of 2.)

4) Use your CPU's built-in floating-point unit to compute g, the base-2
log of q. (For an Intel CPU, see the FYL2X instruction. If q is very
close to 1, you may want to use the FYL2XP1 instruction instead to
preserve more significant bits; in that case, pass it q - 1 rather than
q.) 

5) The base-2 log of i then simply n + g, and you can convert that to
another base b by multiplying it by the base-2 log of b (or,
equivalently, by dividing it by the base-b log of 2).

If your integer is stored in some other fashion (i.e., not binary), then
you'll want to adjust the divisor and the logarithm base appropriately.
The idea is that you want to choose your initial divisor so that it is a
power of the base, where the value of that base is chosen to make the
process of computing the quotient q efficent and accurate.

Steve Schafer
Fenestra Technologies Corp
http://www.fenestra.com/