srsieve/sr2sieve enhancements

rogue · 2011-07-22, 13:46

I have made some enhancements to srsieve and sr2sieve that some of you would be interested in. I've forwarded these to Geoff, but haven't received a response yet.

I modified srsieve to remove numbers that have algebraic factorizations. Not only does it find those that hiddenpowers.pl (used primarily by CRUS) can find, but it can also find others. An example of that is when k = m^x*b^y and x > 1.

I also modified sr2sieve to output the removal rate of the most recent 30 factors rather than the removal rate since sr2sieve started. This allow one to specify a much larger value for -P, but then monitor the output to determine the when it gets to the optimal removal rate. I am considering adding a switch to sr2sieve to be used in conjunction with this change so that you can tell sr2sieve to terminate when the removal rate reaches a specified number of seconds. I am also interested in modifying sr2sieve to support .pfgw formatted input. I so no reason that it should not be able to support both .abcd and .pfgw input.

I'll make source code (and Windows builds) available to those who are interested.

mdettweiler · 2011-07-22, 16:14

I'm definitely interested! It's been a while since I've done much sieving with sr(x)sieve, having not had any 64-bit computers until recently, but now that I have a couple I may decide to volunteer for a CRUS sieving job or the like.

One of the things that I found particularly annoying before with sieving CRUS bases was removing algebraic factors; I tried to write a script for it on one or two occasions, though for some reason it never worked well and I always ended up just emailing the files to Gary for algebraic factor removal.

If you could email me the source and Windows builds at max@noprimeleftbehind.net, that would be great! Also, if you would be amenable, I can post them for download on the noprimeleftbehind.net website; I would imagine them being of great utility to other CRUS members as well.

rogue · 2011-07-22, 16:26

Quote:

Originally Posted by mdettweiler

I'm definitely interested! It's been a while since I've done much sieving with sr(x)sieve, having not had any 64-bit computers until recently, but now that I have a couple I may decide to volunteer for a CRUS sieving job or the like.

One of the things that I found particularly annoying before with sieving CRUS bases was removing algebraic factors; I tried to write a script for it on one or two occasions, though for some reason it never worked well and I always ended up just emailing the files to Gary for algebraic factor removal.

If you could email me the source and Windows builds at max@noprimeleftbehind.net, that would be great! Also, if you would be amenable, I can post them for download on the noprimeleftbehind.net website; I would imagine them being of great utility to other CRUS members as well.

I will most likely post them somewhere.

BTW, I will not modify sr2sieve to read pfgw formatted files at this time. It's harder than I thought it would be.

rogue · 2011-07-22, 19:00

I have posted srsieve (v 0.9.0) and sr2sieve (v 1.9.0).

Source and Win64 builds are included. I couldn't get a Win32 version to link.

I have not thoroughly tested my changes, but I expect any problems that come up to be easy to fix.

The removal rate feature is triggered with the -R option. You specify a parameter with the desired removal rate. When it reaches that rate, you will see this:

sr2sieve 1.9.0 stopped: at p=213382268591 because Removal rate reached.

and sr2sieve will shut down.

It should be possibly (theoretically) to have sr2sieve shut down automatically based upon a removal rate that it calculates internally based upon the range being sieved. I've thought about adding such a feature, but haven't thought enough about it.

ET_ · 2011-07-24, 08:06

Any plans to enhance ppsieve that actually complains with most file formats?
We just need a better sieve than fermfact at FermatSearch...

Luigi

rogue · 2011-07-24, 13:23

Quote:

Originally Posted by ET_

Any plans to enhance ppsieve that actually complains with most file formats?
We just need a better sieve than fermfact at FermatSearch...

Luigi

No plans, because I don't use those programs.

I wonder if fermfact could be ported to a GPU.

ET_ · 2011-07-25, 08:16

Quote:

Originally Posted by rogue

No plans, because I don't use those programs.

I wonder if fermfact could be ported to a GPU.

Thank you Mark.

I hope someone will try soon.

Luigi

rogue · 2011-11-23, 17:27

I've posted srsieve 1.0.0 here.

There was a problem with srfile in v0.9 because I started from a "dirty" copy of srsieve 0.6. That should now be fixed. srfile now supports factor remove from GFN sieve input/factor files.

rogue · 2012-01-10, 18:51

I've posted srsieve 1.0.1 here.

There was a bug in the algebraic factorization removal code which would cause it to remove the wrong n. Thanks to Batalov for pointing it out.

rogue · 2012-02-02, 21:50

I've posted srsieve 1.0.2 here.

I missed some other obvious factorizations. For example if c=-1 and k=x^6 for some integer x, then we know that when n%6=0 that k*b^n-1 is divisible by x*b^(n/6)-1, which is what v1.0.1 did. What we also know is that k=(x^2)^3, thus we can also conclude that when n%2=0 that k*b^n-1 is divisible by (x^2)*b^(n/2)-1.

rogue · 2012-02-10, 14:50

