mersenneforum.org Updated polynomial selection
 Register FAQ Search Today's Posts Mark Forums Read

 2010-12-20, 01:04 #1 jasonp Tribal Bullet     Oct 2004 3,559 Posts Updated polynomial selection 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 Last fiddled with by jasonp on 2010-12-20 at 02:46
 2010-12-20, 08:11 #2 warut   Dec 2009 89 Posts 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: Code: 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: Code: 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?
2010-12-20, 11:54   #3
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

11001001101102 Posts

Quote:
 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

Last fiddled with by fivemack on 2010-12-20 at 11:56

 2010-12-20, 12:06 #4 warut   Dec 2009 89 Posts Thanks a lot, fivemack. So the new poly does have (slightly) higher score.
 2010-12-20, 12:06 #5 jasonp Tribal Bullet     Oct 2004 355910 Posts 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.
 2010-12-20, 14:25 #6 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 22×17×89 Posts Am I correct in thinking that while the old poly sieves faster more relations will be needed?
 2010-12-20, 17:54 #7 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 2×7×461 Posts 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 Last fiddled with by fivemack on 2010-12-20 at 17:57
 2010-12-20, 18:34 #8 jrk     May 2008 3·5·73 Posts Can you pinpoint which "poly ..." line occurred in the output just before the errors start?
 2010-12-20, 19:54 #9 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 25·132 Posts 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: Code: 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 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!
2010-12-20, 19:59   #10
warut

Dec 2009

8910 Posts

Quote:
 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.

2010-12-20, 20:26   #11
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

2×7×461 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Max0526 NFS@Home 9 2017-05-20 08:57 mhill12 Factoring 59 2013-09-09 22:40 pastcow Msieve 6 2013-05-08 09:01 fivemack Factoring 47 2009-06-16 00:24 CRGreathouse Factoring 2 2009-05-25 07:55

All times are UTC. The time now is 20:21.

Tue Mar 21 20:21:59 UTC 2023 up 215 days, 17:50, 0 users, load averages: 1.04, 0.91, 0.88