mersenneforum.org ECM Stage 2 RAM
 Register FAQ Search Today's Posts Mark Forums Read

2018-12-06, 16:55   #56
axn

Jun 2003

5,407 Posts

Quote:
 Originally Posted by Gordon Step 1 took 3847484ms Step 2 took 1217010ms
Interesting.
1) Why is Step 1 running again?
2) How much time would P95 have taken on this B2?

2018-12-06, 17:29   #57
GP2

Sep 2003

A1B16 Posts

Quote:
 Originally Posted by axn Interesting. 1) Why is Step 1 running again? 2) How much time would P95 have taken on this B2?
Perhaps GMP-ECM's implementation of stage 2 uses a step 1 and a step 2. So it's not redoing stage 1, at least I hope not. The README file does refer to "stage 1" and "stage 2", so I don't think "step 1" is a synonym for "stage 1", unless they're very loose with their terminology.

I'm doing some ECM of small Wagstaff numbers up to t=40, and I get the same thing when using GMP-ECM to do stage 2 where stage 1 was done by mprime.

GMP-ECM is run with the -resume option specifying the output written by mprime to results.txt, where mprime used B1=B2 and the GmpEcmHook=1 setting in prime.txt. If it really is redoing stage 1, I hope someone will let me know how to avoid it...

Here's some sample verbose output:

Code:
GMP-ECM 7.0.4 [configured with GMP 6.0.0, --enable-asm-redc] [ECM]
Running on ip-***-***-***-***.us-east-2.compute.internal
Resuming ECM residue saved with Prime95
Using special division for factor of 2^1063+1
Using B1=3000000, B2=5706890290, polynomial Dickson(6), sigma=0:4566259830273646
dF=16384, k=2, d=158340, d2=11, i0=8
Expected number of curves to find a factor of n digits:
35      40      45      50      55      60      65      70      75      80
324     2351    20272   201449  2247436 2.8e+07 3.9e+08 6e+09   1.1e+11 7.4e+15
Step 1 took 11982ms
Using 33 small primes for NTT
Estimated memory usage: 88.06MB
Initializing tables of differences for F took 11ms
Computing roots of F took 392ms
Building F from its roots took 620ms
Computing 1/F took 324ms
Initializing table of differences for G took 18ms
Computing roots of G took 367ms
Building G from its roots took 648ms
Computing roots of G took 368ms
Building G from its roots took 647ms
Computing G * H took 175ms
Reducing  G * H mod F took 169ms
Computing polyeval(F,G) took 1221ms
Computing product of all F(g_i) took 10ms
Step 2 took 5025ms

Last fiddled with by GP2 on 2018-12-06 at 17:38 Reason: mask internal IP address

2018-12-06, 18:11   #58
PhilF

"6800 descendent"
Feb 2005

2D516 Posts

Quote:
 Originally Posted by GP2 If it really is redoing stage 1, I hope someone will let me know how to avoid it...
I am getting ready to do some Fermat ECM factoring work, and I think I'll wait until you get a firm answer on that before I start.

