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.

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. :smile: 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. :rolleyes:

If you could email me the source and Windows builds at [email]max@noprimeleftbehind.net[/email], 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.

[QUOTE=mdettweiler;267275]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. :smile: 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. :rolleyes:

If you could email me the source and Windows builds at [email]max@noprimeleftbehind.net[/email], 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.[/QUOTE]

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.

I have posted [URL="home.roadrunner.com/~mrodenkirch/srsieve_0.9.0.zip"]srsieve[/URL] (v 0.9.0) and [URL="home.roadrunner.com/~mrodenkirch/sr2sieve_1.9.0.zip"]sr2sieve[/URL] (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.

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

Luigi

[QUOTE=ET_;267397]Any plans to enhance ppsieve that actually complains with most file formats?
We just need a better sieve than fermfact at FermatSearch... :smile:

Luigi[/QUOTE]

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

I wonder if fermfact could be ported to a GPU.

[QUOTE=rogue;267407]No plans, because I don't use those programs.

I wonder if fermfact could be ported to a GPU.[/QUOTE]

Thank you Mark.

I hope someone will try soon.

Luigi

I've posted srsieve 1.0.0 [URL="http://home.roadrunner.com/~mrodenkirch/srsieve_1.0.0.zip"]here[/URL].

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.

I've posted srsieve 1.0.1 [URL="http://home.roadrunner.com/~mrodenkirch/srsieve_1.0.1.zip"]here[/URL].

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.

I've posted srsieve 1.0.2 [URL="http://home.roadrunner.com/~mrodenkirch/srsieve_1.0.2.zip"]here[/URL].

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.

I've posted srsieve 1.0.3 [URL="http://home.roadrunner.com/~mrodenkirch/srsieve_1.0.3.zip"]here[/URL].

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