Exponentiation by squaring

Exponentiating by squaring is an algorithm used for the fast computation of large integer powers of a number. It is also known as the square-and-multiply algorithm or binary exponentiation. In additive groups the appropriate name is double-and-add algorithm. It implicitly uses the binary expansion of the exponent. It is of quite general use, for example in modular arithmetic.

quaring algorithm

The following recursive algorithm computes "x""n" for a non-negative integer "n":

:mbox{Power}(x,,n)= egin{cases} 1, & mbox{if }nmbox{ = 0} \ x imesmbox{Power}(x,,n-1), & mbox{if }nmbox{ is odd} \ mbox{Power}(x,,n/2)^2, & mbox{if }nmbox{ is even}end{cases}

Compared to the ordinary method of multiplying "x" with itself "n" − 1 times, in this algorithm the "n is even" case is optimized, according to::x^n=x^{n/2} imes x^{n/2}This way the algorithm uses only O(log "n") multiplications and therefore speeds up the computation of "x""n" tremendously, in much the same way that the long multiplication algorithm speeds up multiplication over the slower method of repeated addition. The benefit is had for "n" greater than or equal to "4". (Note: when measured in terms of the size of the problem data -instead of the value of the data, n- this algorithm is linear time since the size of an integer is also its logarithm.)

xn can be calculated thus, if n is an integer:
# If n < 0, {x = 1 / x; n = - n}
# i = n; y = 1; z = x
# If i is an odd number, y = y * z
# z = z2
# i = i / 2, throwing away the division remainder
# If i ≠ 0, go back to step 3
# The result is y(This method works out 00 as 1.)

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

:13789722341 (mod 2345)

would take a very long time and lots of storage space if the naïve method is used: compute 13789722341 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 13789722341 = 13789(137892)361170. So, if we computed 137892, 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"13 = "x"1101bin: = "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"8 * "x"4 * "x"1: = ("x"4)2 * ("x"2)2 * "x": = ("x"4 * "x"2)2 * "x": = (("x"2)2 * "x"2)2 * "x": = (("x"2 * "x")2)2 * "x" → algorithm needs only 5 multiplications instead of 12 (13-1)

Some more examples:
* "x"10 = (("x"2)2*"x")2 because 10 = (1,010)2 = 23+21, algorithm needs 4 multiplications instead of 9
* "x"100 = ((((("x"2*"x")2)2)2*"x")2)2 because 100 = (1,100,100)2 = 26+25+22, algorithm needs 8 multiplications instead of 99
* "x"1,000 = (((((((("x"2*"x")2*"x")2*"x")2*"x")2)2*"x")2)2)2 because 103 = (1,111,101,000)2, algorithm needs 14 multiplications instead of 999
* "x"1,000,000 = (((((((((((((((((("x"2*"x")2*"x")2*"x")2)2*"x")2)2)2)2)2*"x")2)2)2*"x")2)2)2)2)2)2 because 106 = (11,110,100,001,001,000,000)2, algorithm needs 25 multiplications instead of 999,999
* "x"1,000,000,000 = (((((((((((((((((((((((((((("x"2*"x")2*"x")2)2*"x")2*"x")2*"x")2)2)2*"x")2*"x")2)2*"x")2)2*"x")2*"x")2)2)2*"x")2)2*"x")2)2)2)2)2)2)2)2)2 because 109 = (111,011,100,110,101,100,101,000,000,000)2, algorithm needs 41 multiplications instead of 999,999,999

