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?