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. In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a defined end-state. ... The integers are commonly denoted by the above symbol. ... A number is an abstract entity that represents a count or measurement. ... An additive group is a group, and any group can be written as an additive group, so the adjective additive does not describe a class of groups, but rather the notation used to write the group operation. ... The binary numeral system, or base-2 number system, is a numeral system that represents numeric values using two symbols, usually 0 and 1. ... Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ...

Squaring algorithm

The following recursive algorithm computes xⁿ for a positive integer n: A visual form of recursion known as the Droste effect. ... A negative number is a number that is less than zero, such as −3. ... The integers are commonly denoted by the above symbol. ...

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. The benefit is had for n greater than or equal to 4. (Note: when measured in terms of the size of the problem, this algorithm is linear time since the size of an integer is its logarithm.) Big O notation or Big Oh notation, and also Landau notation or asymptotic notation, is a mathematical notation used to describe the asymptotic behavior of functions. ... A multiplication algorithm is an algorithm (or method) to multiply two numbers. ... In computational complexity, an algorithm is said to take linear time, or O(n) time, if the time it requires is proportional to the size of the input, which is usually denoted n. ...

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 Modular exponentiation is a type of exponentiation performed over a modulus. ... The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write) is the study of message secrecy. ... In ring theory, a branch of abstract algebra, a ring is an algebraic structure in which addition and multiplication are defined and have similar properties to those familiar from the integers. ... Modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic because of its use in the 24-hour clock system) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... This picture illustrates how the hours in a clock form a group. ...

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

The method works in every semigroup and is often used to compute powers of matrices, In mathematics, a semigroup is an algebraic structure consisting of a set S closed under an associative binary operation. ... For the square matrix section, see square matrix. ...

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. In mathematics, the result of the division of two integers usually cannot be expressed with an integer quotient, unless a remainder —an amount left over— is also acknowledged. ... A result is the final consequence of a sequence of actions or events (broadly incidents and accidents) expressed qualitatively or quantitatively, being a loss, injury, disadvantage, advantage, gain, victory or simply a value. ...

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^1101_bin

= 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 12 (13-1)

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. Ruby is a reflective, object-oriented 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. On computer science, a datatype (often simply type) is a name or label for a set of values and some operations which can be performed on that set of values. ... In linear algebra, the identity matrix of size n is the n-by-n square matrix with ones on the main diagonal and zeros elsewhere. ...

 def power(x,n) result = 1 while n.nonzero? if n.modulo(2).nonzero? result = result * x n = n-1 end x = x*x n = n/2 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 = 6561 n := n / 2 = 1 Iteration 4 n = 1 -> n is odd -> result := result * x = 32 * 38 = 310 = 9 * 6561 = 59049 n := n - 1 = 0 return result 

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 = 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 set and * is an associative binary operation on S: In mathematics, a semigroup is an algebraic structure consisting of a set S closed under an associative binary operation. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In mathematics, associativity is a property that a binary operation can have. ... In mathematics, a binary operation is a calculation involving two input quantities, in other words, an operation whose arity is two. ...

• 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. In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ...

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. In computer programming and some branches of mathematics, strings are sequences of various simple objects. ... In mathematics, an identity element (or neutral element) is a special type of element of a set with respect to a binary operation on that set. ...

 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 

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 the number of multiplication by computing the product simultaneously. In mathematics, especially abstract algebra, a binary operation * on a set S is commutative if x * y = y * x for all x and y in S. Otherwise * is noncommutative. ...

Example

The formula a⁷×b⁵ may by calculated within 3 steps:

((a)²×a)²×a (four multiplications for calculating a⁷)

((b)²)²×b (three multiplications for calculating b⁵)

(a⁷)×(b⁵) (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)²×a)²×a×b

which 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:

2⁷×3⁵ = ((2×3)²×2)²×2×3 = (6²×2)²×6 = 72²×6 = 31,104

Calculating the powers simultaneously instead of calculating them separately always reduces the count of multiplications iff at least two of the exponents are greater than 1. IFF, Iff or iff can stand for: Interchange File Format - a computer file format introduced by Electronic Arts Identification, friend or foe - a radio based identification system utilizing transponders iff - the mathematics concept if and only if International Flavors and Fragrances - a company producing flavors and fragrances International Freedom Foundation...

Using transformation

The example above a⁷×b⁵ may also be calculated with only 5 multiplications if the expression is transformed before calculation:

a⁷×b⁵ = a²×ab⁵ with ab := a×b

ab := a×b (one multiplication)

a²×ab⁵ = ((ab)²×a)²×ab (four multiplications)

Generalization of transformation shows the following scheme:
For calculating a^A×b^B×...×m^M×n^N
1st: define ab := a×b, abc = ab×c, ...
2nd: calculate the transformed expression a^A-B×ab^B-C×...×abc..m^M-N×abc..mn^N

Transformation before calculation often reduces the count of multiplications but 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: a⁷×b⁵×c³
separate: [((a)²×a)²×a] × [((b)²)²×b] × [(c)²×c] ( 11 multiplications )
simultaneous: ((a×b)²×a×c)²×a×b×c ( 8 multiplications )
transformation: a := 2   ab := a×b   abc := ab×c ( 2 multiplications )
calculation after that: (a×ab×abc)²×abc ( 4 multiplications ⇒ 6 in total )

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

Example: a⁷×b⁴×c¹
separate: [((a)²×a)²×a] × [((b)²)²] × [c] ( 8 multiplications )
simultaneous: ((a×b)²×a)²×a×c ( 6 multiplications )
transformation: a := 2   ab := a×b   abc := ab×c ( 2 multiplications )
calculation after that: (a×ab)²×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 userful:

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ⁿ) as well as memory consumption reduction.

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. In mathematics, addition chain exponentiation is a fast method of exponentation. ... In mathematics, an addition chain is a sequence a0, a1, a2, a3, ... that satisfies a0 = 1, and for each k>0: ak = ai + aj for some i, j < k. ...