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 yNote:
- 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 fountains sliding foot,
Or at some fruit-trees mossy root,
Casting the bodys 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 (16211678)
“A light and diplomatic bird
Is lenient in my window tree.
A quick dilemma of the leaves
Discloses twist and tact to me.”
—Gwendolyn Brooks (b. 1917)
“The method of painting is the natural growth out of a need. I want to express my feelings rather than illustrate them. Technique is just a means of arriving at a statement.... I can control the flow of paint: there is no accident, just as there is no beginning and no end.”
—Jackson Pollock (19121956)