Although this question is old, the considerations are still relevant and there is still some lack of proper analysis on which prime sieve to choose for various purposes. In this evaluation, it is important to note that these intense considerations are only necessary for ranges of primes in the order of a hundreds of millions or more: A simple trial division algorithm can be sufficient for a range of up to about a million and just about any properly optimized sieve can sieve to a billion in a few seconds to tens of seconds in just about any language that is not interpreted (compiled or Just-In-Time - JIT - compiled to native code). It is large ranges of a billion an up where things get interesting in that the amount of memory used becomes a consideration such that it may be a requirement to implement page segmentation so as to be able to efficiently use the available memory.
First, note that there are three considerations on what makes a particular sieve fast, as follows:
- The number of operations and how these operations increase for increasing ranges for a particular sieve, which latter evaluation is what is indicated by the big-O value for asymptotic execution complexity for large ranges.
- The complexity of each individual culling operation as in machine cycles per operation which usually isn't considered in given big-O functions as per point 1.
- The ability to add page segmentation without impacting excessively on the above two requirements, which segmentation is necessary to reduce memory requirements for large ranges so the sieve can be run at all, to achieve better cache associativity which otherwise will have a (large) negative impact on point 2 above.
Many mistakenly think that the best big-O performance is the best algorithm, but that is an error in analysis: An algorithm may have the best big-O performance as in (say) O(N) for sieving (where
N is the sieving range) but require either many more operations or such complex operations that the execution time for each operation is so high that the total time to execute to a given range may be much higher than for an algorithm with less operations/complexity such that it can never catch up to an algorithm with worse big-O performance for practical achievable sieving ranges; thus, it is usually not the best or only consideration for comparison and is more useful for predicting the performance of a given algorithm with increasing range as compared to itself.
The main three contenders are usually the following with the given big-O performance characterizations following:
- The Sieve of Eratosthenes (SoE) - O(N log(log (N)))
- The Sieve of Sundaram (SoS) - O(N log(N))
- The Sieve of Atkin (SoA) - O(N) (i've added this one as it is usually considered...)
Let's consider these in order:
First, it is pointless to implement the SoE without including the very simple "odds-only" optimization that reduces the number of operations by a factor of about two and a half to about the same number of culling operations as the sieving range. However, there is no reason to stop there, and with a little added complexity in using the maximally wheel factorized "combo sieve" as per the Wikipedia article, one can reduce this to about a quarter of the sieving range for ranges of about a billion to about a third of the sieving range for sieving ranges of about a trillion. Thus, with maximum wheel factorization the number of culling operations aren't much more than the best of the other algorithms. The majority of the inner culling loop(s) in which the SoE spends most of its time can be reduced to a very simple native code single clock cycle read/modify/write instruction with maximum optimization techniques so that even when averaged across supporting code and parts of the code that can't use this optimization, the average is still only two to three CPU clock cycles per culling cycle for ranges of trillions. While it's true that operations get gradually a little slower on the average for larger ranges, they increase relatively slower than the practical application of the other algorithms.
The unmodified SoS algorithm can never approach the performance of other sieves due to not specifying the proper limits for the
j variables, which can easily be limited so that the culling function
i + j + 2ij never exceeds one half of the culling range value as larger values exceed the sieve buffer range. However, the SoS still has many more operations than the "odds-only" SoE as it culls by the factors of all odd values rather than only the prime factors as for the SoE, which is why it has the O(N (log N)) performance rather than O(N ((log (log N))) performance; this makes a significant difference in the number of culling operations for culling ranges of a billion and above, and while the number of operations can be reduced by such techniques as pre-culling for small values of factor, this optimization (and more) can also be applied to the SoE. Now, it could be improved by using a recursive loop so that it uses a secondary source of primes to generate the
i values and letting the
j values start from
i up to maximum, and then observing that every increment from
i + j + 2ij to
i + (j + 1) + 2i(j + 1) is just
i + j + 2ij + (1 + 2i) or just the value of the sieving base prime/factor, but that is exactly the algorithm for the "odds-only" SoE. Once we've optimized the SoS into the SoE, we can apply the same further optimizations as it now identical. So the SoS can not be considered as a competitor as in its simple form it is much less efficient and in its maximally optimized form it is the SoE.
The SoA is by definition a wheel factorized sieve by the prime factors of 2, 3, and 5. The SoA once (and perhaps still does) enjoy quite a bit of Internet hype due to it's very good big-O performance of O(N). However, while it does perform according to that relation with a constant about 0.2517 times N number of culls starting at a very low N value, all is not so rosy as believed: It doesn't match that combined performance for any reasonably large range requiring page segmentation where primes squares-free spans get huge as compared to the page segment range and the complexity of the continuously increasing culling span means that the true combined big-O performance is much worse than that of the fully wheel optimized Sieve of Eratosthenes while the code complexity in implementing it even this efficiently is worse than the maximally wheel factorized SoE. Much of the confusion comes about due to the reference page segmented implementation of the SoE by Atkin and Berstein, which, while reasonably fast in sieving to a billion, did not prove (even close) its claim of linear asymptotic big-O complexity with increasing range as it is very slow for larger ranges, and only beat the reference SoE to which it is compared for a range of a billion by artificially limiting the level of wheel factorization of that implementation. As to the culling speed, due to the increased complexity of the span increasing with every successive operation, typical speed is about twice as slow as for the SoE in CPU cycles per operation, so it would have to have half the number of operations as the maximally wheel factorized SoE, which it never does within practical ranges.