mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2017-09-01, 08:24   #1
lucaf
 
Aug 2017

210 Posts
Default 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 multi-thread, 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
lucaf is offline   Reply With Quote
Old 2017-10-04, 19:44   #2
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

2·7·31 Posts
Default

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 2017-10-04 at 19:45 Reason: typo
Till is offline   Reply With Quote
Old 2017-10-05, 12:54   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

176116 Posts
Smile

Neat!

I haven't gone through the code yet, but at a first glance:
  • I know you're not going for speed, but still it might be worth using something like BitSet rather than a boolean array for the bits.
  • I notice that you're not segmenting the array. You may consider doing this, since without segmenting the array you can handle only small inputs (and can't take advantage of caching).
CRGreathouse is offline   Reply With Quote
Old 2017-10-05, 17:01   #4
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

2×7×31 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I know you're not going for speed, but still it might be worth using something like BitSet rather than a boolean array for the bits.
Good proposition, in particular because BitSet needs only about 1/32 of memory. A boolean in Java has the same space requirement as a (4-byte) int.

Quote:
Originally Posted by CRGreathouse View Post
I notice that you're not segmenting the array. You may consider doing this, since without segmenting the array you can handle only small inputs (and can't take advantage of caching).
I guess for sieving routines written in Java, cache access optimization doesnt help (yet) to improve performance, see the last paragraph of
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 ?
Till is offline   Reply With Quote
Old 2017-10-05, 20:16   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

176116 Posts
Default

Quote:
Originally Posted by Till View Post
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 ?
I haven't read Wambach & Wettig (and my library system doesn't seem to have it). But if I understand the basic idea is similar to Oliveira e Silva's sieve in working with small chunks of memory at a time, small enough to fit in the cache. But yes, the main benefit here is that you can work with bigger numbers. You might want to iterate over the primes up to 10^14 but not have 1.25 TB of RAM to hold the whole array, so you split it into blocks of size 10^7 (or 10^6 or 10^8) which are easy to fit in RAM and might even fit into the cache.
CRGreathouse is offline   Reply With Quote
Old 2017-10-05, 20:47   #6
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

16148 Posts
Default

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 cache-friendly 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.
danaj is offline   Reply With Quote
Old 2017-10-06, 08:33   #7
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

1B216 Posts
Default

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 ahead-of-time 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.
Till is offline   Reply With Quote
Old 2017-10-06, 19:40   #8
lucaf
 
Aug 2017

210 Posts
Default

Quote:
Originally Posted by Till View Post
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
Thank you very much, Till for your attention and for the support!

@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 pre-sieve 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!
lucaf is offline   Reply With Quote
Old 2017-10-06, 20:56   #9
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

2·7·31 Posts
Default

Quote:
Originally Posted by lucaf View Post
Thank you very much, Till for your attention and for the support!
You're welcome!

Quote:
Originally Posted by lucaf View Post
Java BitSet is limited, because max size can be MAXINT, if I'm not wrong
The same holds for any Java array bounds if I'm not wrong.

Quote:
Originally Posted by lucaf View Post
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 pre-sieve these numbers? This is not clear for me.
I'ld guess that typically the primes < sqrt(n) are computed in a simple sieve of Eratosthenes, because their impact on the total runtime is negliible.


Quote:
Originally Posted by lucaf View Post
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.
These guys spent a long time on their theoretical work, and were eager to let their practical outcome look good, too. The code is probably highly optimized. Sometimes one needs several passes through such stuff to understand what your own approach is still missing ;-)

Last fiddled with by Till on 2017-10-06 at 20:57 Reason: typo (as usual)
Till is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Java Quadratic Sieve Ilya Gazman Factoring 3 2016-02-22 11:32
Java based program GordonBM Information & Answers 11 2012-04-24 08:27
Oliver Atkin R.D. Silverman Math 3 2009-01-07 11:05
Sieve of Atkin amcfarlane Math 4 2006-02-21 23:47
Understandable QS java Implementation ThiloHarich Factoring 41 2005-11-28 21:18

All times are UTC. The time now is 04:55.

Mon Apr 12 04:55:07 UTC 2021 up 3 days, 23:35, 1 user, load averages: 2.01, 1.73, 1.77

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.