mersenneforum.org  

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

Reply
 
Thread Tools
Old 2006-06-29, 04:47   #1
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

22058 Posts
Default Faster sieving with NewPGen and srsieve

Here is a way to increase sieve throughput that works with NewPGen (for bases other than 2) and srsieve. Take this base 5 sequence that I am currently sieving as an example:

52922*5^n-1, 50,000 < n < 131072

It happens that all of the remaining terms in the sieve have n that are multiples of 4, and so I could instead sieve the following sequence and find exactly the same factors (since 5^4=625):

52922*625^n-1, 12500 < n < 32768

The difference is that the sieve range is 1/4 the size and so is quite a bit faster, roughly twice as fast with NewPGen, a bit less with srsieve because the benefits of the base 5 mulmod are lost.

In general, if it is possible to write n in k*b^n+c as n=q*m+r for fixed q,r then I think it will be possible to increase sieve throughput by a factor of about sqrt(q) and reduce bitmap memory use by a factor of (q-1)/q.

Version 0.2.0 of srsieve implements the memory reduction, but I am still working on the increased throughput part :-).

For the remaining sequences of the base 5 project it looks like q=4 is a common case, which might mean throughput can be doubled and memory use reduced to 25% of the current requirements.


axn1, could you run 'srfile -c' (version 0.2.0) on the current sieve file? It will print the values n=q*m+r for each sequence and give an effective q value for the file as a whole. If this pans out, it might be good to list the q values along with the Nash weights of the remaining sequences, as finding a prime for a sequence with a small q value would increase the speed of the sieve more than one with a large q.
geoff is offline   Reply With Quote
Old 2006-06-29, 06:30   #2
axn
 
axn's Avatar
 
Jun 2003

17·277 Posts
Default

See the attached file for the stats.

Is it possible to split the sieve files into multiple pieces to maximise efficiency?
Attached Files
File Type: txt stats.txt (8.2 KB, 137 views)
axn is online now   Reply With Quote
Old 2006-06-29, 23:51   #3
konrad127123
 
konrad127123's Avatar
 
Jun 2005

3·11 Posts
Default

Can you take this idea further e.g. if you find that for a particular k all the n values are either 1 or 2 module 12 then you can split it into the sequences (k*5)*(5^12)^n-1 and (k*25)*(5^12)^n-1. I think this is how proth-sieve does things.
konrad127123 is offline   Reply With Quote
Old 2006-06-30, 23:03   #4
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default

Quote:
Originally Posted by axn1
See the attached file for the stats.
Thanks, so the q values are 1,2,4,6,8,12,16,24, with most being 4 or larger.

Quote:
Is it possible to split the sieve files into multiple pieces to maximise efficiency?
Only for a limited number of the sequences. The q values are too large for most of them, using a base of 5^24 would need changes to the srsieve code anyway.

Quote:
Originally Posted by konrad127123
Can you take this idea further e.g. if you find that for a particular k all the n values are either 1 or 2 module 12 then you can split it into the sequences (k*5)*(5^12)^n-1 and (k*25)*(5^12)^n-1. I think this is how proth-sieve does things.
Yes that is what I hope to do. All of the remaining base 5 sequences can be broken up into equivalent sequences with base 5^48 since lcm(1,2,4,6,8,12,16,24)=48. According to the data from axn1 the theoretical gain will be by a factor of about sqrt(4.79), but I am not sure how much overhead will be added, it may end up less than that.
geoff is offline   Reply With Quote
Old 2006-07-03, 03:52   #5
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default

Quote:
Originally Posted by konrad127123
Can you take this idea further e.g. if you find that for a particular k all the n values are either 1 or 2 module 12 then you can split it into the sequences (k*5)*(5^12)^n-1 and (k*25)*(5^12)^n-1. I think this is how proth-sieve does things.
I have finished a prototype that does something like this. A sequence k*b^n+c with n=qm+r for fixed q,r is split into sequences k*b^(iq+r)*(b^tq)^m+c where 0 <= i < t.

For the base 5 sieve all the sequences end up in the form k*b^d*(b^48)^n+c where 0 <=d < 48.

It works out quite a bit faster when there are only a couple of sequences in the sieve, but the more sequences I add the slower it gets, and when there are 350 sequences it actually runs at only 1/4 the speed it did before I made any changes :-(

The problem seems to be that my modular inverse function is extremely slow. I will need to find a faster way to calculate -c/(k*b^d) (mod p) before this idea will work out.
geoff is offline   Reply With Quote
Old 2006-07-04, 20:19   #6
axn
 
axn's Avatar
 
Jun 2003

17·277 Posts
Default

Quote:
Originally Posted by geoff
I have finished a prototype that does something like this. A sequence k*b^n+c with n=qm+r for fixed q,r is split into sequences k*b^(iq+r)*(b^tq)^m+c where 0 <= i < t.

For the base 5 sieve all the sequences end up in the form k*b^d*(b^48)^n+c where 0 <=d < 48.
I am not sure I understand the logic -- are you saying that for each k, you'll sieve 48/q (q=24,16,12,etc..) separate sequences?! Wouldn't that lead to an explosion of sequences, especially for the lower q's? In that case 5^12 (or even 5^4) might be better than 5^48.

Last fiddled with by axn on 2006-07-04 at 20:20
axn is online now   Reply With Quote
Old 2006-07-04, 22:50   #7
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

115710 Posts
Default

Quote:
Originally Posted by axn1
I am not sure I understand the logic -- are you saying that for each k, you'll sieve 48/q (q=24,16,12,etc..) separate sequences?! Wouldn't that lead to an explosion of sequences, especially for the lower q's? In that case 5^12 (or even 5^4) might be better than 5^48.
You may be right :-) I thought that in principle it shouldn't matter if you end up with 48/q sequences since the sieve range has been reduced to 1/48th of the original size. In practice is does seem to matter, although I can't quite work out why.

