mersenneforum.org How do you efficiently sieve for prime 3/4-tuples?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2012-04-20, 18:46   #45
Puzzle-Peter

Jun 2009

22·52·7 Posts

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.

 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-20, 20:43   #47
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

10111111100102 Posts

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.

 2012-04-21, 06:03 #48 Puzzle-Peter     Jun 2009 10101111002 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, 11:47   #49
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

137628 Posts

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?
Attached Files
 tuples.zip (12.8 KB, 227 views)

2012-04-21, 13:27   #50
Puzzle-Peter

Jun 2009

12748 Posts

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.

Last fiddled with by Puzzle-Peter on 2012-04-21 at 13:39

 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-21, 17:51   #52
Puzzle-Peter

Jun 2009

22×52×7 Posts

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.

 2012-04-22, 15:40 #53 Puzzle-Peter     Jun 2009 22×52×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?
2012-04-22, 17:32   #54
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

2·5·613 Posts

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.

 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 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. Last fiddled with by R. Gerbicz on 2012-04-22 at 20:50

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 And now for something completely different 2 2017-04-28 00:08 fivemack Math 27 2015-12-12 18:42 tapion64 GPU Computing 7 2014-04-10 06:15 Unregistered Information & Answers 2 2010-05-25 20:51 Sloth Prime Sierpinski Project 1 2006-05-10 02:02

All times are UTC. The time now is 13:35.

Mon Jun 5 13:35:22 UTC 2023 up 291 days, 11:03, 0 users, load averages: 1.22, 1.18, 1.10

Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