Exponentiation

There are several well known exponentiation algorithms, but this one caught my eye, specifically due to its application in the Rabin-Miller primality test. Here is the math, the algorithm will follow later

Let the problem be rewritten as raise x to the power n. Let us convert n to binary


Where b0, b1, b2.. bk is the binary representation. Now lets rewrite x to the power n as

This in turn is equal to


The trick is to note that we need to compute even powers of x and determine b0, b1, .. bk. A simple trick is to, check if b0 is odd or even, if it is odd, multiply the current temporary value with x, if it is even, skip b0, but keep squaring the current exponent. Note we keep shifting n right, so that b1, b2,.. ,bk move to position b0 eventually.

Here is the algorithm from Sahni's textbook

def exponent(x, n):
 m = n
 expx = x
 power = 1

 while (m > 0):
     while ((m % 2) == 0):
         expx = expx * expx
         m = m >> 1

     m = m - 1
     power = power * expx

 return power