I'm surprised the need to hook the two programs together in order to get the most efficiency still exists. Is there a reason the faster GMP-ECM stage 2 code has not been implemented in Prime95/mprime?

 2018-12-06, 18:21 #59 GP2     Sep 2003 13×199 Posts Hmm... so much for my theories about "step" vs. "stage". I just tried running a curve where both stage 1 and stage 2 were done with GMP-ECM, and the whole thing actually ran faster than letting GMP-ECM resume the output of mprime's stage 1! At least for this particular exponent. And that doesn't even include the time that mprime itself spent doing stage 1 (needlessly??). The value of B2=5706890290 was automatically selected in both cases, and the 281-digit "Input number is" values are equal in both cases (specified as a hex number in the first example since that's how mprime outputs it, and specified as (2^1063+1)/3 divided by the two known factors in the second example below. So the only thing different in the two situations is a different sigma. The command was: Code: echo "(2^1063+1)/3/114584129081/26210488518118323164267329859" | ecm -v 3000000 and the output was: Code: GMP-ECM 7.0.4 [configured with GMP 6.0.0, --enable-asm-redc] [ECM] Running on ip-***-***-***-***.us-east-2.compute.internal Input number is (2^1063+1)/3/114584129081/26210488518118323164267329859 (281 digits) Using special division for factor of 2^1063+1 Using B1=3000000, B2=5706890290, polynomial Dickson(6), sigma=0:12915475272312803168 dF=16384, k=2, d=158340, d2=11, i0=8 Expected number of curves to find a factor of n digits: 35 40 45 50 55 60 65 70 75 80 324 2351 20272 201449 2247436 2.8e+07 3.9e+08 6e+09 1.1e+11 7.4e+15 Step 1 took 10870ms Using 33 small primes for NTT Estimated memory usage: 88.06MB Initializing tables of differences for F took 10ms Computing roots of F took 357ms Building F from its roots took 570ms Computing 1/F took 302ms Initializing table of differences for G took 16ms Computing roots of G took 335ms Building G from its roots took 592ms Computing roots of G took 336ms Building G from its roots took 580ms Computing G * H took 154ms Reducing G * H mod F took 164ms Computing polyeval(F,G) took 1090ms Computing product of all F(g_i) took 9ms Step 2 took 4570ms Expected time to find a factor of n digits: 35 40 45 50 55 60 65 70 75 80 1.39h 10.08h 3.62d 36.00d 1.10y 13.81y 192.57y 2937y 54485y 4e+09y Peak memory usage: 130MB Last fiddled with by GP2 on 2018-12-06 at 18:30
 2018-12-06, 19:15 #60 PhilF     "6800 descendent" Feb 2005 Colorado 2D516 Posts Do you have mprime set to limit the number of cores it can use? I'm also wondering if your results would be very different if the input number was millions of digits. Last fiddled with by PhilF on 2018-12-06 at 19:17
2018-12-06, 19:38   #61
GP2

Sep 2003

50338 Posts

Quote:
 Originally Posted by PhilF Do you have mprime set to limit the number of cores it can use? I'm also wondering if your results would be very different if the input number was millions of digits.
These are running on one-core virtual machines, so it's not an issue.

Also it shouldn't matter to gmp-ecm how many cores mprime used in stage 1. The input to ecm is just a number, it shouldn't matter how that number was arrived at.

Empirically, it's been reported that GMP-ECM works well only for small Mersenne exponents, under about 40k. So I don't think the millions-of-digits case would occur in practice.

Last fiddled with by GP2 on 2018-12-06 at 19:58

2018-12-06, 19:40   #62
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

172·19 Posts

Quote:
 Originally Posted by PhilF Do you have mprime set to limit the number of cores it can use? I'm also wondering if your results would be very different if the input number was millions of digits.
Yes, the outcome is quite different for large-large inputs!

GMP-ECM and mprime use very different methods for ECM computation. mprime (prime95) scales very well by input size, while GMP-ECM uses a stage 2 that's very very fast for small input sizes.

