How to use prime95 for stage 1 & GMP-ECM for stage 2

[VBCurtis]

I read it as stage 1 time : stage 2 time = 1 : 0.4. That's from B2 = 0.4K * B1, where K is the ratio of stage 2 speed to stage 1 speed. If stage 2 runs K times faster than stage 1, and we run stage 2 from B1 to 0.4*K*B1, we will spend 40% of stage 1 time in stage 2.

Earlier in this thread, Mr Silverman says that K = 0.4 was found experimentally, and could (should?) vary from implementation to implementation. When using GMP-ECM, we are constrained by the coarse choices for B2, which likely swamps the hope to find a 'magic' stage 2 : stage 1 time ratio.

[lorgix]

Originally Posted by VBCurtis

I read it as stage 1 time : stage 2 time = 1 : 0.4. That's from B2 = 0.4K * B1, where K is the ratio of stage 2 speed to stage 1 speed. If stage 2 runs K times faster than stage 1, and we run stage 2 from B1 to 0.4*K*B1, we will spend 40% of stage 1 time in stage 2.

Earlier in this thread, Mr Silverman says that K = 0.4 was found experimentally, and could (should?) vary from implementation to implementation. When using GMP-ECM, we are constrained by the coarse choices for B2, which likely swamps the hope to find a 'magic' stage 2 : stage 1 time ratio.

You can vary B1 instead.

[VBCurtis]

Originally Posted by ATH

-k 1 should be even better if you have enough RAM, it should be faster to do stage 2 in one chunk. For P-1 and P+1 it is always faster with -k 1 and I measured it on many occations, but with ECM it sometimes seems faster with -k 2 for some reason.

M1277 B1=110e6 B2=2e12:
k=1: Step 2 took 519171ms (Peak memory usage: 4400MB)
k=2: Step 2 took 720366ms (Peak memory usage: 4593MB)
So here -k 1 was faster but -k 2 took more RAM which makes no sense.

Can you post what actual B2 sizes GMP-ECM used for these runs? I'm pretty sure your k = 2 run had a B2 twice as large as your k = 1 run. The memory use is consistent with running two blocks of size identical to your k = 1 run.

If I'm right, your occasional k = 2 faster than k = 1 is also explained: the B2 you enter is bigger than a single block but smaller than 2 blocks, so its run for k =1 is twice as large as k = 2. Each doubling of memory multiplies B2 by four (ignoring small rounding), so k =2 will always have B2 either half or double a k = 1 run.

If you specify a -k value and have enough memory for your choice, GMP-ECM will choose the next B2 value *larger* than the B2 you request that can use k steps. For instance, B1 = 11e6 will choose B2 = 35e9 by default (k = 3 steps of 12e9 each), but -k 1 will jump to a single 48e9 step. -k 2 will use 2 steps of 48e9, for a B2 of 96e9.

[ATH]

M1277stage2.txt

As you can see there are 4 extra line in the -k 2 run, so it is actually doing 2 steps. But you are probably right they are not running the same B2, but you cannot see it, it shows as 2e12 for both.

If I try P-1 with B1=1e8 and chooses B2=2e12 it actually uses B2=3042014761758, and it uses k=2 even when I start with -k 1 parameter. I have to adjust B2 value to find a spot where it can run k=1. But it seems all of this might be hidden for ECM.

Edit: First test isn't so interesting. I tried B1 = 11e6, B2 = 47e9 with the usual k=4, and with k=1 (GMP-ECM chose 48e9 for this). Stage 2 times were nearly equal, a tiny bit slower for k=1. Perhaps this is why GMP-ECM never chooses k=1 on its own. Your result is clearly faster, so it bears more experimentation.

Can you post your number and I will try test it a bit.

[ATH]

Stage 2 for P-1, P+1, ECM can be done in several "stages". When I do a huge P-1/P+1 on numbers like M1277 I try different B2 values until I find one range that runs on k=1 and fits in my RAM, and then I create a .bat file that keeps running stages with the B2 length for increasing B2 values.

For example if I resume from my 1e12 stage1 savefile for M1277 and type B2=40e12 and -maxmem=9000 it uses:
B2=50610232222492 and k=2: Step 2 took 162616ms. 2191MB RAM. Speed: 49610e9/162.616sec ~ 305e9 per second.

Then I try something slightly over the B2=50e12 for example B2=55e12, then it uses:
B2=77325117087180 and k=3: Step 2 took 214595ms. 2191MB RAM. Speed: 76325e9/214.595sec ~356e9 per second.

Then I choose: B2=80e12 and it uses:
B2=100220645554972 and k=1: Step 2 took 230195ms. 4310MB RAM. Speed: 99220e9/230.195sec = 431e9 per second

Continuing to test speed:

B2=128208510935776 and k=5: Step 2 took 298320ms. 2192MB RAM. Speed: 127209e9/298.320sec = 426e9 per second

