Navigation
  • Home
  • Recent
  • Most Active
  • Popular
  • Blog
  • Credits
  • RSS
    		•
      Interaction
  • Register
  • Statistics
    		•
      Help
  • Suggestions
  • Contact Us
  • How to Edit
  • Help
    		•



    [Edit]


    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.
        Exponentiation by squaring
            Squaring algorithm
            Further applications
                Computation by powers of 2
                    Runtime example: Compute 3
                Runtime example: Compute 3
                    Generalization
                    Text application
                Calculation of products of powers
                    Example
                    Using transformation
                    Examples
                    Implementation
            Alternatives

    top

    Squaring algorithm

    The following recursive algorithm computes xn for a positive integer n:


    mbox(x,,n)=
    egin x, & mboxnmbox \
    mbox(x^2,,n/2), & mboxnmbox \
    x imesmbox(x^2,,(n-1)/2), & mboxn >mbox
    end


    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 xn 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.)

    top

    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
    x13 = x1101bin

    = x(1
      2^3 + 1
        2^2 + 0
          2^1 + 1
            2^0)
    = x1
      2^3
        x1
          2^2
            x0
              2^1
                x1
                  2^0
    = x2^3
      x2^2
        1
          x2^0
    = x8
      x4
        x1
    = (x4)2
      (x2)2
        x
    = (x4
      x2)2
        x
    = ((x2)2
      x2)2
        x
    = ((x2
      x)2)2
        x       → algorithm needs only 5 multiplications instead of 13 - 1 = 12

    Some more examples:
      x10 = ((x2)2
        x)2 because 10 = (1,010)2 = 23+21, algorithm needs 4 multiplications instead of 9
      x100 = (((((x2
        x)2)2)2
          x)2)2 because 100 = (1,100,100)2 = 26+25+22, algorithm needs 8 multiplications instead of 99
      x1,000 = ((((((((x2
        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
      x1,000,000 = ((((((((((((((((((x2
        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
      x1,000,000,000 = ((((((((((((((((((((((((((((x2
        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

    top

    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.nonzero?
    if n.modulo(2).nonzero?
    result = result
      x
    n = n-1
    else
    x = x
      x
    n = n/2
    end
    end
    return result
    end

    top

    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

    top

    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

    top

    Generalization
    Let the pair ( S, and
      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.

    top

    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 )
    The call repeat ( 'Abc', 6 ) returns the string AbcAbcAbcAbcAbcAbc

    top

    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.

    top

    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×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:
    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 the
    count of multiplications iff at least two of the exponents are greater than 1.

    top

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

    a7×b5 = a2×ab5 with ab
    = a×b


    ab
    = a×b (one multiplication)

    a2×ab5 = ((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 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.

    top

    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 )

    top

    Implementation
    // the following javascript function calculates
    // Bas 0 ^ Exp 0 x Bas 1 ^ Exp 1 x ...
    function productOfPowers_simpleVersion ( Bas , Exp )
    //
    // for the following function input has to be sorted:
    // Exp 0 >= Exp 1 >= ...
    function productOfPowers_withTransformation ( Bas , Exp )
    // 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

    top

    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.
     
    Search more:
     

       
    Source Privacy License Download Contact Us Atlas
    Scientus.org Dictionary (Yet Another Wiki) RC : 1.39
    This article is licensed under the GNU Free Documentation License [copyleft]. It uses material from the Wikipedia article "Exponentiation by squaring". link