mersenneforum.org  

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

Reply
 
Thread Tools
Old 2009-07-15, 06:15   #1
markr
 
markr's Avatar
 
"Mark"
Feb 2003
Sydney

23D16 Posts
Default P-1 on small exponents

Okay, I'm after some comments and advice here, folks. I've been occasionally playing around with P-1 on small exponents that were only done to low bounds. So far this looks better than ECM on these exponents. Certainly it's much better credit/day on my old P4 1.7GHz currently doing this. I'm convinced it can be better factors/day too, which is after all the main objective. For example, my latest efforts have so far yielded 9 factors from 219 attempts. I think that's a good rate - it's a little higher than I expected.*

The PrimeNet summary shows P-1 assignments on small exponents (some are mine), so the future PM1-S worktype is allowed for, and I wouldn't be surprised to find I'm going over ground that is already well surveyed & charted. I have a tendency to ramble on a bit, too, which I'll try to curb.

Questions! What are reasonable bounds to use, when there isn't the constraint to maximize project throughput? Is is as simple as trying to maximize factors per time spent?

What are "inadequate" previous bounds, to select candidates to work with? So far I've simply gone with the smallest exponents with B1 & B2 both less than a low limit like 100000. This provides lots of candidates, but eventually the low-hanging fruit will be done. Maybe estimated probability of P-1 finding a factor with the previous bounds?

One thing I'd like is to be able to put a Pminus1 line or similar with specified B1 & B2 in worktodo.txt to request an exponent - currently Pminus1 lines in worktodo.txt give "unsupported assignment work type", so I have to use slightly-faked Pfactor lines to get the assignment & then change them. Maybe there's already a way? I'm constantly learning new things about the v5 server! Anyway, I'm very patient - whenever George & Scott implement PM1-S will be fine.

I must apologise in advance: I may not be able to respond here much for the next couple weeks, as I'll be travelling. I'll try to look in when I can get the chance, as I'm looking forward to your replies.

Some details... Most of the 219 attempts I mentioned were in the 1.4M range, had been TFd to 61 bits, had P-1 with B1=B2=50000, and had 6 or more ECM curves done. I chose B1=200000, B2=5000000 - partly by playing with the Mersenne-aries P-1 probability calculator, and partly because each test took the venerable P4 1.7 about an hour.


* I think Murphy has invoked the Law of Small Numbers to pay me back for not bothering to dig out old results. Previously I'd done some of this manually, trying to stay ahead of the ECM assignments, and despite a couple runs of a hundred or more between factors, overall my recollection is a range of roughly 2-4% factored, which I was happy with. My experience with ECM has been less fortunate - after many curves, one factor. What is the probability of a factor with a single ECM curve, anyway?
markr is offline   Reply With Quote
Old 2009-07-15, 11:27   #2
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

22×691 Posts
Default

Quote:
What are reasonable bounds to use, when there isn't the constraint to maximize project throughput? Is it as simple as trying to maximize factors per time spent?
If your objective is to find factors, I would say yes this would be the way to go.

Quote:
What are "inadequate" previous bounds, to select candidates to work with? So far I've simply gone with the smallest exponents with B1 & B2 both less than a low limit like 100000. This provides lots of candidates, but eventually the low-hanging fruit will be done. Maybe estimated probability of P-1 finding a factor with the previous bounds?
Yes. Use the excellent mersennaries calculator to calculate automatic bounds and choose exponents that are below the 1 or 2 test bounds - your choice. I wouldn't bother doing P-1 on exponents where the test already performed had a chance of finding a factor greater than 50% of the chance of the test using bounds you are going to use.

Last fiddled with by garo on 2009-07-15 at 11:29
garo is offline   Reply With Quote
Old 2009-07-15, 11:34   #3
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

22×691 Posts
Default

Just a couple of additional comments.

The really low hanging fruit was picked by our forum admin several years ago.

GIMPS is desperately short of people to do P-1 at the leading edge of LL. A majority of exponents being LL tested are not getting project optimal P-1 testing. Would you consider doing this more project-critical work instead? I know the P-IV is slow but it should get a P-1 test out in 10 days.
garo is offline   Reply With Quote
Old 2009-07-15, 17:01   #4
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

