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; (which is multiplying 3, four times), this is pretty straight forward:

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

In that same manner, to calculate , 12 rounds of multiplication rounds are required. Nevertheless it is possible to use the following method and reduce number of required rounds.

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 or .

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:

**(Square)**

**(Square)**

*(Square) *

*(Multiply) *

*(Multiply) *

what if the above is arranged as follow:

*(Square) *

*(Multiply) *

**(Square)**

**(Square)**

**(Multiply)**

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

*determines the combination of operations that needs to be carried out to reach to the final answer.*

**Square and Multiple method**### Algorithm

Following steps needs to be carried out :

- Get the binary representation of the exponent.
- Bits are read from left to right (MSB first) and it should start with a 1.
- Starting
*value*= - Start scanning bits from the left.
- As mentioned above the first bit must be 1.
- If scanned bit is 1 then, square the
*value*and then multiply by - If scanneed bit is 0 then, square the
*value*. - Repeat this for all the bits.

As an example, can be taken. Binary representation of 13 is:

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 :

Steps:

*(Square )*

*(Multiply)*

*(Square )*

*(Multiply)*

*(Square )*

*(Square )*

*(Multiply)*

*(Square )*

*(Square )*

*(Square )*

*(Multiply)*

### 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.