1
$\begingroup$

I've been having some fun with prime numbers. A few months ago I sat down to see if I could write something that could compete with Atkin Sieve and ended up with an algorithm that, on my local tests on my RAM-restricted computer provide results where my algorithm is either close to Atkin or it can be way faster (depending on the number of prime numbers that are being discovered).

I set up a repo with the "basic" algorithm and then another version that uses BigIntegers with an expanding array so that memory could expand as much as necessary (trying not to go on RAM-hungry implementations using Collections of BigInteger and such).

This is waaaay out of my area of expertise... let's say, I'm just having fun while learning so I think I need people that have more experience on the field of performance testing and also guidance from people with research background to guide my steps if it's worthy.

So.... how about you take a look at the code and run some local tests? Perhaps offer ideas to improve performance? Or how to know if I should turn this into a serious research project?

Branches

  • Master has a basic implementation that works on boolean arrays.
  • bigint has basically the same implementation using BigInteger (and Collections)
  • bigint-selfgrowing: bigint implementation using an enormous boolean array (grows as needed)
  • bigint-selfgrowing-lessmemory: because of the nature of the data that my algorithm handles, for every 6 numbers, only 2 of them have to be kept so I modified the arrays to not care for the other 4 numbers (which allows for a theoretical 66% memory reduction but with a noticeable performance hit... plus Atkin is still using the original Enormous Boolean Array so it's not comparing oranges to oranges anymore... still, worth a look)

All branches have 3 classes that can be used to easily run tests of the pattern sieve (my sieve) against atkin. They can get 1, 2 or 3 parameters:

  • Single parameter: run single test with so many numbers
  • Two parameters: run tests starting from first parameter up to second parameter increasing number of primes by the first parameter each run
  • Three parameters: Run tests from first parameter up to second parameter increasing primes by the the third parameter each run.

For each test, it will report how many ms/ns/us it took to run (depending on the java class that was called) in csv format (and will also provide a little human-readable output on stderr, just in case).

https://github.com/eantoranz/patternsieve

Thanks in advance.

PS I used an implementation of Atkin that I found on internet (credits provided on commit, code and on stderr when running) so it might not be the best out there... if you know of a better implementation, let me know.

$\endgroup$

closed as primarily opinion-based by Juho, fade2black, Evil, David Richerby, hengxin Dec 25 '17 at 10:37

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Can you try to describe the algorithm without the use of code? The algorithm is the process, rather than the implementation. Comparing your implementation to another's implementation can tell you that maybe you have a better implementation, but not necessarily a better algorithm. See, for instance, the algorithm description for the Atkin sieve on en.wikipedia.org/wiki/Sieve_of_Atkin $\endgroup$ – JimN Dec 13 '17 at 20:29
  • $\begingroup$ I read your code and it is interesting... and you do have an algorithm description in your github, which is good. I'm surprised you aren't using a System.arraycopy( ) to transfer your patterns - I think this would give more speedup. I don't quite understand your tests, though. Up to what size of prime did this test to? (I don't mean time tests, but correctness tests) $\endgroup$ – JimN Dec 13 '17 at 21:57
  • 1
    $\begingroup$ cf. "wheel factorization", "Euler's sieve", "segmented sieve". $\endgroup$ – Will Ness Dec 13 '17 at 21:58
  • 1
    $\begingroup$ One problem is that Atkin's sieve is a complex algorithm, and a fast implementation requires care to the detail. This is quite common with theoretically fast algorithms, whose proofs can skip or overlook details that are crucial and become apparent when actually implementing. It's likely the implementation you found is slow in theory and in practice, because of the simple choices made in the implementation. IIRC Bernstein has a fast implementation available on his website. $\endgroup$ – Juho Dec 13 '17 at 23:37
  • 1
    $\begingroup$ The first step is probably to describe your algorithm succinctly, analyze it theoretically, and compare its time and space usage to Atkin's sieve. If you're interested in empirical comparison, then the question is somewhat off-topic here. $\endgroup$ – Yuval Filmus Dec 14 '17 at 9:09
1
$\begingroup$

Your PatternSieve is what is called a wheel sieve, or the wheel optimization for the SoE and is mentioned at the SoE Wikipedia page. It's well known and used in all fast SoE implementations. See Wheel factorization at Wikipedia for example. Pritchard wrote some articles about it in the early 1980s (e.g. A sublinear additive sieve for finding prime numbers and Explaining the wheel sieve). Sorenson has also written a number of good summary papers over the last 30 years (a recent paper that includes a number of references: Two compact imcremental prime sieves). I found Quesada and van Pelt's 1996 paper A Note on the Extensions of Erathosthenes' Sieve to be useful, though I believe Sorenson's are better as a whole.

The very basic skip-evens is the first form of this, and is almost always used. Doing mod-6 (skipping 2 and 3) is oft-used because it's simple, as seen in Robert William Hank's Python examples. Mod-30 (skipping 2, 3, and 5) is especially popular in high performance implementations because the 8 candidates fit perfectly in one byte. Going further is less common because of decreasing gains for quite a bit more complexity but mod-210 isn't too bad and primesieve uses that in some cases. The modulo is the small primorial (e.g. $5\# = 30 \rm{\ and\ } 7\# = 210$), while the number of remaining numbers is $\phi(n)$ (Euler's totient), e.g. $\phi(30) = 8 \rm{\ and\ } \phi(210) = 48$.

You are looking at empirical performance. This is certainly interesting, but Java is definitely not the best language here, and you would be best served by using properly fast comparisons. It's fairly well known that properly optimized segmented SoE implementations are faster than the segmented SoA. E.g. GordonBGood's long analysis. The SoA you're using is certainly simple and easy to follow, but it's straight from the Wikipedia pseudocode which indicates it skips lots of optimizations. Even Bernstein's convoluted but fast C implementation is slower than the fastest SoE implementations (though it is optimized enough to beat the simple ones).

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.