Alex Kruppa wrote:
> Bruce Leenstra wrote:
>> As luck would have it, this is nearly what I am doing right now:
>> tempvalue = (q+1)/2
>> count = 1
>> while tempvalue != 1 {
>> if tempvalue is odd tempvalue += q
>> shiftright tempvalue > count++
>> }
>> v = count
>I'm not sure I understand that code yet, but
Although it is academic at this point, (your timing of 1+ minutes vs. my timing of 7+
days ),
I arrived at my algorithm by entering the
2^(p+1) mod q = 2*2^p mod q
formula into a spreadsheet so each column was 2^row mod (some prime). Then I found a
formula that would recreate the columns from the bottom up. Notice it does ( /2 and +
q ) vs ( *2 and - q ). My goal was to eliminate the mod step and squeak a little
closer to the dword limit.
I also have a version that checks (mod 4) and combines two passes of the loop so p is
always odd.
Obviously the O(log2(q)) vs. O(q) eclipses any speedup I may have achieved.
However, I am working on your algorithm to address some of the issues Will brought up
. . .
Regards, Bruce
_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
