Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've implemented a big number arithmetics. I've got addition, subtraction and multiplication so far and I want to implement power with positive, integral exponent.

The power will be evaluated manually - by multiplying the value by itself n times. I've observed however, that it can be optimized.

Take $2^4$. $2^4 = 2 * 2 * 2 * 2 = 16$. But remember, that in the algorithm I'm able to store the partial results. So I can evaluate $2 * 2 = 4$ and then $4 * 4 = 16$, thus reducing amount of multiplications from 3 to 2. The previous idea can be written as:

$$4 = 2 + 2; (n^4 = n^2 \cdot n^2)\\ 2 = 1 + 1; (n^2 = n^1 \cdot n^1)$$

Primarily I thought, that the division-by-two algorithm does the trick. But then I've discovered something. Take 15 into consideration.

$$15 = 7 + 7 + 1;\\ 7 = 3 + 3 + 1;\\ 3 = 1 + 1 + 1$$ This method gives us total of 6 multiplications needed to raise value to 15th power. But:

$$15 = 5 + 5 + 5;\\ 5 = 2 + 2 + 1;\\ 2 = 1 + 1$$ What gives us total of 5 multiplications.

Now I'm confused. What rules does this idea follow?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

Look up exponentiation by repeated squaring and addition chains, and for a more extensive treatment see Knuth: TAOCP vol. 2, Seminumerical Algorithms. Beware that repeated squaring isn't always more efficient than repeated multiplication (e.g. for dense polynomials, see papers by R.J. Fateman).

share|improve this answer

You can easily compute the minimal amount of multiplications by dynamic programming it: for a number n, we'll say f(n) is the smallest number of multiplications needed to get x^nfrom x. then f(n) = min (for 1<=i<=n) of (f(i)+f(floor(n/i))+f(n-i*floor(n/i))) f(1) = 0. this way you can compute these values in O(n^2), and this also gives a recurise definition of f.

share|improve this answer
    
This is incorrect: en.wikipedia.org/wiki/Addition-chain_exponentiation. –  StefanKarpinski Dec 9 '13 at 23:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.