Exponentiation by squaring
Exponentiating by squaring is an algorithm. It is used for quickly working out large integer powers of a number. It is also known as the square-and-multiply algorithm or binary exponentiation. It uses the binary expansion of the exponent. It is of quite general use, for example in modular arithmetic.
Squaring algorithm[change | change source]
This algorithm is much faster than the ordinary method to compute such a value. Multipliying x by itself, n operations are needed to calculate x n. With the method shown above, only log2(n) operations are needed.