Square and Multiply

We’ve all done math problems that look like this: 3⁵, 4¹⁰, or N³⁷. These are known as an exponentiation. And there is a trick to solving these problems with less calculations than simply multiplying the base number over and over again. That trick is known as the Square and Multiply method.

Take 3⁵. If doing that one manually, without the Square and Multiply method, it would take 5 different calculations:

1. Convert the exponent to Binary.
2. For the first 1, simply list the number
3. For each ensuing 0, do Square operation
4. For each ensuing 1, do Square and Multiply operations

As an example, lets run 3⁵ through the process:

5 = 101 in Binary
1    First One lists Number               3
0    Zero calls for Square               (3)2
1    One calls for Square + Multiply    ((3)2)2*3

Of course, going from five calculations to three calculations is not a huge gain in efficiency. But as you use the Square and Multiply method with bigger and bigger exponent values, the efficiency increase gets larger.

Take a look at what happens when you use an exponent of 37 (aka, N37):

37 = 100101 in Binary
1    First One lists number                  N
0    Zero calls for Square                  (N)2
0    Zero calls for Square                 ((N)2)2
1    One calls for Square + Multiply      (((N)2)2)2*N
0    Zero calls for Square               ((((N)2)2)2*N)2
1    One calls for Square + Multiply    (((((N)2)2)2*N)2)2*N

We went from requiring 37 steps to only 7.

You can determine the total number of calculations required when using the Square and Multiple method. Since each step requires at least a square operation, each binary digit (after the first) result in at least one operation. Then, since each binary 1 also calls for an additional and multiply operation, you count the binary 1’s a second time.

Or, to put it another way, ignoring the left-most binary 1, count each binary 0 as one operation, and each binary 1 as two operations.

Here are some more examples:

5      101          3 calculations
21     100101       7 calculations
47     101111       9 calculations
56     111000       7 calculations
99     1100011      9 calculations
112    1110000      8 calculations
1024   10000000000  10 calculations

A lot of Cryptography math formulas require exponentiation on incredibly large numbers. When doing such large calculations, computers use methods like the Square and Multiply method to achieve the end result without having to go through every multiplication operation a typical exponentiation would require.

Related Posts:

RSA Example

Subnetting Mastery

Host to Host through a Router

Host to Host through a Switch