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.