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 
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 
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
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.
The Math Less Traveled 
Let’s call this algorithm B (for Binary), and let’s assume that there is a better algorithm A (that is: it exists an integer such that A is strictly more efficient than B ; and without loss of generality A is always at least as efficient as B on every integer). Specifically, let’s assume that A is the best algorithm, which computes each integer with the minimal number of steps.
Let’s call n the smallest integer such that A is strictly more efficient than B.
Clearly B is optimal for n = 0, using 0 steps. So n ≥ 1.
Now let’s consider the two cases n even or n odd.
– If n is odd, then the last step of both algorithm has to be incrementation (it can not be doubling). Which then implies that A has to be strictly more efficient for n-1 than B. Which contradicts n being the smallest such integer.
– If n if even, then the last step of A can not be doubling. Otherwise A would be strictly more efficient than B for n/2, which again contradicts n being the smallest such integer (and strictly positive). So it means the last step of A in incrementation (and the last of B is doubling).
Let’s note α(m) (resp. β(m)) the number of steps for algorithm A (resp. B) to compute the integer m. Writing n = 2k, we have that β(2k) > α(2k). But β(2k) = 1+β(k) = 1+α(k) on one side, and α(2k) = 1+α(2k-1) = 1+β(2k-1) = 2+β(2k-2) = 3+β(k-1) = 3+α(k-1) as we know that the last step of A was incrementation, by the definition of the algorithm B, and for the fact that for integers less that 2k, α and β are equal.
Altogether, it means that we have α(k) > 2+α(k-1). But now this last fact contradicts A being the best algorithm for all integers! Specifically, I can devise a better algorithm C which computes the same thing as A for all integers but k, and computes k by first computing k-1, and then incrementing. We would have γ(k) = 1+γ(k-1) ≤ 2+γ(k-1) < α(k): C is strictly better than A, and we have again a contradiction.
Altogether, it means that such a smallest integer n does not exist, and B computes each integer in the optimal number of steps.
Very nice! I like this proof a lot. And it is completely different than mine. =)
Pingback: Efficiency of repeated squaring: proof | The Math Less Traveled
My thoughts were along these lines…. that writing a number in base 2 must already make the minimal use of doubling. So, if we can factor the expression into 2*sub_expr + 1 then we can read of the doubling and adding sequence as ’21’. for example, 13 = 2^3 + 2^2 + 1 = 2^2(2 + 1) + 1 = 2(2(2 + 1)) + 1. Reading from the innermost expression this is… 21221. To this we prefix a leading 1 to get 121221.
Formatting issues… the line should be ‘read of the doubling and adding sequence as [sequence_for_sub_expr]21
Pingback: Efficiency of repeated squaring: another proof | The Math Less Traveled
Pingback: Primality testing: recap | The Math Less Traveled