In my previous post I proved that the “binary algorithm” (corresponding to the binary expansion of a number ) is the most efficient way to build using only doubling and incrementing steps.
Today I want to explain another nice proof, written in a comment by an anonymous1 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 denote the minimum number of doubling and incrementing steps needed to generate , and let denote the number of steps used by the binary algorithm. Note that for all : if the binary algorithm uses 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 for which . Let be the smallest such , so we must have for all .
First, note that : B uses zero steps for which is obviously optimal. Now, let’s think about the parity of :
If is odd, then the last step of any algorithm to compute 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 steps which yields . Since , there must be some other sequence of length that yields , but since is odd it must also end in an increment, so likewise we can delete the final increment step to get a sequence of steps which yields . But , so algorithm B is not optimal for —contradicting our assumption that is the smallest number for which B is not optimal.
Put more succinctly: if we can generate an odd number more efficiently than algorithm B, then we can also generate more efficiently, so the smallest non-optimal can’t be odd.
So suppose is even, say . We know the last step of B is doubling in this case, since the binary representation of ends in a . Let be a sequence of length that generates .
- If the last step of A is also doubling, then removing the doubling step would give us a way to generate more efficiently than algorithm B (since algorithm B’s sequence for is also the same as the sequence for without the final doubling step), again contradicting the minimality of .
So suppose the last step of A is incrementing. Since the binary sequence for is the same as the sequence for followed by a doubling step, . This in turn is equal to , since we assumed that for any . So we have .
On the other hand, since the last step of the optimal sequence A for is an increment, we have (since A is an optimal sequence for if and only if A without the final increment is an optimal sequence for ). This is equal to , since and are equal on everything less than . Since is odd, the binary algorithm sequence for ends with a double followed by an increment, hence .
Putting this all together, we have , which means . But this is absurd: there’s no way the optimal sequence for takes two more steps than the optimal sequence for , 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 where : the binary algorithm is optimal for every !
Well, unless their given name is actually John Doe.↩