P-1 on small exponents

[markr]

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?

[garo]

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.

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.

[garo]

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.

[Prime95]

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.

[Kevin]

Originally Posted by garo

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.

[markr]

Originally Posted by garo

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]

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.

[garo]

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

[harlee]

Originally Posted by Prime95

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?

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.

[cheesehead]

Originally Posted by harlee

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."

[markr]

Originally Posted by harlee

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.

Originally Posted by harlee

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.