Thread: Is this a puzzle? View Single Post
2020-08-06, 23:05   #28
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

1,429 Posts

Quote:
 Originally Posted by bsquared Doing the recoding first on our 1442080-bit exponent reduces the number of non-zero bits from to 720737 (one bits) to 480780 (one or minus-one bits). Then doing the sliding window algorithm on the recoded exponent results in 100622 muls (plus precomputation). Those multiplications will range over elements x^b, -2^13 < b < 2^13, b odd.
Checked those 480780, 100622 numbers. Turned out that it is using more multiplications, I counted every mults, and to get the final product from the y[] array you also need mults. I mean this is not that a big surprise, for the old/known powmod problem your signed representation could be a winner, but this is a slightly different problem.
Counted 104979 mults for your method but using E=13, and 106085 for E=12.
[I have 104341 for my method with E=13].

Actually when you first hit a given entry in the y[] array then you can do only a (fast) set and not a mult, so that is smaller than 100622 mults (in my method you can also do this trick). And for the exponents (for E=12) yes it is true that - 2^(E+1)< exponent <2^(E+1) but since in the signed representation you don't see two consectuive non-zero term the sharper inequality holds:
abs(exponent)<=2^E*4/3 (just sum 2^E,2^(E-2),2^(E-4) etc.)
even with these tiny improvements you lost (at least for this given fixed N), but likely in the general case also.