I've posted srsieve 1.0.3 here.

I realized after I posted 1.0.2 that I missed other algebraic factorizations, especially on the +1 side.

2011-07-22, 13:46	#1
rogue "Mark" Apr 2003 Between here and the 16060₈ Posts	srsieve/sr2sieve enhancements I have made some enhancements to srsieve and sr2sieve that some of you would be interested in. I've forwarded these to Geoff, but haven't received a response yet. I modified srsieve to remove numbers that have algebraic factorizations. Not only does it find those that hiddenpowers.pl (used primarily by CRUS) can find, but it can also find others. An example of that is when k = m^x*b^y and x > 1. I also modified sr2sieve to output the removal rate of the most recent 30 factors rather than the removal rate since sr2sieve started. This allow one to specify a much larger value for -P, but then monitor the output to determine the when it gets to the optimal removal rate. I am considering adding a switch to sr2sieve to be used in conjunction with this change so that you can tell sr2sieve to terminate when the removal rate reaches a specified number of seconds. I am also interested in modifying sr2sieve to support .pfgw formatted input. I so no reason that it should not be able to support both .abcd and .pfgw input. I'll make source code (and Windows builds) available to those who are interested.

2011-07-22, 19:00	#4
rogue "Mark" Apr 2003 Between here and the 1C30₁₆ Posts	I have posted srsieve (v 0.9.0) and sr2sieve (v 1.9.0). Source and Win64 builds are included. I couldn't get a Win32 version to link. I have not thoroughly tested my changes, but I expect any problems that come up to be easy to fix. The removal rate feature is triggered with the -R option. You specify a parameter with the desired removal rate. When it reaches that rate, you will see this: sr2sieve 1.9.0 stopped: at p=213382268591 because Removal rate reached. and sr2sieve will shut down. It should be possibly (theoretically) to have sr2sieve shut down automatically based upon a removal rate that it calculates internally based upon the range being sieved. I've thought about adding such a feature, but haven't thought enough about it. Last fiddled with by rogue on 2011-07-22 at 19:09

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Sieving twins with srsieve	henryzz	Twin Prime Search	0	2014-03-18 12:44
Intel announces multi-core enhancements for Haswell chips	ixfd64	Hardware	8	2012-02-10 20:32
LLRnet enhancements	kar_bon	No Prime Left Behind	10	2008-03-28 11:21
TODO list and suggestions/comments/enhancements	Greenbank	Octoproth Search	2	2006-12-03 17:28
Suggestions for future enhancements	Reboot It	Software	16	2003-10-17 01:31

2011-07-22, 16:14	#2
mdettweiler A Sunny Moo Aug 2007 USA 2²·11²·13 Posts	I'm definitely interested! It's been a while since I've done much sieving with sr(x)sieve, having not had any 64-bit computers until recently, but now that I have a couple I may decide to volunteer for a CRUS sieving job or the like. One of the things that I found particularly annoying before with sieving CRUS bases was removing algebraic factors; I tried to write a script for it on one or two occasions, though for some reason it never worked well and I always ended up just emailing the files to Gary for algebraic factor removal. If you could email me the source and Windows builds at max@noprimeleftbehind.net, that would be great! Also, if you would be amenable, I can post them for download on the noprimeleftbehind.net website; I would imagine them being of great utility to other CRUS members as well.

2011-07-24, 08:06	#5
ET_ Banned "Luigi" Aug 2002 Team Italia 1001011111101₂ Posts	Any plans to enhance ppsieve that actually complains with most file formats? We just need a better sieve than fermfact at FermatSearch... Luigi

2011-11-23, 17:27	#8
rogue "Mark" Apr 2003 Between here and the 1C30₁₆ Posts	I've posted srsieve 1.0.0 here. There was a problem with srfile in v0.9 because I started from a "dirty" copy of srsieve 0.6. That should now be fixed. srfile now supports factor remove from GFN sieve input/factor files.

2012-01-10, 18:51	#9
rogue "Mark" Apr 2003 Between here and the 2⁴·11·41 Posts	I've posted srsieve 1.0.1 here. There was a bug in the algebraic factorization removal code which would cause it to remove the wrong n. Thanks to Batalov for pointing it out.

2012-02-02, 21:50	#10
rogue "Mark" Apr 2003 Between here and the 1C30₁₆ Posts	I've posted srsieve 1.0.2 here. I missed some other obvious factorizations. For example if c=-1 and k=x^6 for some integer x, then we know that when n%6=0 that kb^n-1 is divisible by xb^(n/6)-1, which is what v1.0.1 did. What we also know is that k=(x^2)^3, thus we can also conclude that when n%2=0 that kb^n-1 is divisible by (x^2)b^(n/2)-1.

2012-02-10, 14:50	#11
rogue "Mark" Apr 2003 Between here and the 2⁴·11·41 Posts	I've posted srsieve 1.0.3 here. I realized after I posted 1.0.2 that I missed other algebraic factorizations, especially on the +1 side.