As you probably realized if you read both, my recent post without words connects directly to my previous post on exponentiation by repeated squaring Each section shows the sequence of operations used by the repeated squaring algorithm to build up a certain exponent. For example, here’s the diagram for 13:
Each row has two open rectangles exactly the same length as the previous row; this represents squaring, that is, multiplying the exponent by two. Some rows also have an extra dark square at the end, which represents multiplying by , that is, adding to the exponent. You can read off the binary representation of the final exponent by reading from top to bottom: a filled-in square represents a , and no filled-in square represents a . In the case of 13 above, we can see that the binary representation of 13 is .
Commenter Steven G made a very interesting guess, that the images represented the most efficient way to form each integer using only doubling and adding 1. This seems plausible, but I was not at all sure. There are lots of ways to build a given integer by doubling and adding 1. For example, we can get 3 by adding 1 three times; or by adding 1, then doubling, then adding 1. We can get 6 by adding 1, doubling, adding 1, and doubling; or by adding 1, doubling twice, and then adding 1 twice. For certain numbers, might there be some weird clever way to build them more efficiently than the algorithm corresponding to their binary representation?
Claim: the binary algorithm is the most efficient way to build using only doubling and incrementing steps. That is, any other way to build by doubling and incrementing uses an equal or greater number of steps than the binary algorithm.
Let’s make this precise:
“One step” refers to either a doubling step or an incrementing step.
The binary algorithm is as follows: start with ; reading the binary representation of from left to right, double the current number and add 1 (two steps) every time you encounter a bit, and only double (one step) every time you encounter a bit— except that for the initial bit you simply add one, instead of doing a useless doubling first (it’s pointless to double zero).
Can you prove the claim? I think I have a nice proof, which I’ll share in a future post, but I’m interested to see what others come up with.