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:
“Heaven has a Sea of Glass on which angels go sliding every afternoon. There are many golden streets, but the principal thoroughfares are Amen Street and Hallelujah Avenue, which intersect in front of the Throne. These streets play tunes when walked on, and all shoes have songs in them.”
—For the State of Florida, U.S. public relief program (1935-1943)
“I sometimes have the sense that I live my life as a writer with my nose pressed against the wide, shiny plate glass window of the mainstream culture. The world seems full of straight, large-circulation, slick periodicals which wouldnt think of reviewing my book and bookstores which will never order it.”
—Jan Clausen (b. 1943)
“Women are denied masturbation even more severely than men and thats another method of controltheyre not taught to please themselves.... Most womenit takes them a while to warm up to the situation but once they get into it, Im sure theyre going to get just as hooked aswell, everyone I know is!”
—Lydia Lunch (b. 1959)