Exponentiation by squaring is an algorithm used for fast computation of large powers. It is also known as the square-and-multiply algorithm or binary exponentiation.
The following algorithm (written in the Zeno programming language) computes xn for a positive integer n. Compared to the ordinary method of exponentiation by multiplying x with itself n - 1 times, this algorithm uses only on the order of log n multiplications and therefore speeds up the computation of xn in much the same way that multiplication speeds up repeated addition.
function power(x : real, n : int) : real
var result : real := 1
while (n ~= 0)
% if n is odd do an extra multiply
if (n mod 2 = 1) then
result := result * x
n := n - 1
end if
% do squaring
if (n > 0) then
x := x * x
n := n div 2
end if
end while
return result
end function
An example, compute 310
In this example, 5 multiplications were used instead of the 9 repeated multiplications which one would expect from the definition of exponentiation. A clever programmer would implement integer division by two (n := n div 2) by shifting all bits one position to the right.x n result 3 10 1 start 3 10 1 n even 9 5 1 n > 0, x := x2, n := n/2 9 4 9 n odd, result := result×x, n := n - 1 81 2 9 n > 0, x := x2, n := n/2 81 2 9 n even 6561 1 9 n > 0, x := x2, n := n/2 6561 0 59049 n odd, result := result×x, n := n - 1 6561 0 59049 n = 0, done