mersenneforum.org  

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

Reply
 
Thread Tools
Old 2005-07-14, 00:32   #1
jaat
 
jaat's Avatar
 
Jul 2005

2·32 Posts
Default Combined Sieving?

Hi,

I want to know whether I can do combined sieving for a bunch of k together with newpgen or some other tool? The issue is not to save time but save a lot of bother doing it for each k independently.

jaat
jaat is offline   Reply With Quote
Old 2005-07-16, 03:04   #2
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

48516 Posts
Default

I don't know of any sieving program that will do this yet.

But with pfgw you can use an ABC2 file to do trial factoring and prp testing for a number of k values. As an example, put this in myfile.txt:
Code:
ABC2 $a*5^$b-1 //{number_primes,$a,1}
a: in { 1002 2004 }
b: from 100 to 1000
and starting pfgw as 'pfgw -f myfile.txt' will trial factor and/or prp test 1002*5^100-1, 2004*5^100-1, 1002*5^101-1, ... etc. When one prp is found for a value of $a then testing will stop for that value and continue just for the remaining values.

This is convenient, but will be much slower than sieving with newpgen unless the range for each k is quite small.
geoff is offline   Reply With Quote
Old 2005-10-12, 10:34   #3
axn
 
axn's Avatar
 
Jun 2003

4,919 Posts
Default

Maybe its time we gave serious though to combined sieving.

Can someone get in touch with Mikael Klasson to get a modified version of proth_sieve that can handle base 5? No idea how tough it'll be to do this, but i guess its worth a shot.
axn is offline   Reply With Quote
Old 2005-10-26, 17:55   #4
jaat
 
jaat's Avatar
 
Jul 2005

100102 Posts
Default

Quote:
Originally Posted by axn1
Maybe its time we gave serious though to combined sieving.

If there is any hope for this project to gather some momentum, this is a must.

jaat
jaat is offline   Reply With Quote
Old 2005-11-30, 19:05   #5
Greenbank
 
Greenbank's Avatar
 
Jul 2005

2·193 Posts
Default

Even if you can get this done it's going to be much slower.

You lose all of the Quadratic Residue filtering.
All of the small-steps will have to be calculated with powmod instead of simple bit shifts.
The order(2) filtering will be gone (although you might be able to adapt this to base 5.

Better off finding a program that implements base 5 sieving now as there would have been some attempts at optimising this sieving. proth_sieve only implements base 2, and therefore it is only optimised for base 2.
Greenbank is offline   Reply With Quote
Old 2006-04-18, 02:26   #6
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default

Riesel5 candidate k=151026 is the only one satisfying k = 0 (mod 3). This makes it the only remaining candidate that could have primes for both odd and even exponents. The possibilities for any other candidates are:

If k = 1 (mod 3) then k*5^even-1 and k*5^odd+1 are composite
If k = 2 (mod 3) then k*5^odd-1 and k*5^even+1 are composite

[3 | k*5^n+/-1 whenever 3 | k*5^(n-2)+/-1 because 5^2 = 1 (mod 3)].

This fact could be exploited by a siever, for example to halve the memory required for a bitmap of candidate n (assuming k=151026 is not in the sieve). NewPGen does not seem to take advantage of this.
geoff is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
UPS /combined UPS and PS for P95 computer Christenson Hardware 12 2011-10-27 03:41
Combined sieving discussion ltd Prime Sierpinski Project 76 2008-07-25 11:44
Combined Sieving speed Joe O Prime Sierpinski Project 7 2006-09-22 09:34
Combined Sieve Guide Discussion Joe O Prime Sierpinski Project 35 2006-09-01 13:44
Sieve discussion Meaning of first/second pass, combined Citrix Prime Sierpinski Project 14 2005-12-31 19:39

All times are UTC. The time now is 14:09.

Tue Apr 20 14:09:36 UTC 2021 up 12 days, 8:50, 0 users, load averages: 3.35, 3.90, 3.75

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.