mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2018-12-06, 16:55   #56
axn
 
axn's Avatar
 
Jun 2003

5,407 Posts
Default

Quote:
Originally Posted by Gordon View Post
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?
axn is offline   Reply With Quote
Old 2018-12-06, 17:29   #57
GP2
 
GP2's Avatar
 
Sep 2003

A1B16 Posts
Default

Quote:
Originally Posted by axn View Post
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
Input number is 0x4D591058893F231FBE69EBEF89B145E1B39711E4E2D33DA1F18BD2E8EA9BDD232321C5FC7FDA0190625DB92793F0433C69FB1B9D55E06CB2712F78F11CB2651238578856D7C38207B0B802860CD4027485E15F72053DF77AA0A6A3C3FF21048AAAD0EB867C49CAD28F57AAB9EA017C9520C4B5241 (281 digits)
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
GP2 is offline   Reply With Quote
Old 2018-12-06, 18:11   #58
PhilF
 
PhilF's Avatar
 
"6800 descendent"
Feb 2005
Colorado

2D516 Posts
Default

Quote:
Originally Posted by GP2 View Post
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?
PhilF is offline   Reply With Quote
Old 2018-12-06, 18:21   #59
GP2
 
GP2's Avatar
 
Sep 2003

13×199 Posts
Default

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
GP2 is offline   Reply With Quote
Old 2018-12-06, 19:15   #60
PhilF
 
PhilF's Avatar
 
"6800 descendent"
Feb 2005
Colorado

2D516 Posts
Default

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
PhilF is offline   Reply With Quote
Old 2018-12-06, 19:38   #61
GP2
 
GP2's Avatar
 
Sep 2003

50338 Posts
Default

Quote:
Originally Posted by PhilF View Post
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
GP2 is offline   Reply With Quote
Old 2018-12-06, 19:40   #62
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

172·19 Posts
Default

Quote:
Originally Posted by PhilF View Post
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.
VBCurtis is offline   Reply With Quote
Old 2018-12-06, 20:37   #63
GP2
 
GP2's Avatar
 
Sep 2003

13×199 Posts
Default 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
GP2 is offline   Reply With Quote
Old 2018-12-06, 21:12   #64
Gordon
 
Gordon's Avatar
 
Nov 2008

3×132 Posts
Default

Quote:
Originally Posted by axn View Post
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.
Gordon is offline   Reply With Quote
Old 2018-12-06, 21:16   #65
Gordon
 
Gordon's Avatar
 
Nov 2008

3×132 Posts
Default

Quote:
Originally Posted by GP2 View Post
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
Gordon is offline   Reply With Quote
Old 2018-12-07, 02:58   #66
axn
 
axn's Avatar
 
Jun 2003

5,407 Posts
Default

Quote:
Originally Posted by Gordon View Post
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 View Post
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.
axn is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to use prime95 for stage 1 & GMP-ECM for stage 2 Prime95 Lone Mersenne Hunters 118 2022-07-04 18:19
Stage 1 G_A_FURTADO Information & Answers 1 2008-10-26 15:21
Stage 1 with mprime/prime95, stage 2 with GMP-ECM D. B. Staple Factoring 2 2007-12-14 00:21
Need help to run stage 1 and stage 2 separately jasong GMP-ECM 9 2007-10-25 22:32
Stage 1 and stage 2 tests missing 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