Msieve 1.41 Feedback

[jasonp]

Originally Posted by Joshua2

I could recommend msieve to overclockers if you wish, since I have a little weight in that area :).

Can I refer them to you when they have trouble compiling or running it?

Anyway, there are better stress tests to use than msieve's linear algebra. You'd need maybe 2GB of relations to get a matrix big enough that multithreaded linear algebra would really push the computer.

[Joshua2]

Or a couple mb c116 as the case may be... I'm rerunning the number w/ 4 threads and 3 again.

[Joshua2]

My comp crashed completely doing a 3 thread on a different number, so I am not going to do 3 thread anymore, maybe it is more demanding on my computer or something, but if so its the only thing to do it; sticking to 2 or 4 threads. I would be curious for someone else to try 3 threads.

Request for msieve 1.42. If poly search is interrupted, parse dat and continue where left off or maybe periodically write a resume.txt file?

[Batalov]

Anyway, carrying on.

A 311-bit gnfs (94-digits) came across my way (not a synthetic one this time, so no snfs timings here). (Why did the chicken crossed the road? I missed one? --Col.Sanders)

1. gnfs with polyselect's poly:
Pruned matrix : 158994 x 159221
Polynomial selection time: 0.17 hours.
Total sieving time: 1.55 hours.
Total relation processing time: 0.02 hours.
Matrix solve time: 0.07 hours.
Time per square root: 0.01 hours.
Prototype def-par.txt line would be:
gnfs,93,4,maxs1,maxskew,goodScore,efrac,j0,j1,eStepSize,maxTime,1200000,1200000,25,25,45,45,2.4,2.4,60000
total time: 1.82 hours.

1a. gnfs with msieve's poly:
select overshot (wanted 0.20hr; but selected for 0.5hr, then went on with line sieving)
but the poly was worth the wait.
Pruned matrix : 106941 x 107182
Total sieving time: 1.00 hours.
Total relation processing time: 0.02 hours.
Matrix solve time: 0.06 hours.
Time per square root: 0.05 hours.
total time: 1.62 hours.

2. mpqs: elapsed time 02:14:47

So, indeed, 300-bit crossover is about right (if 'poly selecting' timing wrinkles are wrought out; it's not every time that I am willing to manually kill and restart). Maybe 305. Something like that. 310 is a gnfs, for sure.

[10metreh]

I just managed to pull an alpha of -6.97 - for a C96!

# norm 3.822211e-009 alpha -6.971967 e 5.049e-009
skew: 51426.51
c0: -69033111193775871035463760
c1: -3261252325389808139474
c2:  166526905095679941
c3: -44875833436
c4: -13205336
c5:  480
Y0: -3360076126620220941
Y1:  12435222503

It was also one of three polys with e's around 5.05, and this one sieved the best out of the three. Normally there's one poly way above the rest, this time it was three!

[Andi47]

goto...

Back to topic:
For small GNFS numbers (below ~94 digits I think), the criteria for good polynomials to save are far too loose: I tried to GNFS a c91 and it ended up saving boatloads of polynomials (the "save..." lines kept scrolling over the screen), so that the saving process seemingly became the bottleneck and sloooowwwwwed down the poly search process. I stopped it after ~two hours (in the beginning it said to have a time limit of 0.14 hours) and found a msieve.dat.p file with a size of 4.1 MB.

[jasonp]

Well, since there are so many aliquot sievers that are keen on small GNFS jobs I guess the top priority should be getting those degree-4 polynomials running and properly tuned. Please be gentle when the first beta comes out, though.

[Joshua2]

Where do the time to poly search for each digit, and the time to spend on each coefficient come from? Have they been tested to be close to optimal? I wouldn't mind spending some cpu time testing for this, it seems a special binary could be made that timed how much better poly's got w/ extra time.

[jasonp]

Originally Posted by Joshua2

Where do the time to poly search for each digit, and the time to spend on each coefficient come from? Have they been tested to be close to optimal? I wouldn't mind spending some cpu time testing for this, it seems a special binary could be made that timed how much better poly's got w/ extra time.

I basically started by estimating how long the sieving should take, then chose the poly search time to be about 3-5% of that. Obviously it's a moving target (better sieving speed should reduce the poly search time), and for the largest input sizes the time limit (a few hundred hours) is grossly too small, but it's better than nothing. The overall search deadline code is in gnfs/poly/poly.c and the per-coefficient search deadlines are in gnfs/poly/stage1/stage1.c

Basically stage 1 should be designed to generate as many candidates as possible to feed to stage 2, but you have to balance the need to drill deeply into one coefficient against the possibility that you won't find anything good there no matter how long you look, and so need to have time to examine other coefficients too.

The notion of optimality is difficult to apply here; NFS poly selection is a combinatorial optimization problem, and the search space is much too large to have any hope of getting completely explored. Certainly if you search for much too long you will get diminishing returns, in that the very best polynomials are rare to nonexistent. Kleinjung's 2006 GNFS polynomial search paper shows that the search time should be a polynomial power of the amount of improvement you should expect, but that doesn't say much about the constant factors implicit in the search process.

By the way, I think there are many unexplored frontiers in NFS poly selection, and I really appreciate the interest you have in the code.

[Joshua2]

Right, it was looking at the code in that I saw those two spots I saw "magic numbers", which aren't the best, and normally not optimal.

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.

[bsquared]

Originally Posted by Batalov

Anyway, carrying on.

...

So, indeed, 300-bit crossover is about right (if 'poly selecting' timing wrinkles are wrought out; it's not every time that I am willing to manually kill and restart). Maybe 305. Something like that. 310 is a gnfs, for sure.

I'm not so sure... I just did a C95 (315 bits) comparison, although granted with a different QS routine, and found

a) msieve poly (non-optimal degree 5) for 20min followed by 1hr 12min of lasieveI12e (asm optimized 64 bit version) sieving for a total of ~5500 sec.

b) QS for 6100 sec.

Granted we are quibbling over a handful of bits, but I'd put the crossover at slightly over 310 bits, if on a core2 and using yafu for the QS.

Of course this will be pushed lower once we see better deg 4 poly selection.

- ben.