20101220, 01:04  #1 
Tribal Bullet
Oct 2004
5×23×31 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 thankyou 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 20101220 at 02:46 
20101220, 08:11  #2 
Dec 2009
1011001_{2} Posts 
Using Brian Gladman's Python script, I've tried the new polynomial selection with C115 of 853390763^191, 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 Code:
n: 9551072875938262304486593334816771187329752005031462161545434825603587474408505215553133278114605492157569894892067 Y0: 15178162685427585924659 Y1: 1652140724723 c0: 1521018887598232812117246912 c1: 110979613016546817143630 c2: 15859705167401022125 c3: 126276461899812 c4: 4502151340 c5: 11856 skew: 56748.63 BTW, is it possible to use msieve to compute the Murphy E score for a given poly? If so, how? 
20101220, 11:54  #3  
(loop (#_fork))
Feb 2006
Cambridge, England
2·7·461 Posts 
Quote:
OLD skew 259311.10, size 4.694e11, alpha 6.986, combined = 4.965e10 rroots = 3 NEW skew 56748.63, size 4.781e11, alpha 5.740, combined = 5.044e10 rroots = 5 Last fiddled with by fivemack on 20101220 at 11:56 

20101220, 12:06  #4 
Dec 2009
89 Posts 
Thanks a lot, fivemack. So the new poly does have (slightly) higher score.

20101220, 12:06  #5 
Tribal Bullet
Oct 2004
6755_{8} 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.

20101220, 14:25  #6 
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
11·557 Posts 
Am I correct in thinking that while the old poly sieves faster more relations will be needed?

20101220, 17:54  #7 
(loop (#_fork))
Feb 2006
Cambridge, England
2×7×461 Posts 
I'm getting about a thousand 'algebraic poly rootfinder failed' messages per CPUminute 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 20101220 at 17:57 
20101220, 18:34  #8 
May 2008
3·5·73 Posts 
Can you pinpoint which "poly ..." line occurred in the output just before the errors start?

20101220, 19:54  #9 
"Ed Hall"
Dec 2009
Adirondack Mtns
5522_{10} 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 <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' 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! 
20101220, 19:59  #10 
Dec 2009
89 Posts 

20101220, 20:26  #11 
(loop (#_fork))
Feb 2006
Cambridge, England
2×7×461 Posts 
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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Polynomial selection  Max0526  NFS@Home  9  20170520 08:57 
SNFS Polynomial selection help?  mhill12  Factoring  59  20130909 22:40 
Best way to scale polynomial selection  pastcow  Msieve  6  20130508 09:01 
2^8771 polynomial selection  fivemack  Factoring  47  20090616 00:24 
Polynomial selection  CRGreathouse  Factoring  2  20090525 07:55 