mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2012-04-22, 09:23   #1
aketilander
 
aketilander's Avatar
 
"Åke Tilander"
Apr 2011
Sandviken, Sweden

2·283 Posts
Question 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.
aketilander is offline   Reply With Quote
Old 2012-04-22, 10:19   #2
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

43×59 Posts
Default

As I understand it, George didn't go beyond 32M because of the non-nessecity-in-my-lifetime prospect. but i could be wrong.
firejuggler is online now   Reply With Quote
Old 2012-04-22, 10:56   #3
TheJudger
 
TheJudger's Avatar
 
"Oliver"
Mar 2005
Germany

11·101 Posts
Default

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?
TheJudger is offline   Reply With Quote
Old 2012-04-22, 11:15   #4
aketilander
 
aketilander's Avatar
 
"Åke Tilander"
Apr 2011
Sandviken, Sweden

2·283 Posts
Smile

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

Quote:
Originally Posted by aketilander View Post
"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?
aketilander is offline   Reply With Quote
Old 2012-04-22, 12:00   #5
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

611310 Posts
Default

Quote:
Originally Posted by aketilander View Post
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
retina is online now   Reply With Quote
Old 2012-04-22, 18:58   #6
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

The FFT table can be found in mult.asm, though when I attempted to read it, ...well, I couldn't. (Also, wouldn't 4M be 4096K?)
Dubslow is offline   Reply With Quote
Old 2012-04-22, 19:20   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

32×7×149 Posts
Default

Quote:
Originally Posted by retina View Post
...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.
Batalov is offline   Reply With Quote
Old 2012-04-22, 19:58   #8
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

3·53·31 Posts
Default

Quote:
Originally Posted by Batalov View Post
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 */
		switch(radix_set)
		{
		case 0 :
			numrad = 6; radix_vec[0] =  9; radix_vec[1] =  8; radix_vec[2] =  8; radix_vec[3] =  8; radix_vec[4] = 16; radix_vec[5] = 16; break;
		case 1 :
			numrad = 5; radix_vec[0] = 18; radix_vec[1] = 16; radix_vec[2] = 16; radix_vec[3] = 16; radix_vec[4] = 16; break;
		case 2 :
			numrad = 5; radix_vec[0] = 36; radix_vec[1] =  8; radix_vec[2] = 16; radix_vec[3] = 16; radix_vec[4] = 16; break;
		case 3 :
			numrad = 5; radix_vec[0] =  9; radix_vec[1] = 16; radix_vec[2] = 16; radix_vec[3] = 16; radix_vec[4] = 32; break;
		case 4 :
			numrad = 5; radix_vec[0] =  9; radix_vec[1] = 16; radix_vec[2] = 16; radix_vec[3] = 32; radix_vec[4] = 16; break;
		case 5 :
			numrad = 4; radix_vec[0] = 36; radix_vec[1] = 32; radix_vec[2] = 32; radix_vec[3] = 32; break;
		default :
			if(nradices){*nradices = 6;}	return ERR_RADIXSET_UNAVAILABLE;
		}; break;
ewmayer is offline   Reply With Quote
Old 2012-04-22, 21:04   #9
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2·3,701 Posts
Default

Quote:
Originally Posted by retina View Post
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?
Prime95 is online now   Reply With Quote
Old 2012-04-22, 21:19   #10
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

6,113 Posts
Default

Quote:
Originally Posted by Prime95 View Post
... 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.
retina is online now   Reply With Quote
Old 2012-04-22, 21:34   #11
aketilander
 
aketilander's Avatar
 
"Åke Tilander"
Apr 2011
Sandviken, Sweden

2·283 Posts
Default FFTs for Billion digit exponents

Quote:
Originally Posted by retina View Post
If you want larger FFT length then just start bugging George for it or write it yourself.
Quote:
Originally Posted by Prime95 View Post
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
aketilander is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Force FFT-size to be used kruoli Software 4 2017-11-17 18:14
Pi(x) value for x at 10^16 size edorajh Computer Science & Computational Number Theory 6 2017-03-08 20:28
Size optimization Sleepy Msieve 14 2011-10-20 10:27
Exponent Size Gap Mini-Geek PrimeNet 8 2007-03-25 07:29
FFT-Size andi314 Lounge 14 2007-01-22 00:21

All times are UTC. The time now is 16:09.

Sun Apr 11 16:09:28 UTC 2021 up 3 days, 10:50, 1 user, load averages: 1.87, 2.00, 1.92

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