A multiple k/c sieve for Sierpinski/Riesel problems

[axn]

Originally Posted by geoff

I did mean a 60% throughput improvement, but I only tested on my P4. The improvement is mainly due to the hashtable being smaller and staying in cache longer, so the actual improvement will depend a lot on cache size.

Well then, you outdid yourself. 3400 p/sec to 8000 p/sec = 135% improvement on my Athlon!

[geoff]

Originally Posted by axn1

Well then, you outdid yourself. 3400 p/sec to 8000 p/sec = 135% improvement on my Athlon!

Great :-) I think what has happened in this case is that the main table now fits entirely in your Athlon's L1 cache. If you start srsieve with the --verbose option it will report the hashtable size, multiply that by two to get the size in bytes of the main table. A lot more primes will have to be found before it will fit in the P4's L1 cache.

[axn]

Originally Posted by geoff

Great :-) I think what has happened in this case is that the main table now fits entirely in your Athlon's L1 cache. If you start srsieve with the --verbose option it will report the hashtable size, multiply that by two to get the size in bytes of the main table.

The -v option reports a hash size of 2^15. So the hash table size should be 64KB which should fit almost entirely within the Athlon's 64KB L1 Data cache.

[geoff]

--twin option to sieve for twin primes.

Support for NewPGen type 19/20 sieve files (b^n+/-k). Use LLR only for these sieves, PRP doesn't work.

mulmod/powmod assembler for the PPC, thanks rogue for this code.

[Citrix]

If someone wanted to work on the brier problem, can your sieve support it?
ie sieve k*2^n+1 and k*2^n-1 together.

edit: Not that I want it implemented, I was just curious if your program supported such a form.

[geoff]

Originally Posted by Citrix

If someone wanted to work on the brier problem, can your sieve support it?
ie sieve k*2^n+1 and k*2^n-1 together.

Yes this will work. The command to sieve just 3*2^n+/-1 for 1 <= n <= 1 million would be:

$ srsieve --twin --nmin 1 --nmax 1e6 "3*2^n-1" "3*2^n+1"

[fetofs]

Originally Posted by geoff

Yes this will work. The command to sieve just 3*2^n+/-1 for 1 <= n <= 1 million would be:

$ srsieve --twin --nmin 1 --nmax 1e6 "3*2^n-1" "3*2^n+1"

But I imagine a "twin" function will eliminate the +1 part when the -1 is eliminated, or vice-versa (unless your program is not as optimized as it minimally should be).

[R. Gerbicz]

Originally Posted by fetofs

But I imagine a "twin" function will eliminate the +1 part when the -1 is eliminated, or vice-versa (unless your program is not as optimized as it minimally should be).

I think the best method for that to sieve (k*2^n+1)*(k*2^n-1)=(k*k)*4^n-1 so base=4 and multiplier=k*k and c=-1.

[geoff]

Originally Posted by R. Gerbicz

I think the best method for that to sieve (k*2^n+1)*(k*2^n-1)=(k*k)*4^n-1 so base=4 and multiplier=k*k and c=-1.

I didn't think of that :-) There is not really much point using srsieve for sieving twins then.

[masser]

We need a prover code for srsieve; just found 43018*5^279020+1 and would like to credit geoff's wonderful program.

[axn]

Originally Posted by masser

We need a prover code for srsieve; just found 43018*5^279020+1 and would like to credit geoff's wonderful program.

Absolutely. Have you tried contacting Chris Caldwell?