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

[Madpoo]

Originally Posted by lorgix

You limited available RAM very strongly. More realistically people will be using a k in the area of 4~20 or so.
If you tell it to use something like half or a quarter of what it "wants" you wont see as dramatic results as when limiting to 250.

If I were you I'd try B2scale 3 next. According to the estimated time to find a factor (given by -v), that should be close to optimal. In practice that is. (Not sure why RDS seem to disagree)

The idea there was to kind of mimic the (lousy?) memory choice Prime95 seems to be making for stage 2, using a puny 207 MB.

Conclusion: it's harmful. But then you don't have to be a rocket surgeon to know that.

[lorgix]

Originally Posted by Madpoo

The idea there was to kind of mimic the (lousy?) memory choice Prime95 seems to be making for stage 2, using a puny 207 MB.

Conclusion: it's harmful. But then you don't have to be a rocket surgeon to know that.

The implementations are very different, as other people have commented.

About the RAM: I just wanted to make sure you wouldn't be afraid to limit RAM usage a little in cases where that might be convenient.

(If you want to put all those GBs of RAM to good use while contributing to GIMPS you may want to look at P-1.)

[Madpoo]

Originally Posted by lorgix

The implementations are very different, as other people have commented.

About the RAM: I just wanted to make sure you wouldn't be afraid to limit RAM usage a little in cases where that might be convenient.

(If you want to put all those GBs of RAM to good use while contributing to GIMPS you may want to look at P-1.)

Okay, well, let me put it this way, is there any reason GMP-ECM would use the slower stage 1 code? Or that Prime95 would use a slower stage 2 routine?

