GWNUM issue

[ET_]

I am working with LLR Version 3.8.20, using Gwnum Library Version 28.13 and would like to discuss a somewhat annoying issue (not a real bug).

I am testing double Mersenne numbers' possible factors of the type 2k(2^p-1)+1 using the alternate form 2k*2^p - 2k +1 (k=600,000-2,000,000) using an ABC file like this one:

ABC $a*2^$b+$c
1202106 859433-1202105
1202296 859433-1202295
...
...
3999792 859433-3999791

For the first values the program chooses the following setup:

Starting probable prime test of 1202106*2^859433-1202105
Using zero-padded type-1 FFT length 84K, Pass1=112, Pass2=768, 2 threads, a = 3

While for the last it chooses the following setup:

Starting probable prime test of 3999792*2^859433-3999791
Using generic reduction Pentium4 FFT length 80K, Pass1=320, Pass2=256, 2 threads, a = 3

The second setup is about three times slower.

A similar behaviour has been noticed with pfgw 3.7.10, so I consider it a "feature" of the GWnum library. It seems that somewhere between k = 600,000 and k=2,000,000 a limit is reached that switches the algorithm used to compute the element.

Question (especially to George): is this change in behaviour due to avoid an overflow of a "double" typed variable when the number to be tested grows up? Is it a "safe limit" that can be overridden? If so, how?

Luigi

[Prime95]

This is a feature.

The algorithm for selecting the FFT to test k*b^n+c is gruesomely complex. If you're curious, look at the gwinfo routine in gwnum.c. In short, increasing k and/or c decreases the number of bits I can stuff into an FFT word without getting a roundoff error. If k and c are too big, then it either "can't be done" or "can't be done without rewriting the carry propagation code to spread carries over more FFT words which is just too hard to do and may not even be possible using the current memory layout which would require even more code changes than are worth considering".

There is a gwnum entry called safety_margin which can be used to "be more aggressive", but that would only buy you a few more lines in ABC file.

[ET_]

Originally Posted by Prime95

This is a feature.

The algorithm for selecting the FFT to test k*b^n+c is gruesomely complex. If you're curious, look at the gwinfo routine in gwnum.c. In short, increasing k and/or c decreases the number of bits I can stuff into an FFT word without getting a roundoff error. If k and c are too big, then it either "can't be done" or "can't be done without rewriting the carry propagation code to spread carries over more FFT words which is just too hard to do and may not even be possible using the current memory layout which would require even more code changes than are worth considering".

There is a gwnum entry called safety_margin which can be used to "be more aggressive", but that would only buy you a few more lines in ABC file.

Thank you George.

This means that using the ABC file

ABC 2*$a*(2^859433-1)+1
601053
601148
601149
601205
601293
601296

allowed by pfgw I should be able to gain some more loops of the faster routine thanks to the smaller k? Or, being the number just the same, the behaviour of both pfgw and llr will be just the same?

Luigi

[axn]

Originally Posted by ET_

This means that using the ABC file

ABC 2*$a*(2^859433-1)+1
601053
601148
601149
601205
601293
601296

allowed by pfgw I should be able to gain some more loops of the faster routine thanks to the smaller k? Or, being the number just the same, the behaviour of both pfgw and llr will be just the same?

Luigi

It will be worse! This form [2*k*(2^p-1)+1] is not at all usable for the faster transform, and i don't think PFGW will automatically simplify it to k*2^(p+1)-(2k-1). So your best bet is to give the input in same format as LLR, with the same performance.

[ET_]

Originally Posted by axn

It will be worse! This form [2*k*(2^p-1)+1] is not at all usable for the faster transform, and i don't think PFGW will automatically simplify it to k*2^(p+1)-(2k-1). So your best bet is to give the input in same format as LLR, with the same performance.

Great! Thank you axn.

It looks like after juggling with Mersenne numbers factorization algorithm, I should learn something about LL, Riesel and Sierpinski numbers' primality test theory.