Question about Prime95

Warlord · 2013-09-29, 15:41

So I have been looking through the helpfile and basically been scouring the internet for this but I can't seem to find an answer. Why doesn't Prime95 use base files?

I expected that it would generate files to continue working to save CPU time. So for example every 1.000.000 iterations make a file that a future computation can use to start from. As an example: my current assignment is M64803829, my previous assignment was M65999761. Now since 2^50.000.000 will always have the exact same result, you'd expect that the program will save such a file as it is computationally huge but storage-wise not actually that big (~20MB uncompressed). To make my point on it not being that big: my current computer has 1Tbyte of disk space on the regular HDD and another 250GB on my SSD and as such: disk space is not an issue and surely other people who participate in this project have comparable disk sizes or even bigger. But it doesn't seem to make launch points. Am I missing a setting to allow that because that does make a whole lot more sense to me as it will save you millions of iterations and therefor a lot of time.

TheJudger · 2013-09-29, 16:52

Reading 2^50.000.000 from disk would take much longer than just creating this in memory, in binary it is a one followed by 50.000.000 zeros.
The LL algorithm does S_n+1 = (S_n²-2) mod 2^exp-1. S₀ = 4, calculate S_exp-2 now. If you remove the modular part (which is different for each mersenne number) and ignore the -2 than we have 2^{2[SUP]50.000.000}[/SUP] which is much, much, much more than 1TB (an still easier to create since it is just an other power of two). The final modular division would take much, much, much longer compared to the ways GIMPS (LL test) works.

Oliver

TheMawn · 2013-09-29, 20:41

The algorithm starts with four. You square it and then subtract two. That's one iteration, and you do two less iterations than the number of exponents (i.e. P-2 iterations). The modulo function is added because that number is getting square over and over again. By taking the modulus of M_P you're keeping the entirety of the calculation to less than 2P bits. Every time you square the number, you double the number of bits. You start with a four bit number, then eight, then sixteen, so as Oliver said, you WOULD end up with a number that is M_P bits. Remember M_P is over 20,000,000 digits long in some of the tests we're currently working on. A Terabyte is a twelve digit long number of bits.

You're absolutely correct about the theoretical possibility of not repeating our work. If we didn't need to do the modulus thing (it's entirely for the sake of faster computations (also storage capacity); it is not necessary to the algorithm in a mathematical sense), we could do one big modulo calculation every time we pass by a candidate exponent and save ourselves the trouble of climbing all the way back up every time, but it's just not possible.

You would have to save 2^60,000,000 bits and there are about 2²⁴⁰ electrons in the known universe.

Brian-E · 2013-09-29, 20:56

And in case TheJudger's and TheMawn's explanations still leave any confusion about what's going on, it's beautifully explained here:
http://www.mersennewiki.org/index.ph...le_Explanation

only_human · 2013-09-29, 21:28

Quote:

Originally Posted by TheMawn

The modulo function is added because that number is getting square over and over again. By taking the modulus of M_P you're keeping the entirety of the calculation to ~~less than 2~~P bits.

P bits.

TheMawn · 2013-09-29, 23:58

Quote:

Originally Posted by only_human

P bits.

We could argue on the technicalities, because you might have M_P-1 leftover after the Modulo and then you go and square it after that. Hence "less than" 2P bits. But yes, after the modulo there are always P or less bits.

only_human · 2013-09-30, 00:17

True - pedantic of me and not a clear distinction. Also if you store an iteration on disk, you need the P bits plus lg P bits to store an iteration count, so again more than P. So either accounting for the 2P bits that exist briefly after squaring, or the lg P bits to keep an iteration count, P bits alone is not sufficient.

2013-09-29, 15:41	#1
Warlord "Cas Wegkamp" Sep 2013 The Netherlands 2² Posts	Question about Prime95 So I have been looking through the helpfile and basically been scouring the internet for this but I can't seem to find an answer. Why doesn't Prime95 use base files? I expected that it would generate files to continue working to save CPU time. So for example every 1.000.000 iterations make a file that a future computation can use to start from. As an example: my current assignment is M64803829, my previous assignment was M65999761. Now since 2^50.000.000 will always have the exact same result, you'd expect that the program will save such a file as it is computationally huge but storage-wise not actually that big (~20MB uncompressed). To make my point on it not being that big: my current computer has 1Tbyte of disk space on the regular HDD and another 250GB on my SSD and as such: disk space is not an issue and surely other people who participate in this project have comparable disk sizes or even bigger. But it doesn't seem to make launch points. Am I missing a setting to allow that because that does make a whole lot more sense to me as it will save you millions of iterations and therefor a lot of time.

2013-09-29, 20:41	#3
TheMawn May 2013 East. Always East. 11×157 Posts	The algorithm starts with four. You square it and then subtract two. That's one iteration, and you do two less iterations than the number of exponents (i.e. P-2 iterations). The modulo function is added because that number is getting square over and over again. By taking the modulus of M_P you're keeping the entirety of the calculation to less than 2P bits. Every time you square the number, you double the number of bits. You start with a four bit number, then eight, then sixteen, so as Oliver said, you WOULD end up with a number that is M_P bits. Remember M_P is over 20,000,000 digits long in some of the tests we're currently working on. A Terabyte is a twelve digit long number of bits. You're absolutely correct about the theoretical possibility of not repeating our work. If we didn't need to do the modulus thing (it's entirely for the sake of faster computations (also storage capacity); it is not necessary to the algorithm in a mathematical sense), we could do one big modulo calculation every time we pass by a candidate exponent and save ourselves the trouble of climbing all the way back up every time, but it's just not possible. You would have to save 2^60,000,000 bits and there are about 2²⁴⁰ electrons in the known universe. Last fiddled with by TheMawn on 2013-09-29 at 20:43 Reason: Forgot to finish a sentence.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Prime95 - hours per day question	Przem	Information & Answers	3	2015-10-06 15:16
prime95 software question	crash893	Software	8	2010-12-12 22:31
Prime95 benchmark question	Builder	Information & Answers	2	2009-10-25 20:43
Question about Prime95 24.12 Problem???	VJS	Software	8	2005-06-24 18:23
Simple question on Prime95	xtreme2k	Software	4	2003-04-02 08:35

2013-09-29, 16:52	#2
TheJudger "Oliver" Mar 2005 Germany 2132₈ Posts	Reading 2^50.000.000 from disk would take much longer than just creating this in memory, in binary it is a one followed by 50.000.000 zeros. The LL algorithm does S_n+1 = (S_n²-2) mod 2^exp-1. S₀ = 4, calculate S_exp-2 now. If you remove the modular part (which is different for each mersenne number) and ignore the -2 than we have 2^{2[SUP]50.000.000}[/SUP] which is much, much, much more than 1TB (an still easier to create since it is just an other power of two). The final modular division would take much, much, much longer compared to the ways GIMPS (LL test) works. Oliver

2013-09-29, 20:56	#4
Brian-E "Brian" Jul 2007 The Netherlands 2·11·149 Posts	And in case TheJudger's and TheMawn's explanations still leave any confusion about what's going on, it's beautifully explained here: http://www.mersennewiki.org/index.ph...le_Explanation

2013-09-30, 00:17	#7
only_human "Gang aft agley" Sep 2002 7252₈ Posts	True - pedantic of me and not a clear distinction. Also if you store an iteration on disk, you need the P bits plus lg P bits to store an iteration count, so again more than P. So either accounting for the 2P bits that exist briefly after squaring, or the lg P bits to keep an iteration count, P bits alone is not sufficient.