Below about 400(?) digits, GMP-ECM is faster in both stages. Above about 12000 digits (though Gordon above disagrees with this number!), mprime is faster for both stages. In between, the fastest method is to use mprime's fast stage1 code and GMP-ECM's fast-for-big-B2 stage 2. The set of users that care about inputs below 12000 digits is small, likely why the GMP-ECM stage 2 has never been incorporated into mprime.

 2018-12-06, 20:37 #63 GP2     Sep 2003 13×199 Posts How to avoid needlessly redoing stage 1 in GMP-ECM!!!! I think I figured it out. As mentioned before, if you want to do stage 1 with mprime/Prime95 and stage 2 wth GMP-ECM, first you need to run mprime/Prime95 with the line GmpEcmHook=1 in your prime.txt file, and you need to set B1 and B2 to the same value (say 3000000) in your ECM2= lines in your worktodo.txt file. Then mprime/Prime95 will output a bunch of lines starting with N= into your results.txt file, instead of its normal output. If you specified 1000 ECM curves, then there will be 1000 lines with N=. Note, if B1 and B2 aren't the same value in the worktodo.txt line, then GmpEcmHook=1 will be ignored and mprime/Prime95 will just do both stage 1 and stage 2 all by itself, and will output only the typical single line of the form "Mxxxx completed xxx ECM curves, B1=nnnnnnn, B2=nnnnnnnnn" Then you feed that results.txt file to GMP-ECM. I don't know if you need to filter out all the lines that don't start with N=, probably GMP-ECM just ignores them. You do that with the command: (assuming you used B1=3000000, change to whatever the actual value is) Code: ecm -resume results.txt 3000000-3000000 > my_output_file.txt Then when it finishes, you search your my_output_file.txt (or whatever you called it) for lines that begin with: Code: ********** Factor found in step But the crucial thing is to specify the argument as 3000000-3000000 (meaning, do stage 1 for B1 from the range 3 million to 3 million, i.e. don't do it at all, but you need to specify the 3 million twice anyway so that B2 gets automatically sized appropriately). Of course, you can specify your own value for B2 if you don't want GMP-ECM's default calculated value. And change the "3 million" to whatever actual value of B1 you used in stage 1. If you do that, then you get "Step 1 took 0 ms". But if you just specify the argument as 3000000, as I was doing these past few weeks for ECM on small Wagstaff numbers, then it does stage 1 for B1 from 0 to 3 million, i.e., redoes the whole thing. I hadn't done GMP-ECM for a long time, so I forgot about this nuance, and it's not actually very well documented, if at all. TL;DR: when running GMP-ECM with -resume and you don't want it to redo stage 1, specify the B1 value as a range from itself to itself, with a hyphen in between, rather than just specifying it as a simple number, which will be interpreted as a range from 0 to that number. Last fiddled with by GP2 on 2018-12-06 at 21:00
2018-12-06, 21:12   #64
Gordon

Nov 2008

3×132 Posts

Quote:
 Originally Posted by axn Interesting. 1) Why is Step 1 running again? 2) How much time would P95 have taken on this B2?
In answer to point 1 - that's my fault, it was early days of using gmp-ecm and I didn't know then that if I had stated the B1 value as

1000000-1000000

then it would have skipped redoing the stage 1. Learnt from that mistake early on :-)

as to point 2 I've got no idea.

2018-12-06, 21:16   #65
Gordon

Nov 2008

3×132 Posts

Quote:
 Originally Posted by GP2 Perhaps GMP-ECM's implementation of stage 2 uses a step 1 and a step 2. So it's not redoing stage 1, at least I hope not. The README file does refer to "stage 1" and "stage 2", so I don't think "step 1" is a synonym for "stage 1", unless they're very loose with their terminology. I'm doing some ECM of small Wagstaff numbers up to t=40, and I get the same thing when using GMP-ECM to do stage 2 where stage 1 was done by mprime. GMP-ECM is run with the -resume option specifying the output written by mprime to results.txt, where mprime used B1=B2 and the GmpEcmHook=1 setting in prime.txt. If it really is redoing stage 1, I hope someone will let me know how to avoid it... [snip]
ecm -maxmem 14000 -resume results.txt 1000000-1000000 100000000 > newresults.txt

2018-12-07, 02:58   #66
axn

Jun 2003

5,407 Posts

Quote:
 Originally Posted by Gordon In answer to point 1 - that's my fault, it was early days of using gmp-ecm and I didn't know then that if I had stated the B1 value as 1000000-1000000 then it would have skipped redoing the stage 1. Learnt from that mistake early on :-)
Cool

Quote:
 Originally Posted by Gordon as to point 2 I've got no idea.
The reason I ask is that I suspect P95 will be (much) faster at that exponent size and that B2 level (smaller exponent and/or larger B2 will tilt it in favor of GMP-ECM). If you ever run similar ECMs in the future, it'll be definitely worthwhile to benchmark both options before you select which way to go.

 Similar Threads Thread Thread Starter Forum Replies Last Post Prime95 Lone Mersenne Hunters 118 2022-07-04 18:19 G_A_FURTADO Information & Answers 1 2008-10-26 15:21 D. B. Staple Factoring 2 2007-12-14 00:21 jasong GMP-ECM 9 2007-10-25 22:32 Matthias C. Noc PrimeNet 5 2004-08-25 15:42

All times are UTC. The time now is 14:33.

Wed Oct 5 14:33:55 UTC 2022 up 48 days, 12:02, 0 users, load averages: 1.38, 1.37, 1.37