mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Riesel Prime Search

Reply
 
Thread Tools
Old 2006-07-11, 09:40   #1
Cruelty
 
Cruelty's Avatar
 
May 2005

22·11·37 Posts
Default 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"
Cruelty is offline   Reply With Quote
Old 2006-07-11, 11:05   #2
Kosmaj
 
Kosmaj's Avatar
 
Nov 2003

2·1,811 Posts
Default

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
Kosmaj is offline   Reply With Quote
Old 2006-07-11, 13:23   #3
Cruelty
 
Cruelty's Avatar
 
May 2005

22×11×37 Posts
Default

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
Cruelty is offline   Reply With Quote
Old 2006-07-12, 15:15   #4
Thomas11
 
Thomas11's Avatar
 
Feb 2003

27×3×5 Posts
Default

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

Last fiddled with by Thomas11 on 2006-07-12 at 15:18
Thomas11 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Variable FFT sizes Mini-Geek Software 7 2008-01-14 17:33
How Much Memory at Various Sizes? wblipp GMP-ECM 5 2005-04-24 20:04
Different word sizes/accuracy for forward/inverse transform? Dresdenboy Math 2 2003-12-29 22:55
Cache Sizes Unregistered Hardware 4 2003-12-06 13:43

All times are UTC. The time now is 17:38.


Thu Dec 8 17:38:01 UTC 2022 up 112 days, 15:06, 0 users, load averages: 0.91, 0.85, 0.96

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

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