mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2007-12-20, 21:27   #1
Jay
 
Jay's Avatar
 
Dec 2007

2·17 Posts
Default gwnum under Win32

Has anyone been able to get GMP-ECM to build under Win32 with gwnum? I've tried with mingw and cygwin, but find it unable to build using gwnum. It appears to be a case of name mangling confusion preventing the linker from resolving global references.
Jay is offline   Reply With Quote
Old 2007-12-26, 19:58   #2
Jay
 
Jay's Avatar
 
Dec 2007

2×17 Posts
Default

Quote:
Originally Posted by Jay View Post
Has anyone been able to get GMP-ECM to build under Win32 with gwnum? I've tried with mingw and cygwin, but find it unable to build using gwnum. It appears to be a case of name mangling confusion preventing the linker from resolving global references.

Okay, I'll make an assumption that nobody has been able to build GMP-ECM for Win32 using the gwnum library. It's too bad since Prime95 doesn't allow resumption of stage-1 and requires redoing the work to push B1 higher.
Jay is offline   Reply With Quote
Old 2007-12-26, 21:51   #3
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

5,743 Posts
Default

why bother
henryzz is offline   Reply With Quote
Old 2007-12-27, 01:58   #4
Jay
 
Jay's Avatar
 
Dec 2007

1000102 Posts
Default

Quote:
Originally Posted by henryzz View Post
why bother
You do a full run of B1=1e6 (around 950 curves) and fail to get a factor. Now you have a choice of doing a full set of 2500 curves at B1=3e6, or you could utilize the nearly 1000 curves that are 1/3 done already.

1500 full B1=3e6 curves + 1000 curves with 1/3 of their stage-1 work done

Versus

2500 full B1=3e6 curves

Why bother? Seems that it would save a whole hell of a lot of CPU cycles using the ability to resume previously done work. While that may not mean much to you, I prefer not to have to repeat work already done.
Jay is offline   Reply With Quote
Old 2007-12-27, 09:04   #5
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25·7·11 Posts
Default

The interface between GMP-ECM and GWNUM is buggy at the moment, it's been on the TO-DO list for way too long now. I'll see what I can do over the holidays.

Continuing ECM curves that failed to find a factor to higher B1,B2 values is not very effective. For small variations of B1 and fixed B2/B1, the probability of finding a factor of a given size increases linearly with B1 (assuming B1 was chosen "about right" for the factor size in question). Assuming this linear behaviour holds, resuming an ECM curve to three times the B1 saves you 1/3 of the work in stage 1, but does not save anything in stage 2, yet reduces your probability of success by 1/3 w.r.t an all fresh curve. The function becomes decidedly sub-linear as you keep increasing B1 so at some point, it should make sense to recycle old curves if the ratio of new B1/old B1 is large enough. This "large enough" however will be large enough that you save only a tiny part of the cpu time over starting with a fresh curve. IIRC, someone here did the math and compared actual probabilities with actual cpu times for different B1,B2 parameters and concluded that it wasn't worth the hassle.

Alex

Last fiddled with by akruppa on 2007-12-27 at 09:12
akruppa is offline   Reply With Quote
Old 2007-12-28, 07:16   #6
Jay
 
Jay's Avatar
 
Dec 2007

3410 Posts
Default

Quote:
Originally Posted by akruppa View Post
Continuing ECM curves that failed to find a factor to higher B1,B2 values is not very effective. For small variations of B1 and fixed B2/B1, the probability of finding a factor of a given size increases linearly with B1 (assuming B1 was chosen "about right" for the factor size in question). Assuming this linear behaviour holds, resuming an ECM curve to three times the B1 saves you 1/3 of the work in stage 1, but does not save anything in stage 2, yet reduces your probability of success by 1/3 w.r.t an all fresh curve. The function becomes decidedly sub-linear as you keep increasing B1 so at some point, it should make sense to recycle old curves if the ratio of new B1/old B1 is large enough. This "large enough" however will be large enough that you save only a tiny part of the cpu time over starting with a fresh curve. IIRC, someone here did the math and compared actual probabilities with actual cpu times for different B1,B2 parameters and concluded that it wasn't worth the hassle.
I've been told by a number of people who claim to understand ECM factoring that the expected curves at any given level are sufficient proof to rule out any factors smaller than that level. If this is true, then recycling curves from the prior level should not change the chances of any given curve providing a solution.

Nearly all of the factoring I do is very long curve times. I'm currently working on B1=110e6 curves for P4096. Each stage-1 curve requires approximately 70 minutes with another 35 minutes for stage-2. If I had the ability to resume stage-1 (to recycle the curves) for the next level, it would save me an estimated 870 CPU days which is the time I'll be investing for the B1=110e6 stage-1 efforts.

Given that it is a fire and forget, I'm not certain what "hassle" would be involved in recycling curves from a previous level. What am I missing?
Jay is offline   Reply With Quote
Old 2007-12-28, 13:01   #7
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000002 Posts
Default

