Name
  • Basic algorithms
  • Math
Edit

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.


Basic method 

The method is based on the observation that, for a positive integer n, we have

 x^n=     
    \begin{cases}
                x \, ( x^{2})^{\frac{n - 1}{2}}, & \mbox{if } n \mbox{ is odd} \\
                (x^{2})^{\frac{n}{2}} , & \mbox{if } n \mbox{ is even}.
     \end{cases}

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.

2k-ary method

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.

Algorithm:

Input
An element x of G, a parameter k > 0, a non-negative integer n = (nl−1, nl−2, ..., n0)2k and the precomputed values x3, x5, ..., x^{2^k-1}.
Output
The element xn in G
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 [1]

\lg(n) < \frac{k(k+1) \cdot 2^{2k}}{2^{k+1} - k - 2} + 1.

C++