* [http://www.cs.princeton.edu/courses/archive/spr05/cos126/lectures/22.pdf Worked example (with modulo) for the RSA algorithm.]

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. Note that n=n-1 is redundant when n=n/2 implicitly rounds towards zero, as lower level languages would do.

def power(x,n) result = 1 while n.nonzero? if n [0] .nonzero? result = result * x n = n-1 end x = x*x n = n/2 end return resultend

The following is the C programming language equivalent program.

long pow(long x, long n){ long result = 1; while ( n ) { if ( n & 1 ) { result *= x; } x *= x; n /= 2; } return result;}

Runtime example: Compute 310

parameter x = 3 parameter n = 10 result := 1 Iteration 1 n = 10 -&gt; n is even x := x2 = 32 = 9 n := n / 2 = 5 Iteration 2 n = 5 -&gt; n is odd -&gt; 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 -&gt; n is even x := x2 = 812 = 38 = 6561 n := n / 2 = 1 Iteration 4 n = 1 -&gt; n is odd -&gt; result := result * x = 32 * 38 = 310 = 9 * 6561 = 59049 n := n - 1 = 0 return result

Runtime example: Compute 310

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" --&gt; result := result*3 = (32)2*3 = 35 = 243 Iteration for digit 4: result := result2 = ((32)2*3)2 = 310 = 59049 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 setand * 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 using 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

Calculation of products of powers

Exponentiation by squaring may also be used to calculate the product of 2 or more powers.If the underlying group or semigroup is commutative then it is often possible to reduce thenumber of multiplication by computing the product simultaneously.

Example

The formula a7×b5 may by calculated within 3 steps::((a)2×a)2×a (four multiplications for calculating a7):((b)2)2×b (three multiplications for calculating b5): (a7)×(b5) (one multiplication to calculate the product of the two)so one gets eight multiplications in total.

A faster solution is to calculate both powers simultaneously::((a×b)2×a)2×a×bwhich needs only 6 multiplications in total. Note that a×b is calculated twice, the result could be stored after the first calculation which reduces the count of multiplication to 5.

Example with numbers::27×35 = ((2×3)2×2)2×2×3 = (62×2)2×6 = 722×6 = 31,104

Calculating the powers simultaneously instead of calculating them separately always reduces thecount of multiplications if at least two of the exponents are greater than 1.

Using transformation

The example above a7×b5 may also be calculated with only 5multiplications if the expression is transformed before calculation:

a7×b5 = a2×(ab)5 with ab := a×b

ab := a×b (one multiplication)
a2×(ab)5 = ((ab)2×a)2×ab (four multiplications)

Generalization of transformation shows the following scheme:
For calculating aA×bB×...×mM×nN
1st: define ab := a×b, abc = ab×c, ...
2nd: calculate the transformed expression aA-B×abB-C×...×abc..mM-N×abc..mnN

Transformation before calculation often reduces the count of multiplicationsbut in some cases it also increases the count (see the last one of the examples below),so it may be a good idea to check the count of multiplications before using the transformed expression for calculation.

Examples

For the following expressions the count of multiplications is shown for calculating each power separately,calculating them simultaneously without transformation and calculating them simultaneously after transformation.

Example: a7×b5×c3
separate: [((a)2×a)2×a] × [((b)2)2×b] × [(c)2×c] ( 11 multiplications )
simultaneous: ((a×b)2×a×c)2×a×b×c ( 8 multiplications )
transformation: a := 2 ab := a×b abc := ab×c ( 2 multiplications )
calculation after that: (a×ab×abc)2×abc ( 4 multiplications ⇒ 6 in total )

Example: a5×b5×c3
separate: [((a)2)2×a] × [((b)2)2×b] × [(c)2×c] ( 10 multiplications )
simultaneous: ((a×b)2×c)2×a×b×c ( 7 multiplications )
transformation: a := 2 ab := a×b abc := ab×c ( 2 multiplications )
calculation after that: (ab×abc)2×abc ( 3 multiplications ⇒ 5 in total )

Example: a7×b4×c1
separate: [((a)2×a)2×a] × [((b)2)2] × [c] ( 8 multiplications )
simultaneous: ((a×b)2×a)2×a×c ( 6 multiplications )
transformation: a := 2 ab := a×b abc := ab×c ( 2 multiplications )
calculation after that: (a×ab)2×a×ab×abc ( 5 multiplications ⇒ 7 in total )

Implementation

// the following javascript function calculates // Bas [0] ^ Exp [0] x Bas [1] ^ Exp [1] x ... function productOfPowers_simpleVersion ( Bas , Exp ) { var str // temporary string // make binary representations: var maxLen = 0 var bin = new Array () for ( var i = 0 ; i < Exp.length ; i++ ) { str = Exp [i] . toString ( 2 ) bin [i] = str if ( maxLen < str.length ) maxLen = str.length } // make all binaries the same length: for ( var i = 0 ; i < bin.length ; i++ ) { while ( bin [i] . length < maxLen ) bin [i] = '0' + bin [i] } // calculate: var result = 1 // . use first binary digits: for ( var y = 0 ; y < bin.length ; y++ ) { str = bin [y] if ( str.charAt ( 0 ) = '1' ) { if ( result = 1 ) result = Bas [y] ; else result = result * Bas [y] } } // . use remaining digits: for ( var x = 1 ; x < maxLen ; x++ ) { // x : all digits except first one result = result * result for ( var y = 0 ; y < bin.length ; y++ ) { // y : all factors str = bin [y] if ( str.charAt ( x ) = '1' ) result = result * Bas [y] } } // ready: return result } // // for the following function input has to be sorted: // Exp [0] >= Exp [1] >= ... function productOfPowers_withTransformation ( Bas , Exp ) { // new bases: var tempBas = new Array () tempBas [0] = Bas [0] for ( var i = 1 ; i < Bas.length ; i++ ) tempBas [i] = Bas [i] * tempBas [i-1] // new exponents: var tempExp = new Array () for ( var i = 0 ; i < Exp.length - 1 ; i++ ) tempExp [i] = Exp [i] - Exp [i+1] tempExp [Exp.length-1] = Exp [Exp.length-1] // now compress: var basTrans = new Array () var expTrans = new Array () for ( var i = 0 ; i < tempExp.length ; i++ ) if ( tempExp [i] > 0 ) { basTrans.push ( tempBas [i] ) expTrans.push ( tempExp [i] ) } // ready: return productOfPowers_simpleVersion ( basTrans , expTrans ) } // now let's test it: alert ( 'S1: ' + productOfPowers_simpleVersion ( [ 2 , 3 ] , [ 7 , 5 ] ) ) // should be 31,104 alert ( 'T1: ' + productOfPowers_withTransformation ( [ 2 , 3 ] , [ 7 , 5 ] ) ) // once again: 31,104 alert ( 'T2: ' + productOfPowers_withTransformation ( [ 2 , 5 , 3 ] , [ 4 , 3 , 2 ] ) ) // 18,000 alert ( 'T3: ' + productOfPowers_withTransformation ( [ 2 , 5 , 3 ] , [ 3 , 3 , 2 ] ) ) // 9,000 alert ( 'T4: ' + productOfPowers_withTransformation ( [ 2 , 5 , 3 ] , [ 4 , 3 , 3 ] ) ) // 54,000 alert ( 'T5: ' + productOfPowers_withTransformation ( [ 2 , 5 , 3 ] , [ 3 , 3 , 3 ] ) ) // 27,000

Variation

From practical standpoint the following modification is also useful:

mbox{Power}(x,,n)= egin{cases} 1, & mbox{if }nmbox{ = 0} \ x imes left(mbox{Power}(x,,frac{n-1}{2}) ight)^2, & mbox{if }nmbox{ is odd} \ left(mbox{Power}(x,,frac{n}{2}) ight)^2, & mbox{if }nmbox{ is even}end{cases}

It is very similar in properties to aforementioned approach. While recursion is a natural way for calculation, it can be easily translated to iterative form. It also might provide some computational advantage (e.g., in case of small "x" and "n" = 3*2"m") as well as memory consumption reduction.

Alternatives and generalizations

Exponentiation by squaring can be viewed as a suboptimal addition-chain exponentiation algorithm: it computes the exponent via an addition chain consisting of repeated exponent doublings (squarings) and/or incrementing exponents by "one" (multiplying by "x") only. More generally, if one allows "any" previously computed exponents to be summed (by multiplying those powers of "x"), one can sometimes perform the exponentiation using fewer multiplications (but typically using more memory). The smallest power where this occurs is for "n"=15:

:a^{15} = x imes (x imes [x imes x^2] ^2)^2 ! (squaring, 6 multiplies):a^{15} = x^3 imes ( [x^3] ^2)^2 ! (optimal addition chain, 5 multiplies if "x"3 is re-used)

In general, finding the "optimal" addition chain for a given exponent is a hard problem, for which no efficient algorithms are known, so optimal chains are typically only used for small exponents (e.g. in compilers where the chains for small powers have been pre-tabulated). However, there are a number of heuristic algorithms that, while not being optimal, have fewer multiplications than exponentiation by squaring at the cost of additional bookkeeping work and memory usage. Regardless, the number of multiplications never grows more slowly than &Theta;(log "n"), so these algorithms only improve asymptotically upon exponentiation by squaring by a constant factor at best.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Exponentiation — Exponent redirects here. For other uses, see Exponent (disambiguation). Exponentiation is a mathematical operation, written as an, involving two numbers, the base a and the exponent (or power) n. When n is a positive integer, exponentiation… …   Wikipedia

  • Modular exponentiation — is a type of exponentiation performed over a modulus. It is particularly useful in computer science, especially in the field of cryptography. Doing a modular exponentiation means calculating the remainder when dividing by a positive integer m… …   Wikipedia

  • Montgomery reduction — In arithmetic computation, Montgomery reduction is an algorithm introduced in 1985 by Peter Montgomery that allows modular arithmetic to be performed efficiently when the modulus is large (typically several hundred bits). A single application of… …   Wikipedia

  • Discrete logarithm — In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga(b) is a solution of the equation ax = b over the… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Computational complexity of mathematical operations — The following tables list the running time of various algorithms for common mathematical operations. Here, complexity refers to the time complexity of performing computations on a multitape Turing machine.[1] See big O notation for an explanation …   Wikipedia

  • Doubling-oriented Doche–Icart–Kohel curve — A Doubling oriented Doche Icart Kohel curve of equation y2 = x3 − x2 − 16x In mathematics, the doubling oriented Doche–Icart–Kohel curve is a form in which an elliptic curve can be written. It is a special case of Weierstrass form and it is also… …   Wikipedia

  • Primitive root modulo n — In modular arithmetic, a branch of number theory, a primitive root modulo n is any number g with the property that any number coprime to n is congruent to a power of g (mod n ). That is, if g is a primitive root (mod n ) and gcd( a , n ) = 1,… …   Wikipedia

  • RSA — In cryptography, RSA is an algorithm for public key cryptography. It is the first algorithm known to be suitable for signing as well as encryption, and one of the first great advances in public key cryptography. RSA is widely used in electronic… …   Wikipedia

  • Primality certificate — In mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. Primality certificates allow the primality of a number to be rapidly checked without having to run an expensive or …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”