20060711, 09:40  #1 
May 2005
2^{2}×11×37 Posts 
FFT sizes
How to calculate FFTsize shift for given "k" for both SSE2 and nonSSE2 CPUs? I would like to "predict" at what "n", LLR test will "slow down"

20060711, 11:05  #2 
Nov 2003
2×1,811 Posts 
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. Last fiddled with by Kosmaj on 20060711 at 11:18 
20060711, 13:23  #3  
May 2005
2^{2}·11·37 Posts 
Quote:
BTW: I've found what I was looking for here. Last fiddled with by Cruelty on 20060711 at 13:40 

20060712, 15:15  #4  
Feb 2003
2^{7}×3×5 Posts 
Quote:
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: Code:
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 zeropadded 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 zeropadding for k > 2^20. This might be wrong for a few cases in the range k = 11.3M */ if (k < 1048576) /* is k < 2^20 ??? */ nmax = n_mersenne  (long)(log2k + log2k*(double)(fftlen/2)); else /* zeropadded 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); } Last fiddled with by Thomas11 on 20060712 at 15:18 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Variable FFT sizes  TimSorbet  Software  7  20080114 17:33 
How Much Memory at Various Sizes?  wblipp  GMPECM  5  20050424 20:04 
Different word sizes/accuracy for forward/inverse transform?  Dresdenboy  Math  2  20031229 22:55 
Cache Sizes  Unregistered  Hardware  4  20031206 13:43 