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:

    “With these I would be.
    And with water: the waves coming forward, without cessation,
    The waves, altered by sand-bars, beds of kelp, miscellaneous
    driftwood,
    Topped by cross-winds, tugged at by sinuous undercurrents
    The tide rustling in, sliding between the ridges of stone,
    The tongues of water, creeping in, quietly.”
    —Theodore Roethke (1908–1963)

    “The knocking out of a pipe can be made almost as important as the smoking of it, especially if there are nervous people in the room. A good, smart knock of a pipe against a tin wastebasket and you will have a neurasthenic out of his chair and into the window sash in no time.”
    —Robert Benchley (1889–1945)

    “Methinks the human method of expression by sound of tongue is very elementary, & ought to be substituted for some ingenious invention which should be able to give vent to at least six coherent sentences at once.”
    —Virginia Woolf (1882–1941)