From: John Maddock (john_at_[hidden])
Date: 2006-11-27 06:29:09
> 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)
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk