Exponentiation by squaring

From Simple English Wikipedia, the free encyclopedia

Exponentiating by squaring is an algorithm. It is used for the fast computation of large integer powers of a number. It is also known as the square-and-multiply algorithm or binary exponentiation. It implicitly uses the binary expansion of the exponent. It is of quite general use, for example in modular arithmetic.

[edit] Squaring algorithm

The following recursive algorithm computes xn for a positive integer n:

\mbox{Power}(x,\,n)=   \begin{cases} x, & \mbox{if }n\mbox{ = 1} \\                  \mbox{Power}(x^2,\,n/2), & \mbox{if }n\mbox{ is even} \\                 x\times\mbox{Power}(x^2,\,(n-1)/2), & \mbox{if }n >\mbox{2 is odd} \end{cases}

This algorithm is much faster than the ordinary method to compute such a value. Multipliying x by itself, n operation's are needed to calculate x n. With the method shown above, only log2(n) operations are needed.

In other languages