How do you efficiently sieve for prime 3/4-tuples? - Page 5

Puzzle-Peter · 2012-04-20, 18:46

Quote:

Originally Posted by firejuggler

where should i change Sprime to sieve a bit deeper for quad? (right now, quad10011_5_20... 32.3 M k ...at 1.22 B, advancing slooowly 1k every 0.2/0.1 sec)

You're running NewPGen, right?

Mx experience is that if sieving to 1e9, the max. k-range is 10T. It can take more, but it is slow. Try splitting the range in half and you should get much faster progress.

firejuggler · 2012-04-20, 18:54

thank you, that did the trick... now the rate is at 60 k per sec, much quicker... ( test primality on several machine)

henryzz · 2012-04-20, 20:43

Quote:

Originally Posted by firejuggler

just a minor nitpick : when you sieve for 7-tuple the file is named "quinxxx.txt"

Whoops. I will correct in the morning.

The 30/210 thing is just a speedup. The list axn posted assumed -5 -1 +1 +5 +7 +11. So this cannot be used for the 7-tuple combination I used. You can add to this list but cannot remove from it without missing candidates. Sometimes you can tighten it after adding more which is why we moved from 30 to 210.

I have been trying to use candidates that include all the previous types as well. I also test them in this order so if I find 5 primes when searching for 6-tuples then I have a 5-tuple. This isn't always possible. 6 and 7 were just too different. I managed to find one for 7 that includes 5 and below though. I would suggest we search for something like 8 at the size for a record at 6. This would mean even if we don't find a 8 we find something useful. I think running separate searches at 6 and 8 would be less effficient. Maybe people at tps would like to search for larger tuples. Some of these records seem to be sitting here for the taken by a project/person with a few cpu years as far as I can see.

@ puzzle-peter The site said there are no known 24-tuples. This basically means there aren't any small optimal tuples which have been found. The trivial search space was exhausted before they came across the first one. Relying on the law of small numbers didn't work in this case.

Puzzle-Peter · 2012-04-21, 06:03

Hm. I'm starting to realize just how much of the basics I'm missing.

A sixtuplet is a quadruplet with additions on each end, another -4 and +4. This is a pattern I don't see in any of the longer tuplets (well, I found one contained in a 19 *lol*). So sieving for 8 won't get any 6 as bycatch, right? But there is an 8-pattern that includes a 7-pattern, which is
8: 0 2 6 8 12 18 20 26
7: 0 2 6 8 12 18 20

The quadruplet pattern appears on most of the larger tuplets, which is why the quad code can be reused by adding to this pattern, correct?

I'm just trying to make sure I am able to make use of everything I read here without messing things up.

Thanks to everybody for your help and explanations!

henryzz · 2012-04-21, 11:47

I added a new constant tuple_size to all the source files. It basically changes the dimensions of ndx and the two loop counts. This means it is easier to do a change and is less error prone. All are attached. The only files with functional different are six and seven. I have changed seven to work mod 210 which should multiple the speed by 7 I believe.

Has anyone ever experimented with adding a prime to the presieve?
Has anyone fiddled with SieveSize?

Puzzle-Peter · 2012-04-21, 13:27

Quote:

Originally Posted by henryzz

Has anyone ever experimented with adding a prime to the presieve?
Has anyone fiddled with SieveSize?

I added 19 to presieve, but by now I believe there are other changes to be made besides adding "*19" to the code. It worked and gave an identical result file, but I saw no speed gain.

I also tried different sievesizes, again with ambigous results. On one core it seemed to be faster when sievesize was larger than L2 cache size. Using all cores at the same time it seemed to be slower. I'm not sure if the constant disk access may have warped my timings as there were other processes needing a lot of bandwidth. I saw the iteration counter went up in irregular time intervals so I probably have to do the timings again.

I fiddled around with the number of smallprimes also and saw it can be quite large and still be lucrative. Depending mainly of N of course.

What's up with the 10000T limit? AFAIK qword can go higher by a factor 100.

EDIT: in Quin, Six and Seven K_START is being size checked as given in G while K_END is handled as given in T. Search ranges grow rapidly with long tuples so I think T is fine. It's really fast anyway.

henryzz · 2012-04-21, 15:32

k limit now increased to 10000P (10^19). There were a few arbitrary limits left in there from it being a twin prime sieve.
Both k_start and k_end are being checked in G now. I prefer G because it allows me to do small ranges for testing. I might try and work on a 5e9 sort of notation at some point.
There are more changes needed for changing the presieve.

Puzzle-Peter · 2012-04-21, 17:51

Quote:

Originally Posted by henryzz

I might try and work on a 5e9 sort of notation at some point.

Don't do it because of me! G is fine and even I could do the switch back to T.

Puzzle-Peter · 2012-04-22, 15:40

