Exponentiation By Squaring - Sliding Window Method

Sliding Window Method

This method is an efficient variant of the 2k-ary method. For example, to calculate the exponent 398 which has binary expansion (110 001 110)2, we take a window of length 3 using the 2k-ary method algorithm we calculate 1,x3,x6,x12,x24,x48,x49,x98,x99,x198,x199,x398. But, we can also compute 1,x3,x6,x12,x24,x48,x96,x192,x199, x398 which saves one multiplication and amounts to evaluating (110 001 110)n2

Here is the general algorithm:

Algorithm:

Input
An element 'x' of 'G',a non negative integer n=(nl,nl-1,...,n0)2, a parameter k>0 and the pre-computed values x3,x5,....
Output
The element xn in G

Algorithm:

1. y := 1 and i := l-1 2. while i > -1 do 3. if ni=0 then y:=y2 and i:=i-1 4. else 5. s:=max{i-k+1,0} 6. while ns=0 do s:=s+1 7. for h:=1 to i-s+1 do y:=y2 8. u:=(ni,ni-1,....,ns)2 9. y:=y*xu 10. i:=s-1 11. return y

Note:

  1. In line 6 the loop finds the longest string of length less than or equal to 'k' which ends in a non zero value. Also not all odd powers of 2 up to need be computed and only those specifically involved in the computation need be considered.

Read more about this topic:  Exponentiation By Squaring

Famous quotes containing the words sliding, window and/or method:

    “Here at the fountain’s sliding foot,
    Or at some fruit-tree’s mossy root,
    Casting the body’s vest aside,
    My soul into the boughs does glide:
    There, like a bird, it sits and sings,
    Then whets and combs its silver wings,
    And, till prepared for longer flights,
    Waves in its plumes the various light.”
    —Andrew Marvell (1621–1678)

    “Loach: What happened to your nose, Gittes? Somebody slam a bedroom window on it?
    J.J. Gittes: Nope, your wife got excited. She crossed her legs a little too quick.”
    —Robert Towne (b. 1936)

    “Relying on any one disciplinary approach—time-out, negotiation, tough love, the star system—puts the parenting team at risk. Why? Because children adapt to any method very quickly; today’s effective technique becomes tomorrow’s worn dance.”
    —Ron Taffel (20th century)