Msieve 1.41 Feedback - Page 4

jasonp · 2009-04-07, 13:50

Quote:

Originally Posted by Joshua2

I was wondering how to tell what range to resume the poly search w/? Look in the .fb log file for the largest c5 and go from there to how high it was going to do? The c5 that is highest for me isn't quite at the bottom which is weird, but its close. It would be nice if this was simpler or even automatic.

You'd have to encode the bounds of the range currently being searched in a savefile; the library deals with batches of up to 50 a5 values at a time to reduce overhead, and there's a lot of searching within each one that you don't want to cut short.

mdettweiler · 2009-04-07, 18:26

Today I've had msieve v1.41 (this also happens with 1.40) crash repeatedly on a 32-bit Windows XP system. The only error information I got was simply "msieve.exe has encountered a problem and needs to close" from Windows--no error message at all from msieve.

The crash occurs whenever I try to run NFS sieving or postprocessing (whether via factMsieve.pl, or manually). Interestingly enough, though, it works just fine with polynomial selection. I simply get "commencing number field sieve <111 digit input>" and the program exits silently immediately after that.

Interestingly enough, version 1.39 works just fine for all of the same situations in which 1.40 and 1.41 produced an error. I'm using the posted binaries for all of them; for 1.40 I was using beta 2, but since it still occurred in 1.41 I doubt this problem is local to the 1.40 beta.

Has anyone else had this problem?

Joshua2 · 2009-04-07, 18:39

Well it may be that it is an extremely stressful program, since I had a number that wouldn't stop in the linear algebra stage and just kept on going past 100%. Also I had another number crash my computer, but those were only when threads was set to 3.

mdettweiler · 2009-04-07, 18:44

Quote:

Originally Posted by Joshua2

Well it may be that it is an extremely stressful program, since I had a number that wouldn't stop in the linear algebra stage and just kept on going past 100%. Also I had another number crash my computer, but those were only when threads was set to 3.

I doubt that the problem is due to system stress; after all, version 1.39 works without a problem. Plus, none of this is specifically in the linear algebra stage--I got the exact same error both when starting NFS sieving (-ns) and NFS filtering (-nc1). I didn't try it for linear algebra (-nc2) or square root (-nc3), though I would presume that it may very well produce the same error for them, too.

10metreh · 2009-04-07, 18:47

Quote:

Originally Posted by mdettweiler

Today I've had msieve v1.41 (this also happens with 1.40) crash repeatedly on a 32-bit Windows XP system. The only error information I got was simply "msieve.exe has encountered a problem and needs to close" from Windows--no error message at all from msieve.

The crash occurs whenever I try to run NFS sieving or postprocessing (whether via factMsieve.pl, or manually). Interestingly enough, though, it works just fine with polynomial selection. I simply get "commencing number field sieve <111 digit input>" and the program exits silently immediately after that.

Interestingly enough, version 1.39 works just fine for all of the same situations in which 1.40 and 1.41 produced an error. I'm using the posted binaries for all of them; for 1.40 I was using beta 2, but since it still occurred in 1.41 I doubt this problem is local to the 1.40 beta.

Has anyone else had this problem?

Once I had a similar problem with 1.38. When the Lanczos started, it wrote something like "memory use: 52.3 MB" and crashed. That bug was fixed in 1.39.

mdettweiler · 2009-04-07, 18:49

Quote:

Originally Posted by 10metreh

Once I had a similar problem with 1.38. When the Lanczos started, it wrote something like "memory use: 52.3 MB" and crashed. That bug was fixed in 1.39.