Next question: the main part is do_sieve_iter. Its outer loop counts to sprime_ctr, so for each subrange sieved the runtime time should be linear with the number of small primes, right?

Decreasing SmallPrimes to a ridiculously low value like 1000 does not give very much of a speedup. Could it be that looping through the array to find the candidates left after sieving and write them to the outfile takes quite a lot of time?

henryzz · 2012-04-22, 17:32

Quote:

Originally Posted by Puzzle-Peter

Could it be that looping through the array to find the candidates left after sieving and write them to the outfile takes quite a lot of time?

Quite possibly.
I am going to attempt running it with gprof. Win64 with gpof support isn't supported by fpc so trying linux.
Unfortunately my ubuntu virtual machine is 9.04 and can't upgrade easily. Downloading the 12.04 Beta 2 iso now.

R. Gerbicz · 2012-04-22, 20:49

I have written a sieve in c language for this problem, see https://sites.google.com/site/robertgerbicz/gsieve.

It should be faster than axn's version. It uses different type of sieves depending on the number of candidates and p value.

Set bound_small_primes as 13, if 2*3*5*7*11*13*SmallPrimes<=end_k-start_k. You can try to use 13 earlier also. Or even higher. Play also with sieve_len. From the printed timing information and ratio of the progress you can get quickly an estimation for the completion time.

Note that this sieve doesn't care about tiny ranges, it is really slow if you give say a 1 billion range. The current setup is fast if end_k-start_k>>2310*10^9.

Due to the wheelsieve it doesn't print out the remaining k candidates in increasing order.

2012-04-20, 18:54	#46
firejuggler "Vincent" Apr 2010 Over the rainbow 2·31·47 Posts	thank you, that did the trick... now the rate is at 60 k per sec, much quicker... ( test primality on several machine) Last fiddled with by firejuggler on 2012-04-20 at 18:55

2012-04-22, 20:49	#55
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 3·5·109 Posts	I have written a sieve in c language for this problem, see https://sites.google.com/site/robertgerbicz/gsieve. It should be faster than axn's version. It uses different type of sieves depending on the number of candidates and p value. Set bound_small_primes as 13, if 23571113SmallPrimes<=end_k-start_k. You can try to use 13 earlier also. Or even higher. Play also with sieve_len. From the printed timing information and ratio of the progress you can get quickly an estimation for the completion time. Note that this sieve doesn't care about tiny ranges, it is really slow if you give say a 1 billion range. The current setup is fast if end_k-start_k>>231010^9. Due to the wheelsieve it doesn't print out the remaining k candidates in increasing order. Last fiddled with by R. Gerbicz on 2012-04-22 at 20:50*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
How/Where to get Jens Kruse Andersen's prime constellation sieve?	Stargate38	And now for something completely different	2	2017-04-28 00:08
Efficiently finding a linear progression in data	fivemack	Math	27	2015-12-12 18:42
GPU Prime Sieve	tapion64	GPU Computing	7	2014-04-10 06:15
Sieve depth vs. prime probability	Unregistered	Information & Answers	2	2010-05-25 20:51
Prime in Riesel Sieve Project	Sloth	Prime Sierpinski Project	1	2006-05-10 02:02

2012-04-21, 06:03	#48
Puzzle-Peter Jun 2009 1010111100₂ Posts	Hm. I'm starting to realize just how much of the basics I'm missing. A sixtuplet is a quadruplet with additions on each end, another -4 and +4. This is a pattern I don't see in any of the longer tuplets (well, I found one contained in a 19 lol). So sieving for 8 won't get any 6 as bycatch, right? But there is an 8-pattern that includes a 7-pattern, which is 8: 0 2 6 8 12 18 20 26 7: 0 2 6 8 12 18 20 The quadruplet pattern appears on most of the larger tuplets, which is why the quad code can be reused by adding to this pattern, correct? I'm just trying to make sure I am able to make use of everything I read here without messing things up. Thanks to everybody for your help and explanations!

2012-04-21, 15:32	#51
henryzz Just call me Henry "David" Sep 2007 Liverpool (GMT/BST) 2×5×613 Posts	k limit now increased to 10000P (10^19). There were a few arbitrary limits left in there from it being a twin prime sieve. Both k_start and k_end are being checked in G now. I prefer G because it allows me to do small ranges for testing. I might try and work on a 5e9 sort of notation at some point. There are more changes needed for changing the presieve.

2012-04-22, 15:40	#53
Puzzle-Peter Jun 2009 2²×5²×7 Posts	Next question: the main part is do_sieve_iter. Its outer loop counts to sprime_ctr, so for each subrange sieved the runtime time should be linear with the number of small primes, right? Decreasing SmallPrimes to a ridiculously low value like 1000 does not give very much of a speedup. Could it be that looping through the array to find the candidates left after sieving and write them to the outfile takes quite a lot of time?