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

[R.D. Silverman]

Originally Posted by lorgix

He is using the -v flag of GMP-ECM, and trusting the values it returns.

This is a non-answer to the question I asked.

[R.D. Silverman]

Originally Posted by fivemack

Yes you do, that's the 't40 503 curves' part; gmp-ecm has implementations of all the Dickman-function work necessary for computing that probability, and reports its reciprocal there.

A choice of B1, B2 is optimal only for a particular factor SIZE. Dickman's function only returns
probabilities of smoothness for given B1,B2 with respect to a composite integer of a given size.
There is no such specification of size in the discussion. All that is presented is run-time info
for various B1, B2 choices.

There are still no probabilities given in the discussion, nor do I see any computations
involving probability/time.

[R.D. Silverman]

Originally Posted by fivemack

Yes you do, that's the 't40 503 curves' part; gmp-ecm has implementations of all the Dickman-function work necessary for computing that probability, and reports its reciprocal there.

We see, for example, a choice of B1, B2 for t40 and a time of 12.2 hrs.
We also see a choice for t40 where B2 is raised from 35e9 to 240e9 and a time of 13 hrs.

We do not see how the probability of success CHANGED when B2 went from 35e9 to 240e9.
Did it change more than or less than the relative time increase? (i.e. 13/12.2)

If the probability went up by more than a factor of 13/12.2, then it is clear that the choice
of 240e9 (i.e. equal time in step 1 and step 2) does give an improvement.

But nowhere in the discussion are the relative probabilities discussed!

[bsquared]

Originally Posted by R.D. Silverman

We see, for example, a choice of B1, B2 for t40 and a time of 12.2 hrs.
We also see a choice for t40 where B2 is raised from 35e9 to 240e9 and a time of 13 hrs.

We do not see how the probability of success CHANGED when B2 went from 35e9 to 240e9.
Did it change more than or less than the relative time increase? (i.e. 13/12.2)

If the probability went up by more than a factor of 13/12.2, then it is clear that the choice
of 240e9 (i.e. equal time in step 1 and step 2) does give an improvement.

But nowhere in the discussion are the relative probabilities discussed!

The probablility stays the same - that is the definition of "t40". t40 means there is a 1/e chance of missing a factor of size 40 digits with the provided parameters. GMP-ECM computes all of the probabilities and is also aware of how long it takes itself to compute a curve. Running -v reports these details. When B2=35e9 it will take 12.2 hours to have a 1/e chance of missing a factor of size 40 digits. With B2=240e9 it takes 13 hours to have the same chance of missing a factor of size 40 digits. So the relative probabilities are being discussed.

[R.D. Silverman]

Originally Posted by bsquared

The probablility stays the same - that is the definition of "t40".

Ah. That's the part that I was missing.

[VBCurtis]

Originally Posted by lorgix

He is using the -v flag of GMP-ECM, and trusting the values it returns.

This is not-quite-true; I average the times for a bunch of stage 1 runs, a couple of stage 2 runs for each choice of B2, and then multiply by the number of curves expected to be required to find a factor. This is a bit more accurate to get expected-time-to-find, but it's useful accuracy when trying to find 5% or small improvements. I do trust -v to provide expected curve counts, as listed in my sample data.

Doing such work on a spreadsheet also allows for quick calculation of expected time for a variety of B1/B2 values; invoking ECM with -v provides the expected curve counts immediately, so I can call ECM with a combination not already tried, note the curve counts required, and use the timings from previous stage 1 & stage 2 runs to find expected time to find a factor. Also, Stage 1 time is almost precisely linear in B1, so one can extrapolate for a variety of B1 values.

Now that Mr Silverman understands the definition of t40 and t45, how does the choice of B2=240e9 improve the probability of success PER UNIT TIME to find any size factor over B2=35e9, or 96e9?

[R.D. Silverman]

Originally Posted by VBCurtis

This is not-quite-true; I average the times for a bunch of stage 1 runs, a couple of stage 2 runs for each choice of B2, and then multiply by the number of curves expected to be required to find a factor. This is a bit more accurate to get expected-time-to-find, but it's useful accuracy when trying to find 5% or small improvements. I do trust -v to provide expected curve counts, as listed in my sample data.

