mersenneforum.org Max FFT Size?
 Register FAQ Search Today's Posts Mark Forums Read

 2012-04-22, 09:23 #1 aketilander     "Åke Tilander" Apr 2011 Sandviken, Sweden 2×283 Posts Max FFT Size? In the source code of Prime95 ver. 26.6 in the file gwnum.h I find the following lines: #define MAX_PRIME 79300000L /* Maximum number of x87 bits */ #define MAX_PRIME_SSE2 596000000L /* SSE2 bit limit */ #define MAX_FFTLEN 4194304L /* 4M FFT max for x87 */ #define MAX_FFTLEN_SSE2 33554432L /* 32M FFT max for SSE2 */ To the best of my understanding this means that if you have on old computer using an old floating-point utility (X87) the size of the FFTs are limited to 4000K (4194304) and if you have a modern computer using SSE2 the size of the FFTs are limited to 32M (33554432). As a concequence of this you cannot test exponents larger then 73.3M with the X87 computer and not larger then 596M with the modern computer. Question 1: Is the limit of the FFT sizes to 32M due to hardware/software limitations? Or is it just because George have not yet written FFTs for larger sizes (due to obvious reasons)? Question 2: I have tried to find a table of all the FFT sizes used by Prime95, but I have not found one. I would be happy if someone would publish such a table or point me to where I can find one.
 2012-04-22, 10:19 #2 firejuggler     "Vincent" Apr 2010 Over the rainbow 2·1,429 Posts As I understand it, George didn't go beyond 32M because of the non-nessecity-in-my-lifetime prospect. but i could be wrong.
 2012-04-22, 10:56 #3 TheJudger     "Oliver" Mar 2005 Germany 23·139 Posts I *guess* the fastest non SSE2 CPU which can be used for Prime95 is the Athlon Thunderbird (up to 1400MHz) which was released mid 2000! (nearly 12 years old). According to the benchmark page it takes roughly half a second per iteration for a 4M FFT. The max exponent for a 4M X87 FFT in Prime95 is (a prime just below) 79.300.000. So a single test of this size would need roughly 40 million seconds to complete (1 year an three month). I *guess* nobody really needs bigger FFTs for X87, right?
2012-04-22, 11:15   #4
aketilander

"Åke Tilander"
Apr 2011
Sandviken, Sweden

2·283 Posts

Yes TheJudger and firejuggler I fully agree with you. This is what I was referring to when I wrote:

Quote:
 Originally Posted by aketilander "due to obvious reasons"
still I am curious to know if it could be easily done or if there is any hardware/software limitations which cannot easily be overcome?

2012-04-22, 12:00   #5
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

22×13×127 Posts

Quote:
 Originally Posted by aketilander still I am curious to know if it could be easily done or if there is any hardware/software limitations which cannot easily be overcome?
While there are some fundamental limits on the mximum FFT length that a 53-bit mantissa can allow, we are nowhere near such a limit yet. If you want larger FFT length then just start bugging George for it or write it yourself.

Last fiddled with by retina on 2012-04-22 at 12:01

 2012-04-22, 18:58 #6 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
2012-04-22, 19:20   #7
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·3·1,657 Posts

Quote:
 Originally Posted by retina ...If you want larger FFT length then just start bugging George for it or write it yourself.
There was an anecdote (a real one, don't remember the name) about a mathematician who added precisely three footnotes to his manuscript 1. Gratitude to <another person> for translating this manuscript to French; 2. Gratitude to <another person> for translating the above footnote to French; 3. Gratitude to <another person> for translating the above footnote to French. (The 3rd one was simply copied and therefore recurrence was removed.)

I think there's a good chance that someone may need to work enough to understand the existing block structure of George's code (without understanding all the details of the code) and faithfully reproduce it for some higher FFT size, e.g. make 8M code from comparing 2M and 4M code branches, ..or 6M from 3M. In contrast, to create something new (like the 2304K code before George really wrote it) would be much harder.

2012-04-22, 19:58   #8
ewmayer
2ω=0

Sep 2002
República de California

101101111000002 Posts

Quote:
 Originally Posted by Batalov In contrast, to create something new (like the 2304K code before George really wrote it) would be much harder.
Which is why I use the following workaround for that:
Code:
	case 2304 :					/* 2.25M = 2304K */
{
case 0 :
case 1 :
case 2 :
case 3 :
case 4 :
case 5 :
default :
}; break;

2012-04-22, 21:04   #9
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

11111011010002 Posts

Quote:
 Originally Posted by retina If you want larger FFT length then just start bugging George for it or write it yourself.
It is trivial to add AVX FFT lengths up to 50M and SSE2 FFT lengths up to 100M, but why bother?

2012-04-22, 21:19   #10
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

22·13·127 Posts

Quote:
 Originally Posted by Prime95 ... why bother?
I think that no matter how large you make the available lengths there will always be people asking for more. Even when such lengths become a physical impossibility to run on contemporary hardware people would still want more.

2012-04-22, 21:34   #11
aketilander

"Åke Tilander"
Apr 2011
Sandviken, Sweden

23616 Posts
FFTs for Billion digit exponents

Quote:
 Originally Posted by retina If you want larger FFT length then just start bugging George for it or write it yourself.
Quote:
 Originally Posted by Prime95 It is trivial to add AVX FFT lengths up to 50M and SSE2 FFT lengths up to 100M, but why bother?
Well first I will finish the LL (with double check) of my 345M exponent (more then half way through, 5,450 GHz-Days*2), then I may try to LL (with double check) M595999993 (would require more then 3 times as much work that is 16,440 Ghz-Days*2) and IF (a very big IF) I can do it it would be nice to try to LL a billion digit exponent (would require almost 6 times as much work as the 596M exponent that is 91,630 GHz-Days*2).

So if I ever would like to try to LL a Billion digit exponent I would need larger FFTs. Yes I admit its whimsical. With current fastest hardware and the latest versions of Prime95 using AVX I think a LL-test of a Billion digit exponent would not take "more" then 10 years or so. That would at least be within my lifetime I hope.

Last fiddled with by aketilander on 2012-04-22 at 21:49 Reason: Comment could be misunderstood

 Similar Threads Thread Thread Starter Forum Replies Last Post kruoli Software 4 2017-11-17 18:14 edorajh Computer Science & Computational Number Theory 6 2017-03-08 20:28 Sleepy Msieve 14 2011-10-20 10:27 Mini-Geek PrimeNet 8 2007-03-25 07:29 andi314 Lounge 14 2007-01-22 00:21

All times are UTC. The time now is 15:22.

Wed Oct 5 15:22:53 UTC 2022 up 48 days, 12:51, 0 users, load averages: 1.64, 1.66, 1.63