What should I do if I think I wrote an algorithm that is _generally_ faster than Atkin Sieve? 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.
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).