1DD016 Posts
Default

IMO, if you enjoy finding factors do P-1 on small exponents. Choose B2 as roughly 20*B1 so that it spends an equal amount of time in stage 1 and stage 2.

I'd say that P-1 and double-checking are both short-handed. TF definitely has too many CPUs.

"Do what makes the most sense" allows me to change the server's rules for handing out assignments, which I may do someday. At present, I'm inclined to let first-time LL testers do the P-1 testing that those dedicated solely to P-1 don't get to. Yeah, the LL testers may not have enough memory to run stage 2, so we won't find quite as many factors. Another choice would be to divert "do what makes the most sense" machines with lots of memory to P-1 half-time or full-time -- and I think P-1 would still fall behind the LL testers. I'd probably define "lots of memory" as 400 or 500 MB/core.
Prime95 is online now   Reply With Quote
Old 2009-07-15, 17:43   #5
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

433 Posts
Default

Quote:
Originally Posted by garo View Post
GIMPS is desperately short of people to do P-1 at the leading edge of LL. A majority of exponents being LL tested are not getting project optimal P-1 testing. Would you consider doing this more project-critical work instead? I know the P-IV is slow but it should get a P-1 test out in 10 days.
My 2.0GHZ PIV can kick out a P-1 test in a little under 4 days, so I'd expect something closer to 6 days.
Kevin is offline   Reply With Quote
Old 2009-07-16, 00:24   #6
markr
 
markr's Avatar
 
"Mark"
Feb 2003
Sydney

3×191 Posts
Default

