Msieve 1.41 Feedback

[Batalov]

non-issue. deleted

[Jeff Gilchrist]

Originally Posted by Joshua2

Yes, it will meet my needs, assumming qs is faster at 2^300, which is quite likely for now. Thanks for your work!

Ok 64bit Windows is up now:
http://gilchrist.ca/jeff/factoring/

Jeff.

[Batalov]

I decided to search for the gnfs/mpqs crossover point, and took a 296-bit number.

#1. Internal gnfs. If I change the
include/common.h:#define MIN_NFS_BITS 290
then
msieve -n 142636039930449499515055724706069369122952024169034908419840194033346894320140545970889557

Sat Apr  4 19:48:19 2009  Msieve v. 1.41
Sat Apr  4 19:48:19 2009  random seeds: e77abf51 a38032e2
Sat Apr  4 19:48:19 2009  factoring 142636039930449499515055724706069369122952024169034908419840194033346894320140545970889557 (90 digits)
Sat Apr  4 19:48:19 2009  searching for 15-digit factors
Sat Apr  4 19:48:20 2009  commencing number field sieve (90-digit input)
Sat Apr  4 19:48:20 2009  commencing number field sieve polynomial selection
Sat Apr  4 19:48:20 2009  time limit set to 0.16 hours
Sat Apr  4 19:48:20 2009  searching leading coefficients from 1 to 956

After 1.5 hours it is still searching for the poly. A bit of a problem here.
Why doesn't it switch to sieving? It has already found about >300,000 polys to choose from! (Hint: I am afraid that elapsed time is only checked in a large outer loop; maybe you may want to insert the secondary check deeper?)

#1a. External gnfs. But if course if we let factMsieve.pl to polyselect, it will use the degree 4 poly, which is the right thing to do.
Polynomial selection time: 0.17 hours.
Total sieving time: 0.81 hours.
total time: 1.02 hours.

#2. If we leave msieve as it is:
include/common.h:#define MIN_NFS_BITS 300
then mpqs and...
Sat Apr 4 19:43:39 2009 elapsed time 00:42:26

#3. Because it is actually a co-factor of 7*10^100+11, snfs takes 0:06:00 to factor. I earlier wrote and deleted a message as a non-issue (but it was an issue with <=1.39), because since 1.40, msieve works without a hitch with the factMsieve.pl script with a poly and -nc1, -nc2, -nc3. (I.e. it doesn't suddenly mpqs when the script already sieved enough and asks for filtering, BL and sqrt. I'd asked about that before - and it's working great. The limit doesn't come into play at all - you can run a snfs-50 if you want, I guess. Just call msieve to filter, BL and sqrt, not to sieve.) Thank you, Jason.

My only concern is #1. I will repeat now with a 301-bit number, to address the objection that 296-bit gnfs is irrelevant. The ~300-320 area is gray, and will need the msieve's internal degree 4 polyselect (which I already saw in the future plans).

So, in short, "you asked for it - you got it. Toyota." You asked for 300 bit limit, you got it. Will it work (completely standalone)? Before the degree-4 select, I doubt it... But it will work with the script!

The crossover is probably at 320, well, maybe, at 310 bits - and with a degree-4 poly.

Food for thought, not really a critique. --Serge

[FactorEyes]

Originally Posted by Batalov

So, in short, "you asked for it - you got it. Toyota."

Huh. I thought you were younger than that.

[jasonp]

Al: Those alpha values do look quite good, but my experience is that if you let the polynomial selection go for long enough you'll eventually find a polynomial with a Murphy E value that's 25-30% better than the cutoff used by the code, which for a C148 is 5.65e-12. The best polynomial in your list is 10% above the cutoff, so you're not quite there yet.

There's no fast way to tell early on how good an E value a given polynomial will have; there are less accurate but faster measures which will give a hint, but when the best poly appears it will be pretty much completely without warning. The polynomial optimization proceeds in two stages: the first optimizes the average polynomial size and the second optimizes the alpha value at the expense of the polynomial size. If a small modification to the poly dramatically improves the alpha, in excess of the increased average size, then the new polynomial is better. Msieve's alpha optimization is very powerful, but you have to watch out for polynomials that have extremely good alpha but only mediocre size. That's a sign that the best alpha value takes the polynomial too far away from it's original size-optimized form.

What you want is a good size and then a good alpha value that doesn't involve modifying the polynomial by much; I've done some experiments with the best polynomial found in Tom's poly search for 109!+1, and this is a good example. The search space for good alpha is really huge for numbers this big, and Msieve finds mediocre polynomials with outstanding alpha values because it looks far away from the initial polynomial found. But the poly used in the sieving is quite special: its size is very good but a tiny correction leads to an alpha which is also very good. The combination makes it the best choice by far.

@Joshua: for small loops like this, which are not time-critical, my decision process tries to optimize readability. Your modified code has an inline variable declaration which requires a C99-compliant compiler (MSVC would complain, which half the userbase uses). So you'd need another variable declaration further up in the code. Also, there are many places in the source which require 'looking ahead' by half an iteration, and I find it easier to keep track of the final value of variables when they are all updated in lockstep but the loop possibly ends early. It's a stylistic thing, no big deal. The admonition to avoid break statements is a good idea in general but is really only important for more extensive looping constructs than this 5-liner.

The hard-coded sieve size is just to have a number available that's not too small, that sieve is not critical to performance.

@Serge: the big problem is that you're using 98-digit parameters during the poly search, and these are much too permissive for an input that small. But you're correct that I need more deadline checks. If Kleinjung-style polynomials cut the sieving time in half, then even a 296-bit input would be faster using GNFS.

[Joshua2]

Msieve 1.41 was chugging along nicely and only going to take a few minutes, and now it is over 100% done with a bazillion hours left to go.

[Joshua2]

Now its taking over the cmd :)

[Batalov]

Kill it before it takes over the whole computer. :-)

If you are not OC'ing: Try the linear algebra again -- maybe you were unlucky (some initial vectors do not converge, this is very rare)...

Then, if it does the same again, stress-test the computer. (I mean stress it differently - msieve already stress-tested it and the computer didn't pass. Even not OC'd computers need tuning; and if it is OC'd then it surely means you have to go lower.) Prime95, memtest, linpack...
____________

P.S. Then you got the same answer as I have. msieve test the computer harder than other programs. I RMA'd half of the memory, and the symptoms went away. See here -
http://mersenneforum.org/showthread....932#post165932

[Joshua2]

I did try again and it did the same thing. I redid it w/ threads = 2 instead of 3 and then it worked. I am overclocking, but its memtest and p95 stable, and I've been running it 24-7 for months and don't have problems normally, so maybe msieve doesn't support 3 threads only 1,2, & 4?

[jasonp]

I see Serge's new avatar and think " 'at's a paddlin' ". We've already determined over email that his new machine had memory problems when running msieve and not other programs. Prime95 accesses data in much more predictable patterns and make much better use of cache than msieve does (or can, really), so I can see multithreaded msieve hitting the system bus very hard with mostly-random read patterns, and with enough threads you might cause marginally-timed memory to misbehave. I'm not ruling out a multithreading bug, though.

Boy, I hope that means the overclockers don't use msieve for a stress test. That would expand the userbase by a factor of 1000, which there's no way I can handle.

[Joshua2]

It seems fishy that I got the same thing twice in a row w/ 3 threads and not 2, maybe I'll try w/ 4. I could try completely starting over w/ 3 as well. I could recommend msieve to overclockers if you wish, since I have a little weight in that area :).