mersenneforum.org  

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

Reply
 
Thread Tools
Old 2011-02-20, 09:35   #1
NBtarheel_33
 
NBtarheel_33's Avatar
 
"Nathan"
Jul 2008
Maryland, USA

5·223 Posts
Question Questions about P-1

I've read the description of the P-1 algorithm at http://www.mersenne.org/various/math.php, but there is no explanation of what the difference is between Stage 1 of P-1 and Stage 2 of P-1 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 P-1 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 "Brent-Suyama Extension" of P-1 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 P-1 finding a factor? How much RAM does one need before this extension becomes feasible?

Enlightenment from the P-1 crowd is much appreciated!
NBtarheel_33 is offline   Reply With Quote
Old 2011-02-20, 13:13   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by NBtarheel_33 View Post
Also, in Stage 2, I've seen Prime95 display messages about processing "relative primes". What does this mean?
http://www.google.ca/search?sourceid...ively+prime%22

Last fiddled with by science_man_88 on 2011-02-20 at 13:13
science_man_88 is offline   Reply With Quote
Old 2011-02-20, 13:49   #3
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

I'm afraid I don't know too much myself, but this page has some more detail on P-1, 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 Mini-Geek on 2011-02-20 at 13:49
Mini-Geek is offline   Reply With Quote
Old 2011-02-21, 22:51   #4
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·641 Posts
Default

Quote:
Originally Posted by NBtarheel_33 View Post
I've read the description of the P-1 algorithm at http://www.mersenne.org/various/math.php, but there is no explanation of what the difference is between Stage 1 of P-1 and Stage 2 of P-1 that makes Stage 2 require so much more memory.
Stage 2 involves repeated multiplications by powers of a certain set of numbers. To save time, it allocates as many work areas as it can to hold certain intermediate calculated powers and products that will be repeatedly used, so that each need be calculated only once. The more work areas it can allocate, the more time it can save by using singly-calculated intermediate products.

So, it's not so much a matter of Stage 2's requiring lots of memory as it is a matter of a classic space-time tradeoff that saves significant time if Stage 2 can allocate many work areas.

Quote:
Also, in Stage 2, I've seen Prime95 display messages about processing "relative primes".
Without saying anything about the math:

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:
Finally, I've heard of users with lots of RAM performing a "Brent-Suyama Extension" of P-1 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 P-1 finding a factor? How much RAM does one need before this extension becomes feasible?
The Brent-Suyama extension (by mathematicians Brent and Suyama, not to be confused with the person Mr. Brent Suyama who's not a mathematician) involves yet still more multiplications (* surprise, surprise *) that are worthwhile only when still more work areas (* surprise, surprise *) can be allocated to hold singly-calculated intermediate products.

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 2011-02-21 at 23:46
cheesehead is offline   Reply With Quote
Old 2011-02-21, 23:23   #5
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7×167 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
I'm afraid I don't know too much myself, but this page has some more detail on P-1, 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
The mersennewiki page describes a plan for stage two which includes primes 6*j +/-1 for successive values of j. This plan does not require much memory. Prime95 uses a plan which includes primes d*j +/- i for d a small multiple of a small primorial chosen dependent upon the available memory, and for i relatively prime to d.

See post #29 in this thread, and subsequent discussion.

Last fiddled with by Mr. P-1 on 2011-02-22 at 00:22
Mr. P-1 is offline   Reply With Quote
Old 2011-02-21, 23:44   #6
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7·167 Posts
Default

Quote:
Originally Posted by NBtarheel_33 View Post
I've read the description of the P-1 algorithm at http://www.mersenne.org/various/math.php, but there is no explanation of what the difference is between Stage 1 of P-1 and Stage 2 of P-1 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 P-1 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?
Not really. In stage 1 you compute 3^E - 1. In stage 2 you compute (3^(E*q1)-1)*(3^(E*q2)-1)*(3^(E*q3)-1)*... where the qi are all primes between B1 and B2. This product is not "larger" than the result of the stage 1 computation, because all calculations are done mod N.

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:
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?
See the post I linked to in my reply to Mini-Geek.

Quote:
Finally, I've heard of users with lots of RAM performing a "Brent-Suyama Extension" of P-1 with a value of E, where E is something like 6, 8, or 12. What exactly is this,...
See the description from the GMP-ECM readme file in the linked post.

Quote:
...and how much more does it increase the chances of P-1 finding a factor?
A little, but not much. Basically the extension throws in additional primes above the B2 limit for a little extra computation. The benefit is marginal.

Quote:
How much RAM does one need before this extension becomes feasible?
It's feasible without a huge amount of memory. However, unless you do have a huge amount of memory, its usually better to use the memory you do have to enable more relative primes per pass.

Last fiddled with by Mr. P-1 on 2011-02-22 at 00:23
Mr. P-1 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Two questions: Dubslow GPU Computing 1 2011-08-05 18:22
Questions about the QS Carmichael Factoring 8 2007-04-10 11:30
Questions OmbooHankvald Prime Sierpinski Project 2 2005-08-01 20:18
LLR questions OmbooHankvald Math 6 2005-06-23 11:42
A few questions :) xtreme2k Lounge 59 2002-10-31 06:20

All times are UTC. The time now is 11:03.

Fri Apr 23 11:03:58 UTC 2021 up 15 days, 5:44, 0 users, load averages: 1.62, 1.70, 1.64

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.