0

I'm programming a library for arbitrary precision arithmetic. The last problem I'm facing is the power function. I figured out to compute 2 ^ (y log2(x)) instead of x ^ y and there remains a single subproblem: How can I efficiently compute 2 ^ x with x in the range (0,1) (zero and one excluded).

Since I obviously store rationals anyway, x has the form p/q (p < q). Therefore I could calculate the q-th root of 2 (Wikipedia's n-th root algorithm https://en.wikipedia.org/wiki/Nth_root_algorithm) and then exponentiate the result by p.

However, this seems very inefficient. Is there any superior algorithm? Thanks for your help.

borchero
  • 5,562
  • 8
  • 46
  • 72
  • 1
    If you think more about it you will find why the natural logarithm is called natural. It does not make much sense to base everything on the 2. `exp(y*ln(x))` has less constants. -- Study [bc libmath](http://www.rkeene.org/viewer/devel/old/bc-dos/bc/libmath.b.htm) for a proven implementation of these functions. – Lutz Lehmann Nov 09 '16 at 15:06
  • see [Power by squaring for negative exponents](http://stackoverflow.com/a/30962495/2521214) for the basics and then the sublinks for more advanced stuff especially the `fixed point bignum pow` – Spektre Nov 09 '16 at 16:47

1 Answers1

2

Since 2 ^ x = e ^ (x ln 2) and e ^ x = 1 + x + x^2/2! + x^3/3! + ... this might be a way to go. The series expansion for e ^ xconverges quickly for limited x (as in your case).

coproc
  • 6,027
  • 2
  • 20
  • 31
  • If x is still too large for quick convergence of the series the identity e^x = (e^(x/2))^2 can be used a few times. – Henry Nov 09 '16 at 13:53
  • O(n) convergence for this Taylor series. You'll need a lot of terms for double precision accuracy. – duffymo Nov 09 '16 at 14:01
  • @duffymo for `x = ln 2 = 0.69...` (the maximal value requested by the OP) and double precision the last term needed is `x^15/15!` since `x^16/16! = 1.3..E-16 < 1/2^52`. – coproc Nov 09 '16 at 14:37
  • @coproc: The question was for "arbitrary precision arithmetic". – Lutz Lehmann Nov 09 '16 at 14:43
  • @coproc - Yes, that's how O(n) works. One term for each digit of precision. Infinite precision is not practical. – duffymo Nov 09 '16 at 14:50
  • @LutzL the title of the question is "Numerical approximation ..." – coproc Nov 09 '16 at 15:07