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 textbookdef 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
Posts
