Thread: LL test speed up? View Single Post
2005-09-20, 00:30   #9

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts

Quote:
 Originally Posted by ppo if S is the generic term of the LL sequence and M is the Mersenne number to be tested, when S is bigger than 2^(n-1)
First, I'll assume you mean that the Mersenne number being tested is M = 2^n-1 (so n is the exponent of 2 for that number), and that by "S" you mean one of the S(i) terms mod M.

Quote:
 when S is bigger than 2^(n-1) it is possible to replace it by M-S, so reducing the size of the numer to be squared.
But this reduction in size is trivial. When S(i) is just below 2^n-1, it's only about twice as big as 2^(n-1) -- i.e., one bit longer. Squaring a 12,016,057-bit number is no slower than squaring a 12,016,056-bit number. (The speed jumps come at FFT size boundaries.)

Quote:
 Can this result in speeding-up the test, or it is something already considered?
1) no (well, it could if you could use a smaller FFT by reducing one bit, but that would happen too rarely to be worth the time needed to program the change), and 2) yes.