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.

Improve this question
2
  • 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 for a proven implementation of these functions. Commented Nov 9, 2016 at 15:06
  • see Power by squaring for negative exponents for the basics and then the sublinks for more advanced stuff especially the fixed point bignum pow Commented Nov 9, 2016 at 16:47

1 Answer 1

Reset to default
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).

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

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.
O(n) convergence for this Taylor series. You'll need a lot of terms for double precision accuracy.
@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: The question was for "arbitrary precision arithmetic".
@coproc - Yes, that's how O(n) works. One term for each digit of precision. Infinite precision is not practical.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.