Thread: Is this a puzzle? View Single Post
2020-08-06, 20:18   #25
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

58916 Posts

Quote:
 Originally Posted by bsquared we can just use left-to-right sliding windows to get the number of multiplications down to 102989 plus precomputing 2^12 odd multipliers x^b, 1 <= b < 2^k (b odd), using the (optimal) max window size k=13.
Yes, I've used the popular sliding window name, but here there is no such precomputation here. Yeah it is hard to believe there is such an algorithm, because in that sliding window you are actually doing many squaring, so you could not reach less than log2(N)=b multiplications, that is a complexity barrier here. But as I've written with the given x^(2^e) you can reach ~b/2 multiplications if you are using only the bits=1, what is now lower than the barrier. But there is another type of "precomputation" when in y[k] you're accumulating the products you needed to raise to the k-th power.

To get an inside where I've gotten the idea, when you want to multiple by x^63 with the traditional method you need 6 multiplications but with:

1. multiple x and x^4 to get x^5
2. multiple x^5 and x^16 to get x^21
3. square x^21 to get x^42
4. multiple x^21 and x^42 to get x^63

You need only 5, because you need to multiple the partial product by x^63. But now it is already a gain over the classical method. Found this in my head, without computer, and actually this is the smallest counter-example.
You can do even better multiple by x^64 and divide by x. Using only 3 mults total. Similar to your method.
And here x is NOT fixed, but if you extract those x bases using the given N exponent/residues and see what you need to raise to the k=63 or any power in the window you can save lots of work, what we reached with the optimal E=13.