20110220, 09:35  #1 
"Nathan"
Jul 2008
Maryland, USA
5·223 Posts 
Questions about P1
I've read the description of the P1 algorithm at http://www.mersenne.org/various/math.php, but there is no explanation of what the difference is between Stage 1 of P1 and Stage 2 of P1 that makes Stage 2 require so much more memory. My guess is that the same calculation is being performed in both stages, but there are many more primes to be included in the product E in Stage 2, and that the extra memory is used to hold these extra primes. I'm also guessing that the reason the save files for a P1 double in size between Stages 1 and 2 is because of the (much) larger product that is being formed in Stage 2. Is that the right idea?
Also, in Stage 2, I've seen Prime95 display messages about processing "relative primes". What does this mean? Are these numbers that are relatively prime to one another? Typically, there is some number of relative primes  e.g. 480  that are getting processed; are these selected out of the primes that lie between B1 and B2? And if so, how does Prime95 decide which primes get selected? Finally, I've heard of users with lots of RAM performing a "BrentSuyama Extension" of P1 with a value of E, where E is something like 6, 8, or 12. What exactly is this, and how much more does it increase the chances of P1 finding a factor? How much RAM does one need before this extension becomes feasible? Enlightenment from the P1 crowd is much appreciated! 
20110220, 13:13  #2  
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
Quote:
Last fiddled with by science_man_88 on 20110220 at 13:13 

20110220, 13:49  #3 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17·251 Posts 
I'm afraid I don't know too much myself, but this page has some more detail on P1, including the best explanation of stage 2 I can find on the web (though I'm still not clear on why stage 2 needs lots of memory, if I were to work out an example using the math there, I'd probably see).
http://mersennewiki.org/index.php/P...ization_Method Last fiddled with by MiniGeek on 20110220 at 13:49 
20110221, 22:51  #4  
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·641 Posts 
Quote:
So, it's not so much a matter of Stage 2's requiring lots of memory as it is a matter of a classic spacetime tradeoff that saves significant time if Stage 2 can allocate many work areas. Quote:
The number of work areas allocated limits the number of relative primes that can be processed in a single pass. For instance, for a certain allocation amount Stage 2 will process 40 relative primes (out of 480) in each of 12 passes. With slightly larger allocations it will process 41, 42, or 43 relative primes in each pass, but there will still be 12 passes (43 * 11 = 473, so a twelfth pass is required for the last 7 relative primes). If the allocation allows processing 44 relative primes in each pass, the number of required passes declines to 11 (44*10 + 40*1 = 480), which will be faster. Quote:
There's some formula for determining when the tradeoff (for increased probability of finding a factor) is worth the extra effort or not, but I can't find it handily right now. One could look at the source code (probably module ecm.c) to find it. :) Last fiddled with by cheesehead on 20110221 at 23:46 

20110221, 23:23  #5  
Jun 2003
7×167 Posts 
Quote:
See post #29 in this thread, and subsequent discussion. Last fiddled with by Mr. P1 on 20110222 at 00:22 

20110221, 23:44  #6  
Jun 2003
7·167 Posts 
Quote:
The save file is larger, not because the numbers are larger, but because you need to save more of them, including the current running value of the stage 2 product, the last term that was multiplied into it and the original result of stage 1. Quote:
Quote:
Quote:
Quote:
Last fiddled with by Mr. P1 on 20110222 at 00:23 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Two questions:  Dubslow  GPU Computing  1  20110805 18:22 
Questions about the QS  Carmichael  Factoring  8  20070410 11:30 
Questions  OmbooHankvald  Prime Sierpinski Project  2  20050801 20:18 
LLR questions  OmbooHankvald  Math  6  20050623 11:42 
A few questions :)  xtreme2k  Lounge  59  20021031 06:20 