The method works in every semigroup and is often used to compute powers of matrices, and, especially in cryptography, to compute powers in a ring of integers modulo q. It can also be used to compute integer powers in a group, using the rule Power(x, -n) = (Power(x, n))-1.
Essentially, this algorithm is equivalent to decomposing the exponent (often means by a base conversion to binary) into a sequence of squares and products: for example
This is an implementation of the above algorithm in the Ruby programming language. It doesn't use recursion, which increases the speed even further.
In most languages you'll need to replace result=1 with result=unit_matrix_of_the_same_size_as_x to get a matrix exponentiating algorithm. In Ruby, thanks to coercion, result is automatically upgraded to the appropriate type, so this function works with matrices as well as with integers and floats.
Example implementation
def power(x,n)
result = 1
while (n != 0)
# if n is odd, multiply result with x
if ((n % 2) == 1) then
result = result * x
end
x = x*x
n = n/2
end
return result
end