Updated polynomial selection

[jasonp]

Yesterday I merged the 'specialq' branch into the main trunk on sourceforge. This implements a huge overhaul of the NFS polynomial selection, including adding advanced hashtable optimizations to the CPU part of stage 1. This means that with proper tuning, stage 1 should run enormously faster on CPUs. For the GPU side, there's been a major shakeup that unifies many different code branches, and reduces the number of GPU kernels to just two, which are identical if compiling for Fermi cards. The GPU changes are a work in progress, and right now I don't think the GPU branch runs appreciably faster than it used to. It's also not clear anymore if the GPU code is faster than the CPU code, though right now it is for larger input numbers.

I'll post a win32 binary on my web page this evening if anyone feels brave and wants to run a few tests. Once any obvious problems are resolved, I'll release v1.48

Finally, I owe jrk a giant thank-you for doing a great deal of the heavy lifting needed to get this overhaul pushed out.

PS: Updated binary is here

[warut]

Using Brian Gladman's Python script, I've tried the new polynomial selection with C115 of 853390763^19-1, expecting to find a better poly than the one I already got with the previous version of msieve.

Old version's poly:

n: 9551072875938262304486593334816771187329752005031462161545434825603587474408505215553133278114605492157569894892067
Y0: -23764701888807470200558
Y1: 1077696796021
c0: -103280087432301204251345515405
c1: -6833889584608490000770522
c2: -23217580812937173900
c3: -158513170378474
c4: 1264211441
c5: 1260
skew: 259311.10

New version's poly:

n: 9551072875938262304486593334816771187329752005031462161545434825603587474408505215553133278114605492157569894892067
Y0: -15178162685427585924659
Y1: 1652140724723
c0: 1521018887598232812117246912
c1: 110979613016546817143630
c2: -15859705167401022125
c3: 126276461899812
c4: 4502151340
c5: 11856
skew: 56748.63

To my surprise, the former poly could be sieved faster (about 0.024 vs 0.028 sec/rel on a P4). The Murphy E score of the latter is 5.044e-010. I didn't record the former's score.

BTW, is it possible to use msieve to compute the Murphy E score for a given poly? If so, how?

[fivemack]

Originally Posted by warut

BTW, is it possible to use msieve to compute the Murphy E score for a given poly? If so, how?

Just put the polynomial into msieve.fb in msieve format and run msieve -v -nc (make sure you've got the skew right, and for some reason the skew line should be at the beginning of the file and is missed out if you put it after the polynomial), and the E-score turns up on the first output line. In your case:

OLD skew 259311.10, size 4.694e-11, alpha -6.986, combined = 4.965e-10 rroots = 3
NEW skew 56748.63, size 4.781e-11, alpha -5.740, combined = 5.044e-10 rroots = 5

[warut]

Thanks a lot, fivemack. So the new poly does have (slightly) higher score.

[jasonp]

The SKEW line is missed unless it comes early, because any line starting with an S after the polynomial is assumed to be a sieve parameter by the sieve code. i.e. the reason is silly.

[henryzz]

Am I correct in thinking that while the old poly sieves faster more relations will be needed?

[fivemack]

I'm getting about a thousand 'algebraic poly rootfinder failed' messages per CPU-minute when running

msieve -v -np 1,999

on the number

696005113603274146249087406461080151837868785491046290335993731206770181299351306725449365913668810065423694108036416675915143109

It's not a serious problem, it just means I need to run the jobs on a disc with more than 1G of free space if I'm leaving them overnight

[jrk]

Can you pinpoint which "poly ..." line occurred in the output just before the errors start?

[EdH]

How very disappointing!

I have two WinXP machines, both running AliWin/Aliqueit. The new version seems to run fine on one of them, but the other won't write/find the 'test.poly' file:

poly  0 139 11299 22123 44776444492026615606
special q: 9 entries, 9 roots
hashtable: 348 entries,  0.14 MB
coeff 4104 specialq 229 - 229 other 11177 - 22354
aprogs: 983 entries, 1179 roots
hashtable: 0 entries,  0.14 MB
polynomial selection complete
error generating or reading NFS polynomials
elapsed time 00:01:32
-> Computing 1.29286e+09 scale for this machine...
-> procrels -speedtest> PIPE
Scaled time: 461550109.79 units (timescale= 0.357).
Traceback (most recent call last):
  File "/Mathwork/aliqueit/factmsieve.py", line 2032, in <module>
    output_summary(NAME, fact_p, pols_p, poly_p, lats_p)
  File "/Mathwork/aliqueit/factmsieve.py", line 1887, in output_summary
    with open(NAME + '.poly', 'r') as in_f:
IOError: [Errno 2] No such file or directory: 'test.poly'

Three tries all resulted the same. Of note, I have seen this on a rare occasion, possibly on this same machine, but, it always worked on a subsequent run.

Also, the elapsed time was quite a bit longer than what is shown.

I just thought of this, in case it's of interest. The failing system is working on a c102, while the working system is running a c97.

Thanks for any advice. . . and for all the work you put into this!

[warut]

Originally Posted by henryzz

Am I correct in thinking that while the old poly sieves faster more relations will be needed?

Maybe. But since the estimated minimum relations needed is sufficient, the sieving speed determines the overall speed.

[fivemack]

Originally Posted by jrk

Can you pinpoint which "poly ..." line occurred in the output just before the errors start?

I think this is probably some kind of compilation issue, I'm running the same jobs on my iMac and seeing not a single error. Will send you output from the misbehaving runs tomorrow.