20060427, 02:10  #1 
Mar 2003
New Zealand
13×89 Posts 
A multiple k/c sieve for Sierpinski/Riesel problems
I have started writing a program to sieve for these projects, it is far from complete but the core sieving algorithm is working and seems to be producing correct results. If you want to try it out I will put the source code here: srsieve
I haven't implemented extended arithmetic yet so it is limited to sieving up to about 4 billion on 32 bit machines. It uses a baby steps giant steps algorithm to sieve any number of candidate sequences at once, both Sierpinski and Riesel. It is already much faster than NewPGen when sieving with 4 or more candidates, although some of that is probably because of the 32bit arithmetic. Here are a couple of timings for sieving on my P3/450 with base 5 Sierpinski candidates from 1 < p < 100,000,000 and 50,000 < n < 100,000: 1 candidate: 14 minutes (NewPGen 18 minutes) 4 candidates: 28 minutes (NewPGen 55 minutes) 
20060427, 02:47  #2 
Jul 2003
wear a mask
2^{5}·3^{2}·5 Posts 
Wow! That siever sounds awesome. I can't wait to try it.
On the topic of sieving, I noticed you reserved a k value I had previously done some sieving on. Here's the sieve file  hopefully it's useful to you. 
20060427, 05:37  #3 
Jun 2003
2·787 Posts 
why not get proth_sieve modified. changing base 2 to base 5 won't take long.

20060427, 09:15  #4 
Jul 2005
182_{16} Posts 
Good work Geoff and thank you for making the source available. I'll take a look at it and see how it compares to proth_sieve (hopefully we can improve both programs!).

20060427, 13:15  #5  
Jul 2005
386_{10} Posts 
Quote:


20060427, 20:08  #6  
Jun 2003
2^{2}·11·107 Posts 
Quote:
Quote:
REQUEST#1: Could someone make a Win32 executable for Geoff's pgm (Athlon 32 build, if possible)? I have no way of compiling it. REQUEST#2: Geoff, can your program handle both + &  sieve simultaneously. If not, can you modify it to do so? 

20060428, 12:18  #7 
"Mark"
Apr 2003
Between here and the
2^{4}×7×53 Posts 
Good work on your sieve. If you can do your invmod entirely to the FPU, you should be able to double the speed of the sieve (at the minimum). I'll play with something this weekend.
Another point I have is that you will have to modify it to handle p > 32 bit in order for it to be truly useful on this project. Consider using Montgomery to handle your mods. 
20060428, 23:18  #8  
"Mark"
Apr 2003
Between here and the
13460_{8} Posts 
Quote:
My timings on n 5000 N 10000 P 10000000 "1396*5^n1" "5114*5^n+1" are: 13.5 seconds (original code) to 5.9 seconds (with these changes). 

20060429, 11:46  #9 
Jun 2003
2^{2}×11×107 Posts 
@geoff: Outstanding! I am right now sieveing all 94 Sierpinski k's for n <= 2,000,000. Getting about 8kp/s. At this rate I'll be done with p < 2^32 in under a week.
@rogue: Can you post the modified source code and/or post an executable? That sound's interesting. 
20060429, 23:41  #10 
"Mark"
Apr 2003
Between here and the
13460_{8} Posts 
email sent to axn1. geoff, get in contact with him if you don't mind.
BTW, I found a bug in next_bit(). This loop: for (i++; B[i] == 0; i++) ; can lead to a SEGFAULT (as it did with me). I modified it to: for (i++; B[i] == 0; i++) if (i > bit_range) break; where bit_range = sieve_range >> 5. sieve_range is passed on the call. I also suggest that you use shifts instead of % and / in bitmap.h. This is what I have: Code:
#define UINT_BIT 32 #define UINT_SHIFT 5 // because 2^5 = 32 extern inline int set_bit(unsigned int *B, int bit) { int ret, mask; B += (bit >> UINT_SHIFT); // B += bit / UINT_BIT; mask = 1 << (bit & (UINT_BIT  1)); //mask = 1 << (bit % UINT_BIT); ret = (mask & *B) != 0; *B = mask; return ret; } extern inline int clear_bit(unsigned int *B, int bit) { int ret, mask; B += (bit >> UINT_SHIFT); // B += bit / UINT_BIT; mask = 1 << (bit & (UINT_BIT  1)); //mask = 1 << (bit % UINT_BIT); ret = (mask & *B) != 0; *B &= ~mask; return ret; } extern inline int test_bit(const unsigned int *B, int bit) { int mask; B += (bit >> UINT_SHIFT); // B += bit / UINT_BIT; mask = 1 << (bit & (UINT_BIT  1)); //mask = 1 << (bit % UINT_BIT); return ((mask & *B) != 0); } extern inline unsigned int first_bit(const unsigned int *B) { int i; for (i = 0; B[i] == 0; i++) ; return i*UINT_BIT + ffs(B[i])  1; } extern inline unsigned int next_bit(const unsigned int *B, int bit, int sieve_range) { unsigned int i, mask, bit_range; bit_range = sieve_range >> UINT_SHIFT; i = (bit >> UINT_SHIFT); //i = bit / UINT_BIT; mask = ~0U << (bit & (UINT_BIT  1)); //mask = ~0U << (bit % UINT_BIT); if (B[i] & mask) return i*UINT_BIT + ffs(B[i] & mask)  1; for (i++; B[i] == 0; i++) if (i > bit_range) break; return i*UINT_BIT + ffs(B[i])  1; } Code:
int tsize; tsize = firstprime(size*HASH_MAIN_FACTOR); hsize = 0x01; while (hsize < tsize) hsize <<= 1; Code:
int slot = bj & (hsize  1); One thing that is misleading is that my code is 64bit, so the limit is 2^63, not 2^32, so it is a little harder to compare. My sieving rate would be much higher if I wrote separate 32bit only code, but the way I view it is that so little time is spent in the 32bit code that it isn't worth coding special routines for it. I have not fully tested thr 64bitness of the code. My additions are fine, but I can't speak for the original code. I would have to look at any references to "int" and replace some of them with "long", or "uint64_t". 
20060430, 01:20  #11  
Jul 2003
wear a mask
2^{5}×3^{2}×5 Posts 
Quote:
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 nrange reservations.... 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Very Prime Riesel and Sierpinski k  robert44444uk  Open Projects  587  20161113 15:26 
Sierpinski/ Riesel bases 6 to 18  robert44444uk  Conjectures 'R Us  139  20071217 05:17 
Sierpinski/Riesel Base 10  rogue  Conjectures 'R Us  11  20071217 05:08 
Sierpinski / Riesel  Base 23  michaf  Conjectures 'R Us  2  20071217 05:04 
Sierpinski / Riesel  Base 22  michaf  Conjectures 'R Us  49  20071217 05:03 