Efficiency of repeated squaring

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 a, that is, adding 1 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 1, and no filled-in square represents a 0. In the case of 13 above, we can see that the binary representation of 13 is 1101.

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 n using only doubling and incrementing steps. That is, any other way to build n 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 0; reading the binary representation of n from left to right, double the current number and add 1 (two steps) every time you encounter a 1 bit, and only double (one step) every time you encounter a 0 bit— except that for the initial 1 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.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in computation and tagged , , , , , , , . Bookmark the permalink.

7 Responses to Efficiency of repeated squaring

  1. John Doe says:

    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.

  2. Pingback: Efficiency of repeated squaring: proof | The Math Less Traveled

  3. Naren Sundar says:

    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.

  4. Pingback: Efficiency of repeated squaring: another proof | The Math Less Traveled

  5. Pingback: Primality testing: recap | The Math Less Traveled

Comments are closed.