FFT sizes

[Cruelty]

How to calculate FFT-size shift for given "k" for both SSE2 and non-SSE2 CPUs? I would like to "predict" at what "n", LLR test will "slow down"

[Kosmaj]

Thomas had a formula, or a short program (?) that could answer your question. I tried to find it but in vain. I hope Thomas will appear and reply to your question soon.

BTW, does anybody have any clues how the "Search" function works on MersenneForum?? Trying to search for posts by "Thomas11" with keyword=LLR returns nothing, although there are several such posts.

[Cruelty]

Originally Posted by Kosmaj

BTW, does anybody have any clues how the "Search" function works on MersenneForum?? Trying to search for posts by "Thomas11" with keyword=LLR returns nothing, although there are several such posts.

Some time ago, searching for such a short "phrase" as "llr" was not allowed - maybe it is still the case?

BTW: I've found what I was looking for here.

[Thomas11]

Originally Posted by Cruelty

BTW: I've found what I was looking for here.

That's the right one. It's based on the LLR 3.6 code, but as far as I know all newer versions use the same FFT lengths.
It works for PRP too (George's PRP as well as the "Proth" mode of LLR) -- simply exchange the maxlen.txt file (into the "proth" one).

This is the "whole" algorithm:

long nmax_from_fftlen(long k, long fftlen, long n_mersenne)
/* find the max. allowed n for given k and fftlen */
/* n_mersenne is the max. allowed n for a Mersenne test */
/* This is adapted from George Woltmans gwnum v24.14 */
{
  long nmax;
  double log2k;
  log2k = log((double) k) / log(2.0);
                                                                                
/* We need to decide whether zero-padded FFT is used or not.
   The algorithm used by gwnum is a bit tricky and needs
   more information than we already have here.
   For simplicity we assume zero-padding for k > 2^20.
   This might be wrong for a few cases in the range k = 1-1.3M */
                                                                                
  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);
                                                                                
  nmax--;                 /* decrement nmax by one */
  return (nmax);
}

Please note that it gives "exact" nmax values only for the non-zero-padded FFTs (e.g. for k smaller than 2^20). For the zero-padded FFTs the GWNUM algorithm is much more sophisticated -- so I implimented only an approximate one for k>2^20. Nevertheless it works quite well and the predicted and the real switching points differ not very much -- at least for the tests I did...