Doing the expected number of curves for an n-digit factor unsucessfully is not a proof of non-existence of a factor <= n digits at all! All it says is that if a factor of n digits exists, it should have been found with ~1-1/e probability. Since we usually use ECM to aim for factors well below the square root of the input number N, the probability that the remaining factors of N are somewhere above n digits is pretty high, but certainly not equal 1. It can and does happen that factors are found with higher B1 (or with NFS) after that factor's "correct" B1 level had the expected number of curves done. It's what we call an "ECM miss."

The hassle I'm talking about is storing and resuming the residue files, taking care not to resume the same file to the same increased B1 twice and all the book- and housekeeping that comes with it. In comparison, simply letting ECM choose a new random curve each time requires no attention on your part at all, except keeping track of the number of curves done to advance B1 at the right time.

Alex
akruppa is offline   Reply With Quote
Old 2007-12-28, 14:11   #8
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

157668 Posts
Default

Quote:
Originally Posted by Jay View Post
I'm not certain what "hassle" would be involved in recycling curves from a previous level. What am I missing?
Starting a new curve from scratch has a higher probability of finding a factor than "recycling" an old curve. I think Alex is saying this probability difference roughly negates your speed difference.
Prime95 is online now   Reply With Quote
Old 2007-12-28, 16:47   #9
Jay
 
Jay's Avatar
 
Dec 2007

1000102 Posts
Default

Quote:
Originally Posted by akruppa View Post
Doing the expected number of curves for an n-digit factor unsucessfully is not a proof of non-existence of a factor <= n digits at all!
My apologies for using incorrect wording.


Quote:
Originally Posted by akruppa View Post
The hassle I'm talking about is storing and resuming the residue files, taking care not to resume the same file to the same increased B1 twice and all the book- and housekeeping that comes with it. In comparison, simply letting ECM choose a new random curve each time requires no attention on your part at all, except keeping track of the number of curves done to advance B1 at the right time.
My doing B1=110e6 curves requires a wee bit more "hassle" than fire and forget. First I have to setup Prime95 stage-1 for some number of curves on my P4 box. Then monitor the box waiting for the box to finish. Once it finishes I then move the curves to my AMD box where I launch GmpEcm stage-2. Then back to the P4 box to start the next batch of curves. And given that it takes two P4 boxes to keep the AMD box busy, it is more than a wee bit of hassle. All in all, I'd rather have the ability to fire and forget a distributed server/client tool using GmpEcm with curve counting, automated level increase, ability to use Prime95 for stage-1 and GmpEcm for stage-2, along with the ability to intelligently decide which machine to do the work. I don't suppose you have one handy?

All in all, I expect a bit of "hassle" to get maximum efficiency from my boxes. And while my emperical testing a couple of years ago using recycled curves produced factors at the frequency I would expect, I will grant the possibility that recycled curves are not as efficient as non-recycled curves.

But darn it, all I want for Xmas is GmpEcm+GWnum under Win32!

My apologies for the inaccurate wording and the arise of a debate over the effectiveness over one potential usage of a stage-1 save capability. If a better justification is required in order to get someone to fix the problem with GmpEcm+GWnum under Win32, please advise me and I'll generate a list of reasons for approval.
Jay is offline   Reply With Quote
Old 2008-01-06, 22:52   #10
Jay
 
Jay's Avatar
 
Dec 2007

2·17 Posts
Default

With a lot of tinkering and trial/error, I've managed to get GmpEcm to build with GWnum under MinGW. It even reports (-v) that it is using GWnum.

gwnum_ecmStage1

It also appears to be able to save stage-1 results and then to resume using the saved results.

Note that I had to do the following to get it to build/work:
- - -
1. Use the mingw version of the GWnum library.
2. Build under MinGW (cygwin fails)
3. Rebuild one of the MinGW C files after getting errors during the GmpEcm make job.
4. Comment out the #define of ADD_UNDERSCORES in Fgw.c

All together, I'd estimate about 30-40 hours of tinkering and experimentation to get it to build/run.

If anyone else wants a Win32 P4 version of GmpEcm with GWnum active, let me know. I will probably end up making an AMD version as well, but it won't be until later in the week.
Jay is offline   Reply With Quote
Old 2008-01-11, 14:33   #11
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

25·7·11 Posts
Default

Sorry, I'm still busy hacking the new P+-1 stage 2. I'll fix the GWNUM interface before the next release.

Alex
akruppa is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Bug report v27.9 build 1 win32 PageFault Software 1 2014-05-13 20:27
How to get Wine/Yafu-Win32.exe to accept this expression? Stargate38 YAFU 8 2012-09-17 19:44
Prime95 for core2duo under Win32? ewmayer Software 8 2008-01-25 17:48
A64/Win32/gmp proggy paulunderwood Programming 16 2006-01-10 11:23
Small win32 program, range of time to do a TF dsouza123 Programming 1 2003-10-09 16:04

All times are UTC. The time now is 03:10.

Wed Nov 25 03:10:42 UTC 2020 up 76 days, 21 mins, 4 users, load averages: 1.71, 1.46, 1.36

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.