Efficiency of repeated squaring: another proof

In my previous post I proved that the “binary algorithm” (corresponding to the binary expansion of a number $n$ ) is the most efficient way to build $n$ using only doubling and incrementing steps.

Today I want to explain another nice proof, written in a comment by an anonymous¹ commenter. So although this proof is not originally due to me, I thought it deserved to be written up more fully and not squished into a comment, and I’ve changed it in a few minor ways which I think make it easier to understand (although perhaps not everyone will agree!).

Let $\alpha(n)$ denote the minimum number of doubling and incrementing steps needed to generate $n$ , and let $\beta(n)$ denote the number of steps used by the binary algorithm. Note that $\alpha(n) \leq \beta(n)$ for all $n$ : if the binary algorithm uses $\beta(n)$ steps, then the optimal number of steps can’t be any higher.

Now, suppose that the binary algorithm (call it algorithm B) isn’t the most efficient algorithm (our goal will be to derive a contradiction from this assumption). That means there exist values of $n$ for which $\alpha(n) < \beta(n)$ . Let $m$ be the smallest such $n$ , so we must have $\alpha(k) = \beta(k)$ for all $k < m$ .

First, note that $m > 0$ : B uses zero steps for $n = 0$ which is obviously optimal. Now, let’s think about the parity of $m$ :

If $m$ is odd, then the last step of any algorithm to compute $m$ has to be incrementing, since that’s the only way to get an odd number—if the last step is doubling then the result would be even. Removing this last incrementing step from the sequence generated by algorithm B results in a sequence of $\beta(m) - 1$ steps which yields $m-1$ . Since $\alpha(m) < \beta(m)$ , there must be some other sequence of length $\alpha(m)$ that yields $m$ , but since $m$ is odd it must also end in an increment, so likewise we can delete the final increment step to get a sequence of $\alpha(m) - 1$ steps which yields $m-1$ . But $\alpha(m) - 1 < \beta(m) - 1$ , so algorithm B is not optimal for $(m-1)$ —contradicting our assumption that $m$ is the smallest number for which B is not optimal.

Put more succinctly: if we can generate an odd number $m$ more efficiently than algorithm B, then we can also generate $m-1$ more efficiently, so the smallest non-optimal $m$ can’t be odd.
So suppose $m$ is even, say $m = 2k$ . We know the last step of B is doubling in this case, since the binary representation of $m$ ends in a $0$ . Let $A$ be a sequence of length $\alpha(m)$ that generates $m$ .
- If the last step of A is also doubling, then removing the doubling step would give us a way to generate $k = m/2$ more efficiently than algorithm B (since algorithm B’s sequence for $m/2$ is also the same as the sequence for $m$ without the final doubling step), again contradicting the minimality of $m$ .
- So suppose the last step of A is incrementing. Since the binary sequence for $2k$ is the same as the sequence for $k$ followed by a doubling step, $\beta(2k) = 1 + \beta(k)$ . This in turn is equal to $1 + \alpha(k)$ , since we assumed that $\alpha(k) = \beta(k)$ for any $k < m$ . So we have $\beta(2k) = 1 + \alpha(k)$ .
  
  On the other hand, since the last step of the optimal sequence A for $m = 2k$ is an increment, we have $\alpha(2k) = 1 + \alpha(2k-1)$ (since A is an optimal sequence for $2k$ if and only if A without the final increment is an optimal sequence for $2k-1$ ). This is equal to $1 + \beta(2k-1)$ , since $\alpha$ and $\beta$ are equal on everything less than $k$ . Since $2k-1$ is odd, the binary algorithm sequence for $2k-1$ ends with a double followed by an increment, hence $1 + \beta(2k-1) = 2 + \beta(2k-2) = 3 + \beta(k-1) = 3 + \alpha(k-1)$ .
  
  Putting this all together, we have $1 + \alpha(k) = \beta(2k) > \alpha(2k) = 3 + \alpha(k-1)$ , which means $\alpha(k) > 2 + \alpha(k-1)$ . But this is absurd: there’s no way the optimal sequence for $k$ takes two more steps than the optimal sequence for $k-1$ , because we could just add an increment.

So we have shown that all these cases lead to absurdity: the conclusion is that there can’t be any such $n$ where $\alpha(n) < \beta(n)$ : the binary algorithm is optimal for every $n$ !

Well, unless their given name is actually John Doe.↩

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

3 Responses to Efficiency of repeated squaring: another proof

Simon Tatham says:

September 10, 2018 at 4:39 am

We could shorten that complicated last case by borrowing your lemma from the previous proof, that there’s always a sequence of shortest length with no two consecutive increment steps.

Let A be not just a optimal sequence for $m$, but one with no consecutive increments. Then, if $m$ is even and the last step of A is an increment, then the step before that must also have been an increment, since it yielded $m-1$ , which is odd. $\Box$
- Brent says:
  
  September 10, 2018 at 10:40 am
  
  Ah, good point!
Pingback: Primality testing: recap | The Math Less Traveled

Comments are closed.