On Raising a Number to a Power

The Egyptians, as well as other people in both ancient and modern times, spent a lot of time trying to figure out how to do calculations quickly and efficiently, developing and refining algorithms for multiplication and other important operations. Indeed, the question of how to multiply two numbers together very quickly remains an important issue in modern computer science, and there are a variety of algorithms available for that purpose, each with its own strengths and weaknesses.

In developing algorithms and solving problems, abstraction becomes an important principle. By that we mean, the ability to strip away the inessential details of a problem (or solution); in other words, to be able to focus on the essential. It leaves us with what we really need to know. We can then often use this abstracted idea fruitfully in a more general context.

At the same time, don't underestimate the value of "simple" problems to illuminate important issues. Some "simple" algorithms have endured for thousands of years. Computing powers efficiently and the role of addition chains is a case in point.

Computing Powers

In this chapter, we consider the problem of computing efficiently, given and , where .

This problem comes up in a variety of contexts. For example, we might want to implement exponentiation in a language such as C, which supports only simpler operations, such as multiplication.

Suppose we want to raise the number to the 8th power, i.e. to compute . We can do this using repeated multiplication; in this case, starting with and multiplying by seven times. We can write a simple program to perform these multiplications:

We can obtain the result in fewer steps, however:

This method costs only three multiplications. Though perhaps insignificant on a small level, the savings are significant if is executed often.

More generally, if we're given a constant , how do we implement with the smallest possible number of multiplications?

If we are not concerned with getting the answer in the smallest possible number of multiplications, the problem can be stated as follows: given a pair , produce a sequence starting with and ending with such that each entry other than the first is the product of two previous entries.

Example

Input:

Output: , with a cost of 4 multiplications.

We could also have produced the following equally correct, but more efficient, outputs:

Output: , with a cost of 3 multiplications.

Output: , with a cost of 3 multiplications.

Multiplication with Addition Chains

Let be the minimum number of multiplications required to produce by repeated multiplication. What is ? Can we calculate it exactly? Can we approximate it?

We begin with some very small examples.

For , we start with , and 0 multiplications are needed to get to ( is left undefined).

For , 1 multiplication is needed to get to .

For , we already know that we can make in 3 multiplications: . This makes 3 an upper bound on . To establish a lower bound, we can perform an exhaustive search, checking all sequences with 2 multiplications. There are only two such sequences: and . Neither of them makes . So the lower bound on is 3, which matches the upper bound. Hence, .

Note, however, that the variable is a red herring. In exponentiation, is . So, we can view exponentiation as a problem of repeated addition of exponents rather than repeated multiplication.

Hence, can be defined as the number of steps required to make , where we start at 1 and, in each subsequent step, we add two previously constructed numbers. The sequence we produce is called an addition chain. It should now be clear why is undefined.

Examples

Addition chain for 8:

Minimal addition chain for 8 (repeated doubling):

Addition chains are a simpler way to represent the original problem.

Suppose that we want the value of . We can look at some of the addition chains for 30:

	(7 additions)
	(6 additions)
	(6 additions)
	(6 additions)

From these examples, we can see that 6 is an upper bound on . To find a lower bound on , we will look at the binary representation of numbers and its connection with repeated doubling.

Binary Representations

Let be the number of 1s in the binary representation of . For example, the binary representation of 5 is 101, so . The binary representation of 12 is 1101, so . From the binary representation, we see that is the sum of powers of 2.

Here is a strategy for constructing an addition chain for : first, we use repeated doubling to create all the powers of two in the binary representation of . We then add up the powers to actually get . The first stage requires one fewer (because 1 is already available) addition than there are bits in the binary representation of ; that is, additions. The second stage takes additions. So, the entire chain needs additions.

Note that is at most the number of bits in the binary representation of ; in other words, . So, we have an upper bound on :

Example

For the binary representation of 30 is 11110. In other words, . We first create the powers of two up to 16 by repeated doubling:

This takes additions. We then add up the powers of two which make up 30. Because , we need 3 more additions to create 30 (it takes 3 additions to add together 4 numbers):

The total cost is 7 additions.

Egyptian Binary Arithmetic

The procedure of using repeated doubling is the same as Egyptian binary arithmetic (see Unary and Binary). Suppose that we want to compute 30 times 5 using the Egyptian method. This is how the calculation would look:

The number of marked entries is and the number of additions is .

We can get to 30 by an addition chain of seven steps: . However, instead of computing only the numbers in the addition chain starting from 1, let's also perform the same operations starting from 5:

In effect, we're multiplying our addition chain for 30 by 5.

There's actually a shorter addition chain that lets you get the answer for 30 times 5 faster. We can get to 30 using the addition chain :

A shortest addition chain for gives a shortest method for the Egyptian approach to multiplying by the number . The fastest scribes would seek to know for commonly arising values of . Indeed, people have been looking for the most efficient addition chains for multiplication for a long time, just for the increase in efficiency when a large number of computations are required. This remains an issue in programming today.

Repeated Squaring

In the context of exponentiation (raising a number to a power), the repeated doubling algorithm is equivalent to the repeated squaring algorithm (RQA).

What features does our solution (RQA) actually make use of? For example, does RQA require the underlying objects to be numbers?

It turns out that the repeated squaring method also works for other objects, such as those in modular arithmetic and for raising a matrix to a power. Indeed, the repeated squaring method works for any notion of "multiplication" that is associative, where the relationship holds, is well-defined, and .

Getting a Lower Bound

We have obtained an upper bound on : . How do we now get a lower bound?

Here's a useful observation. We can't make any number bigger than in steps.

Theorem. For all , no -step addition chain will contain a number greater than .

Proof. The proof is by induction. Let be the statement that no -step addition chain will contain a number greater than .

• Base case: . is true because no chain can exceed after 0 steps.
• Inductive hypothesis: suppose holds for some .
• Inductive step: at stage we add two numbers from some previous steps. By the inductive hypothesis, both numbers are at most . Therefore, the number at step , the greatest number that can be obtained is . This is exactly , so the theorem holds by induction.

All numbers obtainable in steps are bounded by . Let . Then, all numbers obtainable in steps are bounded by .

Theorem. is the largest number that can be made in steps, and it can be made only by repeated doubling.

Proof. By induction.

• Base case: is clear.
• Inductive hypothesis: the statement holds for some .
• Inductive step: to make anything as big as requires having some as big as in steps. By the inductive hypothesis, we must have all the powers of 2 up to at step . Hence, we can only double at stage . The theorem follows.

We can then establish as a lower bound on .

Suppose that . At the last stage, we added two numbers and to get 30. Without loss of generality, we assume that . Thus, . By the doubling bound, . But can't be 16 because there is only one way to make 16 in 4 stages, and it does not make 14 along the way. Thus, and .

Suppose . At stage 3, a number bigger than 7.5 but not more than 8 must have existed. There is only one sequence that gets 8 in 3 additions: . This sequence does not make 7 along the way. Hence, there is nothing to add to 8 to make 15 at the next stage. Thus, . This contradicts our earlier result. So, .

Theorem. .

Proof. The method is similar to Egyptian multiplication:

• Construct in additions.
• Using as a unit, follow a construction method for using additions. In other words, every time the construction of refers to a number , use the number instead.

Example

	Addition chain

Corollary. .

Proof. By induction on .

• Base case: for , the bound clearly holds.
• Inductive hypothesis: assume it has been shown for up to some , where .
• Inductive step: apply the previous theorem using and to obtain

By the inductive hypothesis, , so the corollary follows.

Similarly, we can prove that and that .

Does equality hold? Consider the following case: is it true that ?

The conjecture of equality fails. In the example, .

Minimal Multiplications

Over the years, mathematicians and computer scientists have proposed a variety of conjectures concerning the minimum number of additions, . For example, A. Goulard proposed that the fastest way to an even number is to make half that number, then double it.

Conjecture.

In 1895, E. de Jonquières provided a proof, which was published in ''L'Intermediare des Mathematiques'', vol. 2, pp. 125-126. The proof, however, was flawed, and it is fairly easy to come up with a counterexample. For instance, .

Furthermore, there are infinitely many such examples.

On the other hand, no one has yet settled the question of whether there is an such that .

Here is another interesting conjecture: Each stage might as well consist of adding the largest number so far to one of the other numbers. The first known counterexample is 12,509, which has the addition chain .

The Scholz-Brauer conjecture, proposed in 1937, suggests that . It has been shown to be true for many cases. For example, (since 1 + 1 = 2, 2 + 2 = 4, 4 + 1 = 5, and there is no shorter chain) and (since 1 + 1 = 2, 2 + 1 = 3, 3 + 3 = 6, 6 + 6 = 12, 12 + 12 = 24, 24 + 6 = 30, 30 + 1 = 31, and there is no shorter chain), so .

However, the general question remains open. The bound established earlier that is too weak to settle the question.

References

''The Art of Computer Programming'', Vol. 2, pp. 444-466. by Donald Knuth.