Doing such work on a spreadsheet also allows for quick calculation of expected time for a variety of B1/B2 values; invoking ECM with -v provides the expected curve counts immediately, so I can call ECM with a combination not already tried, note the curve counts required, and use the timings from previous stage 1 & stage 2 runs to find expected time to find a factor. Also, Stage 1 time is almost precisely linear in B1, so one can extrapolate for a variety of B1 values.

Now that Mr Silverman understands the definition of t40 and t45, how does the choice of B2=240e9 improve the probability of success PER UNIT TIME to find any size factor over B2=35e9, or 96e9?

Clearly, for this implementation/hardware combination, it doesn't.

[bsquared]

Originally Posted by R.D. Silverman

Clearly, for this implementation/hardware combination, it doesn't.

Perhaps it's worth noting at this point that GMP-ECM implements features that violate assumptions made in the paper. So it should be no surprise that the results of the paper do not hold. For instance, stage 2 in GMP-ECM uses a fast polynomial arithmetic continuation. Therefore the time to compute to B2 is not a linear function of B1, as assumed in the paper. I.e., K increases with increasing (B2 - B1). GMP-ECM can also find factors by the Brent-Suyama extension, which is not treated in the paper.

[ATH]

Originally Posted by VBCurtis

These expected times are better than GMP-ECM default, showing the improved efficiency of choosing B2 such that stage 2 uses just 2 steps. This is why I suggest the -k 2 flag rather than B2scale in general.

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

With P-1 and P+1 it never uses the exact B2 value you type in, but chooses the next larger that fits with parameters. For ECM it displays the exact value you typed in which makes me think it might do a stage 2 with a larger B2 value fitting parameters in the background, which could be why -k 2 is sometimes faster because it fits parameters better.

[VBCurtis]

Interesting! When I tried -k 1, it did not use just one step. I'll look into what I did wrong when I first tried that- I assumed it just never would do a single-step stage 2.
The data point you posted is a substantial improvement, and most of my ECM usage (t45 and t50 levels) is not memory-limited, so this could speed things along nicely.
Thanks!

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.

[lorgix]

Originally Posted by VBCurtis

This is not-quite-true; I average the times for a bunch of stage 1 runs, a couple of stage 2 runs for each choice of B2, and then multiply by the number of curves expected to be required to find a factor. This is a bit more accurate to get expected-time-to-find, but it's useful accuracy when trying to find 5% or small improvements. I do trust -v to provide expected curve counts, as listed in my sample data.

Doing such work on a spreadsheet also allows for quick calculation of expected time for a variety of B1/B2 values; invoking ECM with -v provides the expected curve counts immediately, so I can call ECM with a combination not already tried, note the curve counts required, and use the timings from previous stage 1 & stage 2 runs to find expected time to find a factor. Also, Stage 1 time is almost precisely linear in B1, so one can extrapolate for a variety of B1 values.

Now that Mr Silverman understands the definition of t40 and t45, how does the choice of B2=240e9 improve the probability of success PER UNIT TIME to find any size factor over B2=35e9, or 96e9?

Yeah, I do the same. I was hoping my post could help clear up the confusion. Apparently it didn't work, but then B^2 stepped in.

Originally Posted by bsquared

Perhaps it's worth noting at this point that GMP-ECM implements features that violate assumptions made in the paper. So it should be no surprise that the results of the paper do not hold. For instance, stage 2 in GMP-ECM uses a fast polynomial arithmetic continuation. Therefore the time to compute to B2 is not a linear function of B1, as assumed in the paper. I.e., K increases with increasing (B2 - B1). GMP-ECM can also find factors by the Brent-Suyama extension, which is not treated in the paper.

I still don't see how the paper says to spend as much time in stage2 as in stage1. I read it as stage1time:stage2time::0.59:0.41, which is consistent with my experience (testing in the way VBCurtis describes).

edit:
About k and B2: GMP-ECM won't use just any B2 you supply, it will use a reasonable number close to what you supply. It doesn't necessarily use the k you supply either, IIRC.