1
$\begingroup$

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?

2 Answers 2

4

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).

0

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.

  • 1
    This is incorrect: https://en.wikipedia.org/wiki/Addition-chain_exponentiation.2013-12-09