mersenneforum.org FFT sizes
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2006-07-11, 09:40 #1 Cruelty     May 2005 22×11×37 Posts FFT sizes 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"
 2006-07-11, 11:05 #2 Kosmaj     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 2006-07-11 at 11:18
2006-07-11, 13:23   #3
Cruelty

May 2005

22·11·37 Posts

Quote:
 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.

Last fiddled with by Cruelty on 2006-07-11 at 13:40

2006-07-12, 15:15   #4
Thomas11

Feb 2003

27×3×5 Posts

Quote:
 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:
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 zero-padded FFT is used or not.
The algorithm used by gwnum is a bit tricky and needs
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...

Last fiddled with by Thomas11 on 2006-07-12 at 15:18

 Similar Threads Thread Thread Starter Forum Replies Last Post TimSorbet Software 7 2008-01-14 17:33 wblipp GMP-ECM 5 2005-04-24 20:04 Dresdenboy Math 2 2003-12-29 22:55 Unregistered Hardware 4 2003-12-06 13:43

All times are UTC. The time now is 13:13.

Sun Jan 29 13:13:10 UTC 2023 up 164 days, 10:41, 0 users, load averages: 0.66, 0.97, 1.31

Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