Square and Multiply algorithm

Square and Multiply algorithm is an interesting algorithm which is also known as binary exponentiation algorithm as well. The algorithm is very useful against calculation of large integer powers of a number.

For an example, like calculating; \displaystyle 3^4 (which is multiplying 3, four times), this is pretty straight forward:

3 * 3 = \displaystyle 3^2
3^2 * 3  = \displaystyle 3^3
3^3 * 3  = \displaystyle 3^4

In order to get the answer 3 rounds of calculations are required.

In that same manner, to calculate \displaystyle 5^{13} , 12 rounds of multiplication rounds are required. Nevertheless it is possible to use the following method and reduce number of required rounds.

5^1 * 5^0 =\displaystyle 5^1
5^1 * 5^1 = \displaystyle 5^2
5^2 * 5^2  = \displaystyle 5^4
5^4 * 5^4  = \displaystyle 5^8
5^8 * 5^4  = \displaystyle 5^{12}
5^{12} * 5^1  = \displaystyle 5^{13}

Above is a short cut method to obtain the answer, however things might go weird when the exponent is really large, for example something like \displaystyle 3^{105} or \displaystyle 2^{846} .

Even using the shortcut method seems quite cumbersome but better than the first method.

However, in such situations Square and Multiply method comes handy. Even in the second method, we have applied Square and Multiply operation to get the answer. Using this algorithm make it easier to apply the logic behind, especially when it needs to be implemented as a computer program.

Taking back the earlier example, check the operations carried out:

5^1 * 5^0 =\displaystyle 5^1
(Square) 5^1 * 5^1 = \displaystyle 5^2
(Square) 5^2 * 5^2  = \displaystyle 5^4
(Square) 5^4 * 5^4  = \displaystyle 5^8
(Multiply) 5^8 * 5^4  = \displaystyle 5^{12}
(Multiply) 5^{12} * 5^1  = \displaystyle 5^{13}

what if the above is arranged as follow:

5^1 * 5^0 =\displaystyle 5^1
(Square) 5^1 * 5^1 = \displaystyle 5^2
(Multiply) 5^2 * 5^1  = \displaystyle 5^3
(Square) 5^3 * 5^3  = \displaystyle 5^6
(Square) 5^6 * 5^6  = \displaystyle 5^{12}
(Multiply) 5^{12} * 5^1  = \displaystyle 5^{13}

Even though that there is no much improvement in computational rounds, the second approach aligns with the Square and Multiple method. So as you might already have understood, the Square and Multiple method determines the combination of operations that needs to be carried out to reach to the final answer.

Algorithm

Following steps needs to be carried out :

  1. Get the binary representation of the exponent.
  2. Bits are read from left to right (MSB first) and it should start with a 1.
  3. Starting value\displaystyle n^0
  4. Start scanning bits from the left.
  5. As mentioned above the first bit must be 1.
  6. If scanned bit is 1 then, square the value and then multiply by \displaystyle n
  7. If scanneed bit is 0 then, square the value.
  8. Repeat this for all the bits.

As an example, \displaystyle 5^{13} can be taken. Binary representation of 13 is: 13_{ten}  = \displaystyle 1101_{two}

Since the first bit is 1, initially the value is squared and multiplied. Then next bit is taken, it is 1, therefore the value is square and multiplied again.  Then the third bit is 0, therefore the value is only squared. Final bit is 1, the value needs to be squared and multiplied. Pretty easy right !

Time to check this method for a larger exponent. Lets take following : \displaystyle 3^{105}

\displaystyle 105_{ten} = 1101001_{two}

Steps:
(Square  ) 3^0 * 3^0 =\displaystyle 3^0
(Multiply) 3^0 * 3^1 =\displaystyle 3^1
(Square ) 3^1 * 3^1 =\displaystyle 3^2
(Multiply) 3^2 * 3^1 =\displaystyle 3^3
(Square ) 3^3 * 3^3 =\displaystyle 3^6
(Square ) 3^6 * 3^6 =\displaystyle 3^{12}
(Multiply) 3^{12} * 3^1 =\displaystyle 3^{13}
(Square ) 3^{13} * 3^{13} =\displaystyle 3^{26}
(Square ) 3^{26} * 3^{26} =\displaystyle 3^{52}
(Square ) 3^{52} * 3^{52} =\displaystyle 3^{104}
(Multiply) 3^{104} * 3^1 =\displaystyle 3^{105}

Python Implementation

Following is the python code:

string bin(int num)

The above function takes an integer as the argument and then return the binary equivalent as a string. It starts with 0b prefix. Therefore it is required to consider [2:] of the string. As the first bit is always 1, the final output of the first step is always equal to x. That is the reason for starting the for loop from 3.

def exp_func(x, y):
    exp = bin(y)
    value = x

    for i in range(3, len(exp)):
        value = value * value
        if(exp[i:i+1]=='1'):
            value = value*x
    return value

Summary

Square and Multiply algorithm is a very useful algorithm which can be used to calculate values of integers having really large exponents. The number of calculation rounds is relatively less compared to the brute force method.

Advertisements

Please add your valuable idea below, will make a discussion, thanks !

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s