The modular inverse was not a problem after all, instead of calculating 1/(b^d) for each d, it is much faster to calculate 1/b once then calculate (1/b)^d for each d.
geoff is offline   Reply With Quote
Old 2006-07-06, 23:32   #8
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

48516 Posts
Default

Just a note that the reason that a base less than 5^48 was faster was due to inefficiencies in my code that affected the larger bases more than the small ones. Now that I have fixed the worst of these, the speed increase seems to be converging to the expected sqrt(4.79) figure.
geoff is offline   Reply With Quote
Old 2006-07-07, 01:19   #9
konrad127123
 
konrad127123's Avatar
 
Jun 2005

3×11 Posts
Default

Have you tried using a value of Q larger than 48? It could possibly increase the sieve speed further.
konrad127123 is offline   Reply With Quote
Old 2006-07-07, 22:56   #10
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

100100001012 Posts
Default

Quote:
Originally Posted by konrad127123
Have you tried using a value of Q larger than 48? It could possibly increase the sieve speed further.
I hadn't until you asked the question, then I thought I had better try it before I reply :-)

The method srsieve uses to split up the base 5 sequences into base 5^Q subsequences is to express k*5^n+/-1 as k*5^(qm+r)+/-1 for fixed q,r. If q is maximised then for the Base 5 project sieve that leads to a maximum Q=48 since every remaining term happens to have a q that divides 48.

However it is possible to apply that same method to the base 5^48 sequences and get subsequences in even larger bases. I have added this capability to srsieve 0.3.3 for experiment. If you specify --limit-base=X with a value of X greater than the Q selected by srsieve in the first pass, it will continue splitting up the sequences until either the base reaches b^X or the base cannot be increased further.

For example with the Base 5 project sieve you could use multiples of 48 for X to get higher bases. I haven't tested this much, but none of the few cases I tried resulted in a speedup. If you find a case where using --limit-base=X results in better throughput than the default, I would be interested to hear.

There is one good reason why increasing Q will eventually result in reduced throughput: The work in the sieve has to be spread evenly between the baby steps and the giant steps to get good performance, but as the number of sequences increases the number of giant steps has to be reduced to keep that balance. Eventually only one giant step can be done, and it is not possible to re-balance by reducing the giant steps further. With the Base 5 project sieve we are already down to 4 giant steps with Q=48.
geoff is offline   Reply With Quote
Old 2006-07-08, 00:38   #11
konrad127123
 
konrad127123's Avatar
 
Jun 2005

1000012 Posts
Default

Quote:
Originally Posted by geoff
I hadn't until you asked the question, then I thought I had better try it before I reply :-)

The method srsieve uses to split up the base 5 sequences into base 5^Q subsequences is to express k*5^n+/-1 as k*5^(qm+r)+/-1 for fixed q,r. If q is maximised then for the Base 5 project sieve that leads to a maximum Q=48 since every remaining term happens to have a q that divides 48.
This is probably a silly question, but in your code, say you have a k value such that the corresponding n values are all 2 or 18 modulo 48. The corresponding q value would then be 16. Suppose we use Q=48 as normal, your code will then sieve the 2 and 18 modulo 48 subsequences. Will it also sieve the 34 modulo 48 subsequence since 34 % 16 =2? I'm guessing the answer is no (as it should be :)), but I couldn't work it out from the quick glance at the code that I had.

I'm away for a while now, so won't have a chance to play with the variable Q option for a the next fortnight or so.
konrad127123 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Parallel sieving with newpgen fivemack And now for something completely different 3 2017-05-16 17:55
Sieving twins with srsieve henryzz Twin Prime Search 0 2014-03-18 12:44
Is TPSieve-0.2.1 faster than Newpgen? cipher Twin Prime Search 4 2009-05-18 18:36
Sieving multiple NewPGen files in a row(How?) jasong Software 18 2005-12-30 20:23
Sieving with NewPGen Cruelty 15k Search 41 2005-10-27 10:28

All times are UTC. The time now is 03:50.

Fri Oct 23 03:50:54 UTC 2020 up 43 days, 1:01, 0 users, load averages: 1.87, 1.71, 1.60

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.