# What should I do if I think I wrote an algorithm that is _generally_ faster than Atkin Sieve? [closed]

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

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.

• 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 – JimN Dec 13 '17 at 20:29
• 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) – JimN Dec 13 '17 at 21:57
• cf. "wheel factorization", "Euler's sieve", "segmented sieve". – Will Ness Dec 13 '17 at 21:58
• 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. – Juho Dec 13 '17 at 23:37
• 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. – Yuval Filmus Dec 14 '17 at 9:09

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$.