mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2010-12-20, 01:04   #1
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

DCE16 Posts
Default 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
jasonp is offline   Reply With Quote
Old 2010-12-20, 08:11   #2
warut
 
Dec 2009

5916 Posts
Default

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?
warut is offline   Reply With Quote
Old 2010-12-20, 11:54   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

7×911 Posts
Default

Quote:
Originally Posted by warut View Post
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
fivemack is offline   Reply With Quote
Old 2010-12-20, 12:06   #4
warut
 
Dec 2009

89 Posts
Default

Thanks a lot, fivemack. So the new poly does have (slightly) higher score.
warut is offline   Reply With Quote
Old 2010-12-20, 12:06   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·3·19·31 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2010-12-20, 14:25   #6
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

132428 Posts
Default

Am I correct in thinking that while the old poly sieves faster more relations will be needed?
henryzz is offline   Reply With Quote
Old 2010-12-20, 17:54   #7
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

7×911 Posts
Default

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
fivemack is offline   Reply With Quote
Old 2010-12-20, 18:34   #8
jrk
 
jrk's Avatar
 
May 2008

3·5·73 Posts
Default

Can you pinpoint which "poly ..." line occurred in the output just before the errors start?
jrk is offline   Reply With Quote
Old 2010-12-20, 19:54   #9
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

3,541 Posts
Default

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'
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!
EdH is offline   Reply With Quote
Old 2010-12-20, 19:59   #10
warut
 
Dec 2009

89 Posts
Default

Quote:
Originally Posted by henryzz View Post
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.
warut is offline   Reply With Quote
Old 2010-12-20, 20:26   #11
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

637710 Posts
Default

Quote:
Originally Posted by jrk View Post
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.
fivemack is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Polynomial selection Max0526 NFS@Home 9 2017-05-20 08:57
SNFS Polynomial selection help? mhill12 Factoring 59 2013-09-09 22:40
Best way to scale polynomial selection pastcow Msieve 6 2013-05-08 09:01
2^877-1 polynomial selection fivemack Factoring 47 2009-06-16 00:24
Polynomial selection CRGreathouse Factoring 2 2009-05-25 07:55

All times are UTC. The time now is 17:37.

Wed Jan 20 17:37:46 UTC 2021 up 48 days, 13:49, 0 users, load averages: 3.11, 3.64, 3.69

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.