A surprising addition chain fact:
l(2n) = l(n) for n=191

One way of computing x^4 using multiplication is: x*x*x*x. A faster way, using one fewer multiplies, is: y*y, where y=x*x.

The list of intermediate results obtained in the first method is {x^1, x^2, x^3, x^4}. The second method produces {x^1, x^2, x^4}. Listing only the exponents, we have {1,2,3,4} and {1,2,4}, respectively. These lists of exponents are called addition chains. They have the property that every number in the list (after the first which is always 1) is the sum of two prior numbers in the list.

The two prior numbers don't have to be distinct. In the case of {1,2,4}, the 4 is the sum of 2+2. The two prior numbers also don't have to include the immediately preceding number. In the chain {1,2,4,6,8,14}, the 8 is the sum of 4+4, which doesn't involve 6. We usually only consider chains that have no duplicates and whose elements are in increasing order.

The addition chain property assures us that given a chain of length k that ends in n, we can compute x^n with k-1 multiplies. For example, given the chain {1,2,3,6}, we can compute x^6 with 3 multiplies: z*z, where z=x*y and y=x*x, based on the sums 6=3+3, 3=1+2, and 2=1+1, respectively. Sometimes there is some ambiguity--in the chain {1,2,3,4,5}, the 5 could be considered the sum of 1+4 or 2+3. But we don't worry about that.

Assuming that all multiplies take approximately the same amount of time, and that no other operations are available, the fastest calculation of x^n will use the shortest chain ending in n. l(n) is defined as the length of the shortest chain for n. The shortest chain might not be unique. l(6)=4, with two shortest chains: {1,2,3,6} and {1,2,4,6}. But we don't worry about that either.

Notice that no element in a chain is more than twice the preceding element. This suggests a possible strategy for finding the shortest chain for n when n is even: find the shortest chain (somehow) for n/2, and then add n to the end of that chain. This strategy seems intuitively attractive because it combines an optimum solution for n/2 with an optimum final doubling step. Using a sports analogy, in a relay race, if your team has the fastest time in the final lap, and the fastest total time for the prior laps, you can't lose the race.

If n happens to be a power of two, this strategy finds the optimum solution of doubling at every step. But does it really find the optimum solution for all even n? This is equivalent to asking whether l(2n) > l(n) for all n. If there is some n for which l(2n) <= l(n), then this strategy will not find the minimum chain for 2n. Knuth found such an n by computer search: l(382)=l(191)=11. Thurber proved that there are an infinite number of such examples. So we will have to try harder to find a strategy for finding minimal chains that works in all cases.

For further information on addition chains and their applications, see the references on Thurber's home page.