View Single Post
Old 2005-09-20, 00:30   #9
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts
Default

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.
cheesehead is offline   Reply With Quote