# Show that you can calculate x ^ 62 using only 8 multiplications

I have this method:

power (x, n) {
if n == 0
return 1
if n is even
return power(x * x, n/2)
if n is odd
return power(x * x, n/2) * x


I thought to calculate x ^ 64, which can be done using 6 multiplication actions, and then get x ^ 62 from there, but here I stuck. We can achieve it only by dividing by x and then again by x and not multiplying. Any idea of how to solve it or maybe another approach?

• Look up the russian multiplication algorithm. Essentially, it converts to binary, which is $\log_2$ doublings, and adding. Here's one link: cut-the-knot.org/Curriculum/Algebra/PeasantMultiplication.shtml – Ethan Bolker Mar 3 '19 at 14:16
• The topic of Exponentiation by squaring comes up often enough to deserve treatment as a "common question" or abstract duplicate, but the closest such item we have is How do I compute $a^b \bmod c$ by hand?, which only treats it under some Answers alongside many other aspects of the modular exponentiation computation. In this particular example $n=62$ the "simple" additive chain noted by @EthanBolker and others here attains the minimum length $8$. – hardmath Mar 9 '19 at 17:33
• With respect to your code, it omits another "immediate return" case that would improve recursion efficiency. You have if n==0 return 1, and I'd follow it with if n==1 return x. – hardmath Mar 9 '19 at 18:25

I don't know anything about programming. So I'm not sure what you are looking for. But you can calculate $$x^{62}$$ using $$8$$ multiplication as follows : $$x^2\to x^4\to x^6\to x^{12}\to x^{24}\to x^{30}\to x^{31}\to x^{62}.$$

Here are $$8$$ more solutions using $$8$$ multiplications:

$$2,3,6,12,24,48,14,62$$.

$$2,4,6,12,24,48,14,62$$.

$$2,4,8,12,24,48,14,62$$.

$$2,3,5,10,20,40,22,62$$.

$$2,4,5,10,20,40,22,62$$.

$$2,4,8,10,20,40,22,62$$.

$$2,4,8,16,20,40,22,62$$.

$$2,3,5,10,11,20,31,62$$.

I don't see any obvious way to determine an optimal solution, nor an easy way to prove that there is none using $$7$$ multiplications.

• Knuth has a good discussion of constructions for additive chains (which is what we're performing here to reach exponents via multiplication) in AoCP, vol. II if memory serves. Much earlier he'd published some papers on it, but determining the chain of minimal length in general is an open problem. – hardmath Mar 9 '19 at 3:24
• @hardmath: That's interesting, thanks! Though if you mean Knuth gives an algorithm, yes it's easy to find an optimal solution via a program. But no obvious way to humanly prove such things, especially for longer chains. – user21820 Mar 9 '19 at 3:36
• From what I recall, Knuth describes three constructions (one being the "simple" binary expansion of $n$ and its corresponding additive chain), and a comparison of lengths produced for $n$ up to some moderate limit, with the observation that no one construction is always superior. Optimal chains for $n \lt 149$ are diagrammed here, confirming that eight are best possible for $n=62$. – hardmath Mar 9 '19 at 5:31
• @hardmath: Hmm that linked webpage says that it is an open conjecture that the number of steps is at least $\lfloor \log_2(n) \rfloor + \log_2(v(n))$ where $v(n)$ is the number of ones in the binary representation of $n$, which does give $8$ for $n = 62$. I wonder why it's still open; it doesn't sound like a difficult problem... =) – user21820 Mar 9 '19 at 6:05
• @hardmath: This question had stuck in my mind and I was going to ask the general problem as an original question, but I checked back here only to see that you've given me the name to search for (additive chains) and have already asked it previously! It sure does sound like the kind of problem Knuth is likely to have collected a definitive answer to. Knowing that he hasn't gives me that same feeling that there could be a lot of interesting math here. – JonathanZ supports MonicaC Mar 9 '19 at 19:02