Encyclopedia > Exponentiating by squaring

  Article Content

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 xn for a positive integer n:

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

Compared to the ordinary method of multiplying x with itself n-1 times, this algorithm uses only O(lg n) multiplications and therefore speeds up the computation of xn tremendously, in much the same way that the "long multiplication" algorithm speeds up multiplication over the slower method of repeated addition.

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.

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

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



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
242

... Contents 242 Centuries: 2nd century - 3rd century - 4th century Decades: 190s 200s 210s 220s 230s - 240s - 250s 260s 270s 280s 290s Years: 237 238 239 240 ...

 
 
 
This page was created in 73.6 ms