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.