gwnum under Win32

[Jay]

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]

Originally Posted by Jay

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.

[henryzz]

why bother

[Jay]

Originally Posted by henryzz

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.

[akruppa]

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

[Jay]

Originally Posted by akruppa

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?

[akruppa]

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

[Prime95]

Originally Posted by Jay

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.

[Jay]

Originally Posted by akruppa

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.

Originally Posted by akruppa

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]

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.

[akruppa]

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

Alex