Information About

Exponentiation By Squaring
  CATEGORIES ABOUT EXPONENTIATION BY SQUARING
   
exponentials
   
arbitrary precision algorithms
   
computer arithmetic
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...




SQUARING ALGORITHM


The following Recursive Algorithm computes ''x''''n'' for a Positive Integer ''n'':

:
\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 imes\mbox{Power}(x^2,\,(n-1)/2), & \mbox{if }n >\mbox{2 is odd} \
\end{matrix} ight.


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''''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''.


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

  • 2^3 + 1---2^2 + 0---2^1 + 1---2^0)

  • 2^3 --- ''x''1---2^2 --- ''x''0---2^1 --- ''x''1---2^0

  • ''x''2^2 --- 1 --- ''x''2^0

  • ''x''4 --- ''x''1

  • (''x''2)2 --- ''x''

  • ''x''2)2 --- ''x''

  • ''x''2)2 --- ''x''

  • ''x'')2)2 --- ''x''       → algorithm needs only 5 multiplications instead of 13 - 1 = 12


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

  • ''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



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.modulo(2) == 1)


    

  •  x

    • 
            n = n-1




        else


    

  • x

    • 
            n = n/2




        end

    end

    return result

end



Runtime example: Compute 310

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
  • 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
  • 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

    • 

  •  x

    • 
  end




  return result

end



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
  • 3 = (32)2---3 = 35 = 243


Iteration for digit 4:
  • 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

  • ''' ) be a Semigroup , that means S is an arbitrary Set

  • 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)'''


  • 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 ) {