A multiple k/c sieve for Sierpinski/Riesel problems

[axn]

Originally Posted by masser

I worked a little on something similar this week. For all of the Sierpinski k's that haven't been tested to n=100000 (35 sequences), I ran Geoff's siever up to the current sieve limit. I'm including the file here - I'm going to test from 56000 to 60000. There are only 15000 candidates; as a group we could probably test these values fairly quickly. Maybe we should start a new thread to do n-range reservations....

I put up something (upto n < 80,000). I've removed the k's that geoff has reserved. Will put up more when the ranges get finished.

EDIT:- Meanwhile, the sieve is currently at p=1.1 billion

[geoff]

Thanks for all the feedback.

I have posted a new version, but I haven't been online since I posted version 0.0.1 and so I haven't addressed any of the bugs or suggestions above, but I will look at them over the next few days.

Version 0.0.3 has 64 bit arithmetic which takes over once the 32 bit limit is reached, but it currently uses GMP to do the 64 bit mulmod which is quite slow. A new file format is used which writes all candidates in one file: use the --newpgen switch to write NewPGen format files to pass to prp.

Note that I only have 32 bit Intel machines running Linux, so any help getting it to work and tested on other platforms will be much appreciated.

Also note that this is a very early development version, and I am still learning as I go, so there may well be serious bugs. I wouldn't put 100% trust in the results unless they agree with NewPGen's.

[geoff]

Originally Posted by axn1

REQUEST#2:- Geoff, can your program handle both + & - sieve simultaneously. If not, can you modify it to do so?

It already handles both +1 and -1 candidates together in the same sieve. For candidate sequences k*b^n+c the only restrictions are: each k must be positive and relatively prime to b; b must be >= 2; c must be +1 or -1.

For those interested in the algorithm, that main improvement compared to sieving one candidate sequence at a time is that the baby steps part of the algorithm is independent of the number of candidates in the sieve, and increasing the number of (cheap) baby steps allows the number of (expensive) giant steps to be reduced.

I think the speed is mainly proportional to sqrt(kn), where k is the number of candidate sequences and n the range of n values. For sieving one candidate at a time las we have been doing, speed is proportional to k sqrt(n).

[axn]

Originally Posted by geoff

Also note that this is a very early development version, and I am still learning as I go, so there may well be serious bugs. I wouldn't put 100% trust in the results unless they agree with NewPGen's.

I am currently running it with the -c option -- that should act as check against erroneous factors. If it doesn't find a few factors here and there, I am not too bothered.

[geoff]

This version fixes the next_bit() segfault bug and implements the hash function improvements reported by rogue. Also simple timing information is reported (--report option).

I will work on a proper benchmarking suite so that we can measure the effects of changes ant test out different compile time parameters.

Originally Posted by axn1

I am currently running it with the -c option -- that should act as check against erroneous factors. If it doesn't find a few factors here and there, I am not too bothered.

The --check option checks that no non factors are written to the screen or to the --factors file, but it can't check against things like bitmap corruption. To be sure there are no candidate n eliminated that shouldn't have been it would be necessary to check that every n missing from the final sieve file is accounted for by a factor in the --factors file.

Nevertheless it should be fine to use it now to help eliminate as many candidate k as possible, but when we start combined sieving with a stable version we should consider restarting whatever k are left from scratch.

[axn]

Originally Posted by geoff

Nevertheless it should be fine to use it now to help eliminate as many candidate k as possible, but when we start combined sieving with a stable version we should consider restarting whatever k are left from scratch.

Since I currently have all the factors > 100000 in the file, all we need to doublecheck is to redo the sieve till p < 100000 and we can quickly check if the totals tally.

[jasong]

Just so you guys know, the guy working on the new sieve client(not the one in this thread) does intend to make it base-5 compatible. When that will actually happen, I don't know, but it's in the works.

Mildly off-topic: I've been told that the resulting code will even be portable to the Playstation Portable. Woo-hoo!!!

[rogue]

Originally Posted by jasong

Just so you guys know, the guy working on the new sieve client(not the one in this thread) does intend to make it base-5 compatible. When that will actually happen, I don't know, but it's in the works.

Fine, but it isn't done yet. Assuming you are referring to proth_sieve, it doesn't output files in NewPGen format and you have to remove candidates that are factored from the SoB.dat file. Personally, I think that geoff's program is much more useful for this project.

[Greenbank]

I'm trying to find the time to write up some things about how proth_sieve works and whether the differences (BSGS is implemented in a different way) would be useful for srsieve.

If only I had more time...

[geoff]

I have added assembler versions of mulmod32, powmod32 and mulmod62 supplied by rogue. mulmod32 is twice as fast and mulmod62 five times faster than the previous versions.

A --benchmark option times some of these critical functions.

On my P3/450, srsieve 0.0.5 with just one base 5 candidate in the sieve is
now about 25% faster than NewPGen for p above 2^32, and about 50% faster for smaller p.

Originally Posted by davar55

What is BSGS?

The baby steps giant steps algorithm, used to compute the discrete logarithm.

[R. Gerbicz]

I've posted a speedup to seventeenorbust forum some years ago. There the base=2 but you can replace this by base=b. See my post at: http://www.free-dc.org/forum/showthr...254#post=29254
Implementing this they have gotten an about 3-4 times faster sieve.