Hmm...interesting. However, this time it was doing filtering (didn't even get the chance to start Lanczos). Probably a different bug, even though the symptoms are somewhat similar (though that can be mostly attributed to the fact that neither error produced any helpful error messages).

jasonp · 2009-04-07, 19:12

This is something that's starting to appear depressingly often. When running msieve for anything except the polynomial selection the first thing the library tries is to rate the NFS polynomial, and if you are doing certain SNFS jobs there appears to be a numerical instability in the code that does the polynomial rating, which causes a crash. FactorEyes was the first to report it, and the code in question was added in v1.40; v1.41 has a partial fix but I'll have to do better.

10metreh · 2009-04-07, 19:17

Quote:

Originally Posted by jasonp

When running msieve for anything except the polynomial selection the first thing the library tries is to rate the NFS polynomial

I thought it tried trial division first!

Andi47 · 2009-04-07, 19:23

Quote:

Originally Posted by jasonp

This is something that's starting to appear depressingly often. When running msieve for anything except the polynomial selection the first thing the library tries is to rate the NFS polynomial, and if you are doing certain SNFS jobs there appears to be a numerical instability in the code that does the polynomial rating, which causes a crash. FactorEyes was the first to report it, and the code in question was added in v1.40; v1.41 has a partial fix but I'll have to do better.

Is it possible that the numerical instability is related to the "Integrator failed" errors during poly selection, which do still occur in 1.41?

Joshua2 · 2009-04-07, 20:22

I get integrator failed more often than the save lines on some numbers, I assumed it was normal. What does it really mean?

jasonp · 2009-04-07, 21:13

10metreh: I was insufficiently precise; the first thing the NFS code tries is rating the polynomial

The 'integration failed' messages don't have anything to do with these crashes. The crash occurs because you have to find the (floating point) roots of the algebraic polynomial in order to set up the numerical integration, and unfortunately it's impossible to build a polynomial rootfinder that is simultaneously

- capable of finding complex roots
- bulletproof regardless of the polynomial coefficients
- less than 1000 lines of code that started life as a crappy Fortran program

The code in the library uses Laguerre's method from Numerical Recipes and is pretty simple, but fails once in a while and produces nonsensical roots, which cause the integrator to crash. It seems to fail more often for SNFS polynomials. For bulletproof rootfinders, the best choice is the Jenkins-Traub model, which is 1000 lines of horrible C. Any volunteers want to convert the source to use quadruple-precision arithmetic, which is also needed to avoid most numerical integration failures?

I don't either, so the rootfinder needs a bulletproof method for approximating complex roots to enough accuracy that Laguerre's method is guaranteed to converge. Perhaps a continuation algorithm is needed.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Msieve 1.53 feedback	xilman	Msieve	149	2018-11-12 06:37
Msieve 1.50 feedback	firejuggler	Msieve	99	2013-02-17 11:53
Msieve v1.48 feedback	Jeff Gilchrist	Msieve	48	2011-06-10 18:18
Msieve 1.43 feedback	Jeff Gilchrist	Msieve	47	2009-11-24 15:53
Msieve 1.42 feedback	Andi47	Msieve	167	2009-10-18 19:37

2009-04-07, 18:26	#35
mdettweiler A Sunny Moo Aug 2007 USA (GMT-5) 3·2,083 Posts	Today I've had msieve v1.41 (this also happens with 1.40) crash repeatedly on a 32-bit Windows XP system. The only error information I got was simply "msieve.exe has encountered a problem and needs to close" from Windows--no error message at all from msieve. The crash occurs whenever I try to run NFS sieving or postprocessing (whether via factMsieve.pl, or manually). Interestingly enough, though, it works just fine with polynomial selection. I simply get "commencing number field sieve <111 digit input>" and the program exits silently immediately after that. Interestingly enough, version 1.39 works just fine for all of the same situations in which 1.40 and 1.41 produced an error. I'm using the posted binaries for all of them; for 1.40 I was using beta 2, but since it still occurred in 1.41 I doubt this problem is local to the 1.40 beta. Has anyone else had this problem?

2009-04-07, 18:39	#36
Joshua2 Sep 2004 13×41 Posts	Well it may be that it is an extremely stressful program, since I had a number that wouldn't stop in the linear algebra stage and just kept on going past 100%. Also I had another number crash my computer, but those were only when threads was set to 3.

2009-04-07, 19:12	#40
jasonp Tribal Bullet Oct 2004 3,541 Posts	This is something that's starting to appear depressingly often. When running msieve for anything except the polynomial selection the first thing the library tries is to rate the NFS polynomial, and if you are doing certain SNFS jobs there appears to be a numerical instability in the code that does the polynomial rating, which causes a crash. FactorEyes was the first to report it, and the code in question was added in v1.40; v1.41 has a partial fix but I'll have to do better.

2009-04-07, 20:22	#43
Joshua2 Sep 2004 13·41 Posts	I get integrator failed more often than the save lines on some numbers, I assumed it was normal. What does it really mean?

2009-04-07, 21:13	#44
jasonp Tribal Bullet Oct 2004 3,541 Posts	10metreh: I was insufficiently precise; the first thing the NFS code tries is rating the polynomial The 'integration failed' messages don't have anything to do with these crashes. The crash occurs because you have to find the (floating point) roots of the algebraic polynomial in order to set up the numerical integration, and unfortunately it's impossible to build a polynomial rootfinder that is simultaneously - capable of finding complex roots - bulletproof regardless of the polynomial coefficients - less than 1000 lines of code that started life as a crappy Fortran program The code in the library uses Laguerre's method from Numerical Recipes and is pretty simple, but fails once in a while and produces nonsensical roots, which cause the integrator to crash. It seems to fail more often for SNFS polynomials. For bulletproof rootfinders, the best choice is the Jenkins-Traub model, which is 1000 lines of horrible C. Any volunteers want to convert the source to use quadruple-precision arithmetic, which is also needed to avoid most numerical integration failures? I don't either, so the rootfinder needs a bulletproof method for approximating complex roots to enough accuracy that Laguerre's method is guaranteed to converge. Perhaps a continuation algorithm is needed.