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