Exponentiating by squaring

Exponentiating by squaring is an algorithm used for the fast computation of large powers of a number x. The following recursive algorithm computes xⁿ for a natural number n:

                      /  1;                      if n = 0 
     Power(x, n)  =  {   Power(x2, n/2);         if n is positive and even
                      \  x * Power(x2, (n-1)/2); if n is odd

Compared to the ordinary method of multiplying x with itself n-1 times, this algorithm speeds up the computation of xⁿ tremendously.

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.

Example implementation

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 matrix exponentiating algorithm. In Ruby, thanks to weak typing, result is automatically upgraded to appropriate type, so this function works with matrices as well as with integers and floats.

def power(x,n)
    result=1
    i=1
    while (n != 0)
        if ((n & i) != 0) then
            result*=x
            n-=i
        end
        x*=x
        i<<=1
    end
    return result
end