20170901, 08:24  #1 
Aug 2017
2_{10} Posts 
Simple Atkin sieve java example
Hi all,
I'm lurking your site since months and I'm impressed by the high level of your knowledge. I experienced some difficult in find clear examples and applications of Atkin / Bernstein sieve, so I wrote my own example code for educational purposes. The code is here: https://gist.github.com/lucafmi/729f...67ea233abbb3c6 it's not optimized (not multithread, written in java, no deep reduction of operations) because it's a simple version that can be read and understood easily. I'm not a math expert, I'm a software engineer, so my question is: am I interpreted the algorithm in the right way? Did I something wrong? Am I missing some important part? Any suggestion, observation, is appreciated Thank you all LucaF 
20171004, 19:44  #2 
"Tilman Neumann"
Jan 2016
Germany
2·7·31 Posts 
Hi Luca,
I was thinking some time ago to implement the Atkins sieve in Java and just found your thread today. I didn't give it a deeper look yet, but if I can trust the comments in your code then you get the right number of primes below 1000. So there's some reason to believe that it works. I'ld say it looks fine. Btw. most guys here are only interested in maximum speed solutions I guess, i.e. C and assembler code. Don't get discouraged by that ;) Till Last fiddled with by Till on 20171004 at 19:45 Reason: typo 
20171005, 12:54  #3 
Aug 2006
1761_{16} Posts 
Neat!
I haven't gone through the code yet, but at a first glance:

20171005, 17:01  #4  
"Tilman Neumann"
Jan 2016
Germany
2×7×31 Posts 
Quote:
Quote:
http://www.mersenneforum.org/showpos...9&postcount=47 But it is interesting if it allows to compute larger primes. Would segmenting in Atkins / Eratosthenes sieve work in a way similar to that of quadratic sieves aka Wambach/Wettig ? 

20171005, 20:16  #5  
Aug 2006
1761_{16} Posts 
Quote:


20171005, 20:47  #6 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
1614_{8} Posts 
A simple segmented sieve is typically more like what Kim describes: http://primesieve.org/segmented_sieve.html
Basically you just keep sieving segments independently. While this is more operations, it's a win due to much smaller memory space being accessed. It's also a giant win in memory use. Oliveira e Silva's sieve is a lot more complicated and uses substantially more memory (many GB near 2^63). The access patterns are sitll nicely localized and its empirical growth rate at large sizes is superior. It cleverly stores the offsets for each sieve prime in separate buckets, doing at least two important optimizations. (1) you no longer have to calculate the offset for each sieve prime during each segment since it is stored (this saves ~3 divides and a couple lookups per sieve prime per segment) and (2) it skips sieve primes that don't hit this segment entirely. The last one is not terribly interesting when sieving below 10^10, for instance, but when we're in the 10^17 range which is more its design goal, lots of sieve primes start missing segments. His sieve puts them in the appropriate bucket for the upcoming segment meaning we only have to run through the sieve primes that actually touch this segment. If you want really fast performance for a decent range starting past 10^15 then definitely look into the cachefriendly bucket sieve. That was what it was meant for and it does well. Otherwise a standard simple segmented sieve is worth looking at. Even just to 10^9 they do a lot better than monolithic sieves. primegen, Bernstein's C segmented Sieve of Atkin, does really well at small sizes, though still a bit slower than the fastest segmented SoE implementations. It shows very poor growth as the size increases and by 10^13 it's slower than most of the segmented SoE implementations I measured (even the ones it was faster than at 10^11). All the above based on looking at sieves in C on x86_64 machines. 
20171006, 08:33  #7 
"Tilman Neumann"
Jan 2016
Germany
1B2_{16} Posts 
Thanks for the explanations and the links
So indeed segmenting works quite in the same way in segmented Eratosthenes as in the segmented QS. The Wambach/Wettig paper can be found here: https://pdfs.semanticscholar.org/6ac...b2178ee739.pdf Btw. the situation concerning cache access in Java could change in the future. Java 9 has introduced aheadoftime compilation, see http://openjdk.java.net/jeps/295. So far it is an experimental feature and supports only Linux, and somewhere I read that the current performance may "sometimes be better and sometimes worse" than running a program in the JVM. But in the long run AOT compilation might become quite interesting concerning both cache access and overall performance. 
20171006, 19:40  #8  
Aug 2017
2_{10} Posts 
Quote:
@CRGreathouse you are right my code is not optimized at all. It was intended to be a really simple and understandable code implementing the Atkin Sieve.  about bitset: Java BitSet is limited, because max size can be MAXINT, if I'm not wrong Some days ago I wrote a C version, where I stored the boolean value in bits (storing only odd numbers, I have 8 odd numbers every byte, 16 n/byte). Observing that the Atkin sieve admits 16 valid modulus 60 remainders I think I can store them in a more compressed manner, using 2 bytes every 60 numbers (1 byte every 30 numbers against 1 byte every 16 numbers).  I will try to use segmented arrays and multithreading, but my maths/programming level is not so high: I get in trouble when I try to segment the Atkin's... If I need to store also the small primes <sqrt(n) to sieve correctly, do I need to presieve these numbers? This is not clear for me. I compiled the code of Bernstein's Atkin sieve implementation, and the Kim Walisch's Eratosthenes wheel sieve  and tried to understand their code  , and these software are impressive; any improvement I can make at mine, I'll never have interesting results in speed, compared to these, considering that the Bernstein one was written a lot of years ago, without multithreading. P.S. I didn't know the Wambach/Wettig sieve, very interesting! 

20171006, 20:56  #9  
"Tilman Neumann"
Jan 2016
Germany
2·7·31 Posts 
You're welcome!
Quote:
Quote:
Quote:
Last fiddled with by Till on 20171006 at 20:57 Reason: typo (as usual) 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Java Quadratic Sieve  Ilya Gazman  Factoring  3  20160222 11:32 
Java based program  GordonBM  Information & Answers  11  20120424 08:27 
Oliver Atkin  R.D. Silverman  Math  3  20090107 11:05 
Sieve of Atkin  amcfarlane  Math  4  20060221 23:47 
Understandable QS java Implementation  ThiloHarich  Factoring  41  20051128 21:18 