In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or, more generally of an element of a ring, like a polynomial of a square matrix. Some variants are commonly referred to assquare-and-multiply algorithms or binary exponentiation. In additive notation the appropriate term is double-and-add. These can be of quite general use: for example in modular arithmetic or powering of matrices.
The method is based on the observation that, for a positive integer n, we have
This may be easily implemented into the following recursive algorithm:
Function exp-by-squaring(x,n) if n<0 then return exp-by-squaring(1/x,-n); else if n=0 then return 1; else if n=1 then return x; else if n is even then return exp-by-squaring(x*x, n/2); else if n is odd then return x * exp-by-squaring(x*x, (n-1)/2).
A brief analysis shows that such an algorithm uses O(log2n) squarings and O(log2n) multiplications. For n > about 4 this is computationally more efficient than naively multiplying the base with itself repeatedly.
This algorithm calculates the value of xn after expanding the exponent in base 2k. It was first proposed by Brauer in 1939. In the algorithm below we make use of the following function f(0) = (k,0) and f(m) = (s,u) where m = u·2s with u odd.
1. y := 1 and i := l-1 2. While i>=0 do 3. (s,u) := f(ni) 4. for j:=1 to k-s do 5. y := y2 6. y := y*xu 7. for j:=1 to s do 8. y := y2 9. i := i-1 10. return y
For optimal efficiency, k should be the smallest integer satisfying