Re: [boost] Yet another bignum type

From: John Maddock (john_at_[hidden])
Date: 2006-11-27 06:29:09

>> Logarithm
>
> Natural logarithm and/or any base?  How can it be done, especially
> since I would be limited to integer arithmetic and results?  I only
> have access to Knuth's _The Art of Computer Programming_ books,
> Wikipeida, plus occasional bignum pages I see on the web.  I don't
> have access to the ACM/IEEE stuff, where I suspect a lot of "kewl"
> algorithms live.

This is somewhat offtopic since log/pow/exp are only really relevant for 
floating-point types, but basically:

If x is a base 2 number in normalised form then split it into significand s 
in range [1,2) and integer exponent n, then:

If s > 1.5, divide s by two and add one to n.

Then we have s in [0.75,1.5)
and:

ln(x) = ln(s) + n*ln(2)

ln(s) can be calculated from it's taylor series for small x < 1 (hence the 
split above), ln(2) you could either just store lots of digits, or calculate 
that specific value by some other method.

Note that this only really works for base 2 numbers, since if we have base 
N, then the significand is in [1,N) and it's harder (though not impossible) 
to reduce that so that we can use the taylor expansion.

HTH, John.