Quote:
Originally Posted by garo View Post
GIMPS is desperately short of people to do P-1 at the leading edge of LL. A majority of exponents being LL tested are not getting project optimal P-1 testing. Would you consider doing this more project-critical work instead? I know the P-IV is slow but it should get a P-1 test out in 10 days.
Just over 6 days (Kevin's estimate was spot on); I've given it one to see how long it takes in practice.

Originally this machine only had 512MB RAM, so P-1 on large exponents was out, and I set it doing double-checks, which was good until the 18M & 19M ranges ran out. These days, if I set it to "what make sense" the server won't give it double-checks, as it only has 256KB L2 cache (so no exponent over 20M). So when I increased its RAM a few weeks ago, I assumed even larger FFT sizes would be no good. But it looks like the credit/day is about the same for PM1-S & PM1-L*. Now I'm torn between them!

Thanks for the helpful replies, garo & everyone.


* Credit/day for this machine is highest for TF from 2^62 to 2^64. Next best is LL tests below 20M.
markr is offline   Reply With Quote
Old 2009-07-16, 00:31   #7
markr
 
markr's Avatar
 
"Mark"
Feb 2003
Sydney

10758 Posts
Default

Correction and update: 13 factors from 240 attempts!

I missed 3 factor-results because they were manually submitted and showed as F-ECM instead of F-PM1 in the results page.
markr is offline   Reply With Quote
Old 2009-07-16, 10:21   #8
garo
 
garo's Avatar
 
Aug 2002
Termonfeckin, IE

22×691 Posts
Default

I moved posts related to the discussion on GIMPS's shortage of P-1 testers to this thread:
http://www.mersenneforum.org/showthread.php?p=181114#post181114

Last fiddled with by garo on 2009-07-16 at 10:24
garo is offline   Reply With Quote
Old 2009-08-02, 12:28   #9
harlee
 
harlee's Avatar
 
Sep 2006
Odenton, MD, USA

22·41 Posts
Default

Quote:
Originally Posted by Prime95 View Post
IMO, if you enjoy finding factors do P-1 on small exponents. Choose B2 as roughly 20*B1 so that it spends an equal amount of time in stage 1 and stage 2.
I doing P-1 work in the 2M and some in the 5M range with 25.11 and noticed a couple of things. First, for 2M exponents, the B2 is B1*13 and for 5M exponents it is B1*16.5 then B1*17.5. Why isn't it B1*20 like Prime95 suggested?

Code:
UID: harlee/P4_2600, M2114467 completed P-1, B1=20000, B2=260000, Wd1: 36D6140E, AID: 228B7C6B08AC54101A132C630C7727EA
UID: harlee/P4_2600, M5052589 completed P-1, B1=55000, B2=907500, E=6, Wd1: 82D06CAF, AID: D202551ED26816B6776F748E8C0671FF
UID: harlee/P4_2600, M5052767 completed P-1, B1=60000, B2=1065000, E=6, Wd1: 82C7E9FD, AID: EC2640F9F03CBCB5C85C309637D1E220
[Tue Jul 28 15:34:01 2009]
Second, I seem to recall reading the output E=6 has a special meaning, can't seem to find it. Anyway, probably due to the small B1 & B2 settings the 2M exponents are not getting that by default. The is plenty of memory allocated for P-1 stage 2 (1.5GB) to use so that isn't an issue.
harlee is offline   Reply With Quote
Old 2009-08-02, 20:32   #10
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

170148 Posts
Default

Quote:
Originally Posted by harlee View Post
First, for 2M exponents, the B2 is B1*13 and for 5M exponents it is B1*16.5 then B1*17.5. Why isn't it B1*20 like Prime95 suggested?
Prime95's suggestion was a rule-of-thumb general recommendation that will give good results.

The prime95 program (and its cousin mprime) uses an algorithm for choosing B1 and B2. The algorithm always chooses a B2 that is a multiple of B1*0.25, but it does not have a hard-coded requirement of B2 = B1*20.

If the algorithm chooses a multiple that is less than 20, that is only because it calculates that the optimal balance of time versus chance of finding a factor is at that multiple. Using 20 explicitly wouldn't ruin anything; it would just be a slightly suboptimal (from a GIMPS project throughput point-of-view) balance of time versus chance of finding a factor.

- - -

The algorithm's "view" might be expressed as:

"Consider the time difference between using B2 = B1*13 (my choice in this specific case) and using B2 = B1*20.

You would have a better chance (but perhaps only very slightly better) of factoring a mersenne number by applying that difference in time toward trying to factor some other exponent than in using that time to search with B2 = B1*20 on this exponent.

But it's your call, if you want to do it -- just use Pminus1= and specify B1/B2 yourself."

Last fiddled with by cheesehead on 2009-08-02 at 20:37
cheesehead is offline   Reply With Quote
Old 2009-08-03, 00:36   #11
markr
 
markr's Avatar
 
"Mark"
Feb 2003
Sydney

3·191 Posts
Default

Quote:
Originally Posted by harlee View Post
First, for 2M exponents, the B2 is B1*13 and for 5M exponents it is B1*16.5 then B1*17.5. Why isn't it B1*20 like Prime95 suggested?
It seems to be a rule of thumb. The optimum is not very peaked - you don't lose much if you move a small distance from it. Also I think it varies with the size of the exponent and the size of B1 & B2 relative to it. Hence "roughly 20".

As cheesehead said, it's your call what B1 & B2 you use. I prefer larger values - probably more than optimal. For example, I did some P-1 on 2M exponents earlier this year mostly using B1=100000, B2=3000000. The Mersenne-aries P-1 probability calculator is a huge help.

Quote:
Originally Posted by harlee View Post
Second, I seem to recall reading the output E=6 has a special meaning, can't seem to find it. Anyway, probably due to the small B1 & B2 settings the 2M exponents are not getting that by default. The is plenty of memory allocated for P-1 stage 2 (1.5GB) to use so that isn't an issue.
The E=6 is from something called the Brent-Suyama extension. This thread is helpful.
markr is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sieving with powers of small primes in the Small Prime variation of the Quadratic Sieve mickfrancis Factoring 2 2016-05-06 08:13
256KB L2 limited to small exponents, but 8MB L3 xorbe Information & Answers 2 2009-02-08 05:08
Unreserving exponents(these exponents haven't been done) jasong Marin's Mersenne-aries 7 2006-12-22 21:59
New "small" exponents available Prime95 PrimeNet 6 2006-05-21 15:38
Small set of 12 GP2 Completed Missions 2 2003-10-03 18:30

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


Sat Oct 16 16:22:52 UTC 2021 up 85 days, 10:51, 0 users, load averages: 1.49, 1.43, 1.30

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.