PFGW vs LLR comparison discussion

[Mini-Geek]

Originally Posted by rogue

PFGW has the ability to tell you the FFT length with -V. Maybe Jean has a hidden option or could add one.

As Max said, LLR always tells you the FFT length. No problem there. The problem is easily seeing where the cutoffs are. You can do this for base 2 with the fft_len utility (designed and easy for a single k, not quite so easy for a range of k's, but still quite workable), but (AFAIK) there's no similar thing for other bases.

[mdettweiler]

Originally Posted by Mini-Geek

As Max said, LLR always tells you the FFT length. No problem there. The problem is easily seeing where the cutoffs are. You can do this for base 2 with the fft_len utility (designed and easy for a single k, not quite so easy for a range of k's, but still quite workable), but (AFAIK) there's no similar thing for other bases.

Does fft_len utilize LLR to do the grunt work behind it? If so, then perhaps with some small modifications it would work all right for the new N-1/N+1 tests on other bases.

[Mini-Geek]

Originally Posted by mdettweiler

Does fft_len utilize LLR to do the grunt work behind it? If so, then perhaps with some small modifications it would work all right for the new N-1/N+1 tests on other bases.

No.
http://www.mersenneforum.org/showthr...2302#post62302
I don't know exactly how it works or how to modify it to work for other bases (if possible). These seem to be the critical lines of code: (from llrtools.c; log2k is the base 2 logarithm of k)

  if (k < 1048576)        /* is k < 2^20 ??? */
    nmax = n_mersenne -= (long)(log2k + log2k*(double)(fftlen/2));
  else                    /* zero-padded FFT is used, if k > 2^20 */
    nmax = (long)(((double)n_mersenne + (double)fftlen*0.3)/2.0);

e.g. FFT length 20480 can do a maximum Mersenne n of 423300, (as read from the "maxlen.txt" file) so the max n for k=300 and FFT length=20480 is 423300-(8.23+8.23*10240)=423300-84283=339017 (later decremented to 339016)
(and this is about what the program in fact does return: 339028, the difference probably attributable to my 8.23 estimation)
I don't see anything there that can easily convert to other bases. But that might just be because I don't really know what's going on with that formula and why it's accurate.

[Prime95]

Selecting an FFT length is surprisingly complex. The code is buried in gwnum.c of the 25.13 sources (the key routine is gwinfo). How complex is it? Imagine testing k*b^n+c with k, b, and c constant you could run into a case where n uses one FFT length, increasing n by 1 uses a larger FFT length, but increasing n by 2 is back using the smaller FFT length!

LLR should not be selecting FFT length or maximum n - it should let the gwnum handle these calculations.

In general, base-2 FFTs will always be faster than non-base-2 FFTs for the same FFT length. This is because the rounding and carry propagation code is more complex for non-base-2.

[Jean Penné]

Originally Posted by Prime95

Selecting an FFT length is surprisingly complex. The code is buried in gwnum.c of the 25.13 sources (the key routine is gwinfo). How complex is it? Imagine testing k*b^n+c with k, b, and c constant you could run into a case where n uses one FFT length, increasing n by 1 uses a larger FFT length, but increasing n by 2 is back using the smaller FFT length!

LLR should not be selecting FFT length or maximum n - it should let the gwnum handle these calculations.

In general, base-2 FFTs will always be faster than non-base-2 FFTs for the same FFT length. This is because the rounding and carry propagation code is more complex for non-base-2.

Hi,

All versions of LLR let gwnum calculate the FFT length. I always thought it is the better thing to do !

Best Regards,
Jean