mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Sierpinski/Riesel Base 5

Reply
 
Thread Tools
Old 2006-04-27, 02:10   #1
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default 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)
geoff is offline   Reply With Quote
Old 2006-04-27, 02:47   #2
masser
 
masser's Avatar
 
Jul 2003
wear a mask

2×5×11×13 Posts
Default

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.
Attached Files
File Type: txt 139784.txt (5.2 KB, 176 views)
masser is offline   Reply With Quote
Old 2006-04-27, 05:37   #3
Citrix
 
Citrix's Avatar
 
Jun 2003

62316 Posts
Default

why not get proth_sieve modified. changing base 2 to base 5 won't take long.
Citrix is offline   Reply With Quote
Old 2006-04-27, 09:15   #4
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2×193 Posts
Default

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!).
Greenbank is offline   Reply With Quote
Old 2006-04-27, 13:15   #5
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2·193 Posts
Default

Quote:
Originally Posted by Citrix
why not get proth_sieve modified. changing base 2 to base 5 won't take long.
It would take quite a while, an awful lot of proth_sieve was written assuming that it was sieving base 2 numbers. Plus proth_sieve can't sieve anything below p=10^9.
Greenbank is offline   Reply With Quote
Old 2006-04-27, 20:08   #6
axn
 
axn's Avatar
 
Jun 2003

13×192 Posts
Default

Quote:
Originally Posted by Greenbank
It would take quite a while, an awful lot of proth_sieve was written assuming that it was sieving base 2 numbers.
That's a problem. But it might be worth it.
Quote:
Originally Posted by Greenbank
Plus proth_sieve can't sieve anything below p=10^9.
Not so much of a problem. We can always get ourselves to 10^9 one k at a time (NewPGen or some such program).

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?
axn is offline   Reply With Quote
Old 2006-04-28, 12:18   #7
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2·13·227 Posts
Default

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.
rogue is offline   Reply With Quote
Old 2006-04-28, 23:18   #8
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

134168 Posts
Default

Quote:
Originally Posted by rogue
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.
Strike that. I am mistaken. The time in invmod is negligable to If it is possible to have hsize set to a power of 2, then do so, because then you can use & instead of / when building your hash table. You also should consider an ASM routine to handle mulmods and powmods. This combination almost triples the speed. You should also consider using 64-bit p as it won't take long before p > 2^32.

My timings on
-n 5000 -N 10000 -P 10000000 "1396*5^n-1" "5114*5^n+1"
are:
13.5 seconds (original code) to 5.9 seconds (with these changes).
rogue is offline   Reply With Quote
Old 2006-04-29, 11:46   #9
axn
 
axn's Avatar
 
Jun 2003

13·192 Posts
Default

@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.
axn is offline   Reply With Quote
Old 2006-04-29, 23:41   #10
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

134168 Posts
Default

e-mail 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;
}
In bsgs.c, calculate hsize in init_hashtable with
Code:
  int tsize;
  tsize = firstprime(size*HASH_MAIN_FACTOR);
  hsize = 0x01;
  while (hsize < tsize)
      hsize <<= 1;
Then in lookup() and insert(), use
Code:
   int slot = bj & (hsize - 1);
This will improve performance for small p more than anything else. FYI, with the changes I've made to date, I get around 650 primes/sec across for n from 5000 to 2000000 for the 94 Sierpinski base 5 candidates, which is close to twice as fast of the original code on my box.

One thing that is misleading is that my code is 64-bit, 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 32-bit only code, but the way I view it is that so little time is spent in the 32-bit code that it isn't worth coding special routines for it. I have not fully tested thr 64-bitness 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".
rogue is offline   Reply With Quote
Old 2006-04-30, 01:20   #11
masser
 
masser's Avatar
 
Jul 2003
wear a mask

2·5·11·13 Posts
Default

Quote:
Originally Posted by axn1
@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.

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....
Attached Files
File Type: txt test.txt (199.9 KB, 291 views)
masser is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 08:26.

Tue Sep 22 08:26:25 UTC 2020 up 12 days, 5:37, 0 users, load averages: 1.14, 1.31, 1.37

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.