Exponentiation by squaring

Exponentiating by squaring is an algorithm used for the fast computation of large integer powers of a number x. 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.

Contents

1 Squaring algorithm 2 Further applications 3 Example implementations 3.1 Computation by powers of 2 3.1.1 Runtime example: Compute 310 3.2 Computation by binary representation 3.2.1 Runtime example: Compute 310 3.3 Generalization with example 3.3.1 Generalization 3.3.2 Text application 4 Alternatives

Squaring algorithm

The following recursive algorithm computes xⁿ for a positive integer n:

<math>

\mbox{Power}(x,\,n)=\left\{ \begin{matrix} x, & \mbox{if }n\mbox{ = 1} \\ \mbox{Power}(x^2,\,n/2), & \mbox{if }n\mbox{ is even} \\ x\times\mbox{Power}(x^2,\,(n-1)/2), & \mbox{if }n >\mbox{2 is odd} \\ \end{matrix}\right. <math>

Compared to the ordinary method of multiplying x with itself n − 1 times, this algorithm uses only O(log n) multiplications and therefore speeds up the computation of xⁿ tremendously, in much the same way that the "long multiplication" algorithm speeds up multiplication over the slower method of repeated addition.

Further applications

The same idea allows fast computation of large exponents modulo a number. Especially in cryptography, it is useful to compute powers in a ring of integers modulo q. It can also be used to compute integer powers in a group, using the rule

Power(x, -n) = (Power(x, n))^-1.

The method works in every semigroup and is often used to compute powers of matrices,

For example, the evaluation of

13789⁷²²³⁴¹ (mod 2345)

would take a very long time and lots of storage space if the naïve method is used: compute 13789⁷²²³⁴¹ then take the remainder when divided by 2345. Even using a more effective method will take a long time: square 13789, take the remainder when divided by 2345, multiply the result by 13789, and so on. This will take 722340 modular multiplications. The square-and-multiply algorithm is based on the observation that 13789⁷²²³⁴¹ = 13789(13789²)³⁶¹¹⁷⁰. So, if we computed 13789², then the full computation would only take 361170 modular multiplications. This is a gain of a factor of two. But since the new problem is of the same type, we can apply the same observation again, once more approximately halving the size.

The repeated application of this algorithm is equivalent to decomposing the exponent (by a base conversion to binary) into a sequence of squares and products: for example

x¹³ = x¹¹⁰¹

= x^{(1*2^3 + 1*2^2 + 0*2^1 + 1*2^0)}

= x^{1*2^3} * x^{1*2^2} * x^{0*2^1} * x^{1*2^0}

= x^{2^3} * x^{2^2} * 1 * x^{2^0}

= x⁸ * x⁴ * x¹

= (x⁴)² * (x²)² * x

= (x⁴ * x²)² * x

= ((x²)² * x²)² * x

= ((x² * x)²)² * x       → algorithm needs only 5 multiplications instead of 13 - 1 = 12

Some more examples:

• x¹⁰ = ((x²)²*x)² because 10 = (1,010)₂ = 2³+2¹, algorithm needs 4 multiplications instead of 9
• x¹⁰⁰ = (((((x²*x)²)²)²*x)²)² because 100 = (1,100,100)₂ = 2⁶+2⁵+2², algorithm needs 8 multiplications instead of 99
• x^1,000 = ((((((((x²*x)²*x)²*x)²*x)²)²*x)²)²)² because 10³ = (1,111,101,000)₂, algorithm needs 14 multiplications instead of 999
• x^1,000,000 = ((((((((((((((((((x²*x)²*x)²*x)²)²*x)²)²)²)²)²*x)²)²)²*x)²)²)²)²)²)² because 10⁶ = (11,110,100,001,001,000,000)₂, algorithm needs 25 multiplications
• x^{1,000,000,000} = ((((((((((((((((((((((((((((x²*x)²*x)²)²*x)²*x)²*x)²)²)²*x)²*x)²)²*x)²)²*x)²*x)²)²)²*x)²)²*x)²)²)²)²)²)²)²)²)² because 10⁹ = (111,011,100,110,101,100,101,000,000,000)₂, algorithm needs 41 multiplications

Example implementations

Computation by powers of 2

This is a non-recursive implementation of the above algorithm in the Ruby programming language.

In most statically typed languages, result=1 must be replaced with code assigning an identity matrix of the same size as x to result to get a matrix exponentiating algorithm. In Ruby, thanks to coercion, result is automatically upgraded to the appropriate type, so this function works with matrices as well as with integers and floats.

def power(x,n)
    result = 1
    while (n != 0)
        # if n is odd, multiply result with x. decrement n by 1
        if (n.modulo(2) == 1) then
            result = result * x
            n = n-1
        end
        # last iteration: no need to compute x = one more power of 2
        if (n > 0) then
            x = x*x
            n = n/2
        end
    end
    return result
end

Runtime example: Compute 3¹⁰

parameter x =  3
parameter n = 10
result := 1

Iteration 1
  n = 10 -> n is even
  x := x2 = 32 = 9
  n := n / 2 = 5

Iteration 2
  n = 5 -> n is odd
      -> result := result * x = 1 * x = 1 * 32 = 9
         n := n - 1 = 4
  x := x2 = 92 = 34 = 81
  n := n / 2 = 2

Iteration 3
  n = 2 -> n is even
  x := x2 = 812 = 38 = 6,561
  n := n / 2 = 1

Iteration 4
  n = 1 -> n is odd
      -> result := result * x = 32 * 38 = 310 = 9 * 6561 = 59,049
         n := n - 1 = 0

return result

Computation by binary representation

function power ( x, n )
  if ( n equals 0 ) return 1
  result := x
  bin := binary_representation_of ( n )
  for digit := second_digit_of_bin to last_digit_of_bin
    result := result * result
    if ( digit equals "1" ) result := result * x
  end
  return result
end

Runtime example: Compute 3¹⁰

result := 3
bin := "1010"

Iteration for digit 2:
  result := result2 = 32 = 9
  1010bin - Digit equals "0"

Iteration for digit 3:
  result := result2 = (32)2 = 34  = 81
  1010bin - Digit equals "1" --> result := result*3 = (32)2*3 = 35  = 243

Iteration for digit 4:
  result := result2 = ((32)2*3)2 = 310  = 59,049
  1010bin - Digit equals "0"

return result

JavaScript-Demonstration: http://home.arcor.de/wzwz.de/wiki/ebs/en.htm

Generalization with example

Generalization

Let the pair ( S, * ) be a Semigroup, that means S is an arbitrary set and * is an associative binary operation on S:

• For all elements a and b of S is a*b also an element of S
• For all elements a, b and c of S is valid: (a*b)*c equals a*(b*c)

We may call * a "multiplication" and define an "exponentiation" E in the following way:
For all elements a of S:

• E ( a, 1 ) := a
• For all natural numbers n > 0 is defined: E ( a, n+1 ) := E ( a, n ) * a

Now the algorithm exponentiation by squaring may be used for fast computing of E-values.

Text application

Because the concatenation + is an associative operation on the set of all finite strings over a fixed alphabet ( with the empty string "" as its identity element ) exponentiation by squaring may be used for fast repeating of strings.

Example ( javascript ):
function repeat ( s, n ) {
  if ( s == "" || n < 1 ) return ""
  var res = s
  var bin = n.toString ( 2 )
  for ( var i = 1 ; i < bin.length ; i++ ) {
    res = res + res
    if ( bin.charAt ( i ) == '1' ) res = res + s
  }
  return res
}
The call repeat ( 'Abc', 6 ) returns the string AbcAbcAbcAbcAbcAbc

Alternatives

Addition chain exponentiation can in some cases require fewer multiplications by using an efficient addition chain to provide the multiplication order. However, exponentiating by squaring is simpler to set up and typically requires less memory.fr:exponentiation rapide pl:Algorytm szybkiego potęgowania