(I don't think I'd ever deliberately limit the memory to gmp-ecm, but if I did it wouldn't be as drastic as going from 18 GB to 250 MB)

[VBCurtis]

Originally Posted by Madpoo

Okay, well, let me put it this way, is there any reason GMP-ECM would use the slower stage 1 code? Or that Prime95 would use a slower stage 2 routine?

(I don't think I'd ever deliberately limit the memory to gmp-ecm, but if I did it wouldn't be as drastic as going from 18 GB to 250 MB)

Prime95 uses an entirely different stage 2 routine, one that takes substantially less memory. Your case on M1277 is unusual, in that the number is small enough for GMP-ECM stage 2 to be practical. Another thread recently explored how small "small" needs to be, with a guess that exponents higher than 30-40k are too large for GMP-ECM's memory requirements (of course, memory the size you have would extend this up a bit). Exponents 1277-40k are such a small range that the folks who chase ECM factors down here can choose to use both programs if need be. The other 99.9x% of users would have no use for the GMP-ECM stage 2.

A similar "rare case" argument is made for stage 1- Prime95's faster code works only for mersenne numbers and (I think?) Fermat numbers. GMP-ECM is general-use, so including the Prime95 stage 1 for just those cases is not helpful for most users. Of course, that's different from answering "what stops someone from combining the two?"; specifically, the FFT stage 1 into GMP-ECM should be possible, though well beyond my pay grade. I'm a button-pusher, not a programmer.

As for flags to try for improved efficiency: Instead of using B2scale, try -k 2. This will choose the next-larger B2 size such that stage 2 will be done in just two steps. This uses more memory, but is usually faster.

[VBCurtis]

Originally Posted by R.D. Silverman

Because there is no such thing as the "correct" ratio. It will be different for different computers.
It will be highly dependent on aggregate DRAM size, L2/L3 cache size, memory latency,
memory bandwidth, etc.

The optimal thing to do for ANY computer is to measure how long step 2 takes relative
to step 1 and select the B2/B1 ratio so that GMP-ECM spends as much time in step 2
as it does in step 1, FOR THAT COMPUTER. This ratio will be DIFFERENT
for different computers.

This must be done on a case-by-case basis.

I'm sorry, we're looking at different "ratio"s. I am not referring to the ratio of B2 to B1. I am referring to the ratio of time spent on B2 to time spent on B1. In your paper, B2 = 0.4K * B1 for that computer/implementation/memory/etc, where K is the relative speed of stage 2 to stage 1. So, if B2 = K * B1, then the machine would have spent as much time in stage 2 as it did in stage 1, since stage 2 is K times faster. Since you chose B2 = 0.4K * B1, it is spending 40% as long in stage 2 as it did in stage 1. (right?)

Yet, you insist that stage 2 time should always be equal to stage 1 time for best results. Your answer to the ratio I am looking for is "always 1, no matter what, on any computer,", even though your paper suggests 0.4 was the correct ratio of stage 2 time to stage 1 time for the machine and software you used in that research. This is the contradiction I am trying to figure out. Can you please explain my error in interpreting your paper?

My previous post tried to make the point that this ratio is subject to discovery by experiment, as you said you did in that paper to find the 0.4 that you used. I used the -v flag in GMP-ECM to find the number of curves for a desired t-level, and tried to minimize the time to complete the listed number of curves for said t-level. This is the suggested procedure in the GMP-ECM documentation to optimize parameters for a particular computer/use case. I understand this to be standard practice, so I thought I was explaining my method when I made mention of the -v flag. I am interested to learn why this is an incorrect procedure, since that is what led me to conclude a ratio of stage 2 time ~ half of stage 1 time is the most efficient way to complete a desired t-level.

[Madpoo]

Originally Posted by VBCurtis

...well beyond my pay grade. I'm a button-pusher, not a programmer.

I'm with you on that.

Originally Posted by VBCurtis

As for flags to try for improved efficiency: Instead of using B2scale, try -k 2. This will choose the next-larger B2 size such that stage 2 will be done in just two steps. This uses more memory, but is usually faster.

I'll give that a try next time, thanks.

[VBCurtis]

A little data sample, for a C166 on a Haswell-E with DDR4:
B1 = 11e6, stage 1 took 46 sec for each run
B2 = 35e9, GMP-ECM default: 18 sec (this is k = 3 steps in stage 2)
t40 686 curves = 12.2 hr
t45 4482 curves = 79.7 hr
t50 33676 curves = 24.95 days

B2 = 240e9, 47 sec and equal to stage 1 time:
t40 503 curves = 13.0 hr
t45 3243 curves = 83.8 hr
t50 23946 curves = 25.78 days

So, for a common B1 choice of 11e6, the default GMP-ECM choice where stage 2 takes 40% the time of stage 1 has a lower expected time to find factors smaller than one would expect, of the size one targets with B1 = 11M (45 digits), and larger factors one might get lucky to find. This is one instance, but the data I took for a wide variety of B1/B2 shows in every case selecting B2 such that stage 2 time = stage 1 time has a longer expected time to find any size factor than stage 2 time = 40-50% of stage 1 time.

I also tested B2 = 96e9, 28 sec for the next-largest B2 that uses k = 2 steps in stage 2:
t40 582 curves = 12.0 hr
t45 3791 curves = 77.9 hr
t50 28048 curves = 24.0 days
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.

[lorgix]

Originally Posted by VBCurtis

A little data sample, for a C166 on a Haswell-E with DDR4:
B1 = 11e6, stage 1 took 46 sec for each run
B2 = 35e9, GMP-ECM default: 18 sec (this is k = 3 steps in stage 2)
t40 686 curves = 12.2 hr
t45 4482 curves = 79.7 hr
t50 33676 curves = 24.95 days

B2 = 240e9, 47 sec and equal to stage 1 time:
t40 503 curves = 13.0 hr
t45 3243 curves = 83.8 hr
t50 23946 curves = 25.78 days

So, for a common B1 choice of 11e6, the default GMP-ECM choice where stage 2 takes 40% the time of stage 1 has a lower expected time to find factors smaller than one would expect, of the size one targets with B1 = 11M (45 digits), and larger factors one might get lucky to find. This is one instance, but the data I took for a wide variety of B1/B2 shows in every case selecting B2 such that stage 2 time = stage 1 time has a longer expected time to find any size factor than stage 2 time = 40-50% of stage 1 time.

I also tested B2 = 96e9, 28 sec for the next-largest B2 that uses k = 2 steps in stage 2:
t40 582 curves = 12.0 hr
t45 3791 curves = 77.9 hr
t50 28048 curves = 24.0 days
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.

This is how I arrived at stage1time:stage2time::1:0.695.

About k: It is true that all else equal, a lower k is more efficient. But you will often need to use a different k to reach the optimal relationship between stage1time and stage2time. I mostly use B2scale, but I also pay attention to k and B2. Sometimes large steps occur, and I then test two (or more) different settings.

[R.D. Silverman]

Originally Posted by VBCurtis

A little data sample, for a C166 on a Haswell-E with DDR4:
B1 = 11e6, stage 1 took 46 sec for each run
B2 = 35e9, GMP-ECM default: 18 sec (this is k = 3 steps in stage 2)
t40 686 curves = 12.2 hr
t45 4482 curves = 79.7 hr
t50 33676 curves = 24.95 days

B2 = 240e9, 47 sec and equal to stage 1 time:
t40 503 curves = 13.0 hr
t45 3243 curves = 83.8 hr
t50 23946 curves = 25.78 days

So, for a common B1 choice of 11e6, the default GMP-ECM choice where stage 2 takes 40% the time of stage 1 has a lower expected time to find factors smaller than one would expect,

Did you pull this conclusion from your ass? I see no, repeat no, zilch, nada computation
for the probability of finding a factor given your B1, B2 choices.

What is your OBJECTIVE FUNCTION???

Where are the probability computations? You can not conclude anything about
"lower expected time", unless you know what the probability of success is.

I see a lot of data about computation time. Nowhere do I see any kind of an
optimization. WHAT ARE YOU OPTIMIZING? It certainly is not the primary
objective, which is to maximize the probability of success per UNIT TIME spent.

[lorgix]

Originally Posted by R.D. Silverman

Did you pull this conclusion from your ass? I see no, repeat no, zilch, nada computation
for the probability of finding a factor given your B1, B2 choices.

What is your OBJECTIVE FUNCTION???

Where are the probability computations? You can not conclude anything about
"lower expected time", unless you know what the probability of success is.

I see a lot of data about computation time. Nowhere do I see any kind of an
optimization. WHAT ARE YOU OPTIMIZING? It certainly is not the primary
objective, which is to maximize the probability of success per UNIT TIME spent.

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

[fivemack]

Originally Posted by R.D. Silverman

Did you pull this conclusion from your ass? I see no, repeat no, zilch, nada computation
for the probability of finding a factor given your B1, B2 choices.

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.