What are some fast algorithms for computing the nth power of a number?

This question leads to an absolutely delightful little theory which everyone should know about (and everyone would know about if everyone read Knuth’s TAOCP cover to cover, as everyone should).

So let's say I give you some number x and I ask you to calculate x^{10}. At your disposal is some gizmo that can calculate products, but each calculation of a product costs you something – an arm, a leg, or a few milliseconds. Doesn't matter, as long as we agree that your goal is simply to minimize the number of multiplications.

So. What do you do?

A very reasonable solution goes like this: first calculate x^2 by multiplying x \times x. Then multiply x^2 by itself to obtain x^4=x^2\times x^2. Then do this again to get x^8=x^4\times x^4. Now to get x^{10}, all you need is to multiply x^8 by x^2, which luckily we have already calculated. So we managed to find x^{10} using four multiplications:

1. x (given)
2. x^2=x\times x
3. x^4=x^2\times x^2
4. x^8=x^4\times x^4
5. x^{10}=x^8\times x^2.

Let’s think about what's going on here. We see that it doesn't really matter what x is – it could be large, small, an integer, a floating point number, a large matrix or anything else that we can multiply. (For matrices there are useful shortcuts such as diagonalizing them first, or triangulating. But this is outside our main concern here).

The only thing that matters is the sequence of exponents in our calculation, where at each step we produce a new exponent which is the sum of two previously calculated exponents. The starting point is simply 1.

1. 1 (given)
2. 2=1+1
3. 4=2+2
4. 8=4+4
5. 10=8+2

The sequence 1,2,4,8,10 is called an addition chain ending in 10. An addition chain is just a sequence of numbers, starting with 1, where each number is the sum of two (not necessarily distinct) earlier numbers in the sequence. The length of the chain is how many numbers it has, excluding the 1 in the beginning (since we have it for free). In other words, the length is just the number of addition steps we need to take (or multiplication steps in the calculation of x^n).

The challenge of calculating x^n efficiently is now seen to be simply this: find the shortest possible addition chain ending in n. The length of this optimal chain is called l(n).

The number 10 can also be achieved via 1,2,4,5,10, where instead of greedily doubling the 4 to get 8 we’ve added the 4 and the 1 to get 5; this “sacrifice” paid up in the next step where we were able to double the 5 to land straight on 10. You can convince yourself that there’s no way to get to 10 with fewer steps. So l(10)=4.

But what is the shortest possible chain for 23? For 191? For 3^{1729}?

The most efficient step in an addition chain is doubling, which is just multiplying the previous element by 2. The sequences for 10 contain mostly doublings, and there’s an easy way to use the binary representation of a number to create an addition chain for that number that has lots of doublings: Write the number in binary; remove the leftmost “1”; replace each “1” with a “D1” and each “0” with a “D”; and interpret the result as a chain where “D” means “double” and “1” means “add 1”.

For example, to make 21, write 21=10101_2, erase the leading 1 to get 0101, and interpret this as D D1 D D1 which means “double, double, add one, double, double, add one”. Indeed, 1,2,4,5,10,20,21 is an addition chain for 21, and it is the best possible.

This “binary method” is quite efficient, and Knuth points out that some people actually claimed that it always produces the most efficient addition chain. But this is false. It is already false for 15=1111_2, where the binary method leads to 1,2,3,6,7,14,15 but you can do better: 1,2,3,6,12,15.

(Good coding exercise: write a program that calculates an addition chain of shortest possible length for a given number n).

Addition chains are incredibly subtle. Here are some surprises mentioned by Knuth:

• A “star chain” is one where every number utilizes its immediate predecessor. This seems like a very reasonable thing to do, and it is natural to assume that there’s always a star chain that achieves the minimum length. But this isn’t true. The first counterexample I know of is 2^{6106}+2^{3048}+2^{2032}+2^{1016}+1, a rather monstrous number. This was discovered by Hansen in 1958.
• If you’ve found the best addition chain for n, it is reasonable to expect that the best chain for 2n is just the best chain for n followed by a doubling. A doubling is, after all, the most efficient step. In other words, the conjecture is that l(2n)=l(n)+1. But this isn’t true. The shortest possible addition chain for 191 has 11 steps, so l(191)=11, and amazingly, l(382)=11 as well. You can get to 382 in the same(!) number of steps as you can get to 191.

(Use your code to verify those claims).

Section 4.6.3 in vol. 2 of Knuth’s “The Art of Computer Programming” contains a very detailed analysis of the theory of addition chains, as an excursion off of the efficient computation of x^n. Those deep, surprising excursions are one of the wonders of this incredible sequence of books.

There are still several open problems about addition chains, and some very clever associated algorithms. It’s amazing how a simple problem such as calculating x^n in the most efficient way leads to such unexpected depths.