B2=206701342595580 and k=2: Step 2 took 318804ms. 4310MB RAM. Speed 205701e9/318.804sec = 645e9 per second

B2=307754275966846 and k=3: Step 2 took 415509ms. 4310MB RAM. Speed 306754e9/415.509sec = 738e9 per second

B2=412403056413180 and k=1: Step 2 took 457316ms. 8547MB RAM. Speed 411403e9/457.316sec = 900e9 per second

The combination of RAM usage and the lower the k the faster it is. For my actual P-1 on M1277 I used "stages" of the last length of B2 of 411e12 and k=1.

[ATH]

Testing more I realized that for my situation where I want as high a B2 as possible with a fixed amount of RAM it is actually faster with higher k values, but the gain is diminishing with each additional k:

B2=412403056413180 and k=1: Step 2 took 457316ms. 8547MB RAM. Speed 411403e9/457.316sec = 900e9 per second
B2=813933287856988 and k=2: Step 2 took 651928ms. 8547MB RAM. Speed 812933e9/651.928sec = 1247e9 per second
B2=1207728689654866 and k=3:Step 2 took 859347ms. 8546MB RAM. Speed 1206728e9/859.347sec = 1404e9 per second
B2=1616780995945930 and k=4:Step 2 took 1062336ms. 8547MB RAM. Speed 1615781e9/1062.336sec = 1521e9 per second
B2=2115504465424782 and k=5:Step 2 took 1275199ms. 8547MB RAM. Speed 2114504e9/1275.199sec = 1658e9 per second
B2=2551698640606480 and k=6:Step 2 took 1483975ms. 8548MB RAM. Speed 2550699e9/1483.975sec = 1719e9 per second

But I still think when you want a fixed B2 value for ECM it is faster with lowest k if it is possible to find the correct parameters in that range.

[fivemack]

I really don't think that a speed in number-of-primes-per-second makes sense - stage 2 is a list-matching process and you'd expect the time to be proportional to the square root of B2, so larger B2 will automatically run 'faster' in the sense you're using.

The relevant figure is probability-of-factor per second (which is of course also dependent on the B1 value); running ECM on (10^211)/9 with B1=10^8, where it takes 329.74s to do the B1 step, I get

k=1 B2=0.012e12    6.1s  135MB  t55 needs 43893 curves total 4095 hours
k=1 B2=0.194e12   27.7s  566MB  t55 needs 25328 curves total 2515 hours
k=1 B2=0.794e12   82.1s 1157MB  t55 needs 19192 curves total 2196 hours
k=1 B2=3.178e12  181.7s 2393MB  t55 needs 15427 curves total 2192 hours
k=2 B2=6.357e12  272.1s 2393MB  t55 needs 13853 curves total 2316 hours
k=3 B2=9.535e12  346.2s 2393MB  t55 needs 13079 curves total 2456 hours

[ATH]

Yeah the last 2 post went on a tangent, where I was mostly talking about optimizing speed for a single huge P-1 or P+1 curve, so I was focusing on the actual stage2 speed.

But for ECM you should definitely consider the required number of curves as well as the speed of the stage2, and it does look like k=1 is fastest in your test.

[Madpoo]

It's a simple enough question... I did some ECM work doing stage 1 in Prime95 and then used the ecm hook option to then do stage 2 in GMP-ECM.

Question is: Can the same be done with P-1? That same option didn't seem to do anything on a P-1 stage 1 that I tried... did I do it wrong or is that not really an option with P-1 at all?

Follow-up question: Does it even hold true with P-1 that stage 1 is faster in Prime95 and stage 2 is faster in GMP-ECM? Or is that only true for ECM work? I thought maybe Prime95 actually used more memory for P-1 than it does for ECM so I kind of wonder if I need to bother with jumping through hoops?

[Prime95]

There is no option for doing P-1 stage 1 in prime95 and stage 2 in GMP-ECM. If such an option did exist, GMP-ECM would be vastly superior to Prime95's stage 2 for small exponents.

I do not know if GMP-ECM would support this if I implemented the feature in prime95.

[R.D. Silverman]

Originally Posted by Prime95

There is no option for doing P-1 stage 1 in prime95 and stage 2 in GMP-ECM. If such an option did exist, GMP-ECM would be vastly superior to Prime95's stage 2 for small exponents.

I do not know if GMP-ECM would support this if I implemented the feature in prime95.

A better question:

Why would you want to? If people would ever bother to READ my ECM paper they might actually learn something.

Running P-1 is equivalent to running a single ECM curve. If it is known a priori that P-1 is divisible by (say) q, then one
simply reduces the size of the factor you are looking for by log(q) and then chooses the ECM parameters appropriately
for running just one curve.

However, it is clear that rather than run a SINGLE ECM curve to high limits (which is what P-1 to high limits accomplishes)
it is much better to run MANY ECM curves with lower limits.

This @&*!&*#%^ fascination with running P-1 to high limits is simply WRONG-HEADED. [unless of course, ECM is not
available]