0
$\begingroup$

Relevant Information:
Sieve of Eratosthenes
Sieve of Sundaram

Suppose I want to generate all primes in [2,n], and I have both of these algorithms at my disposal to get the job done. Which is preferable under what conditions?

I read that Sundaram runs in O(n log n) time, whereas Eratosthenes runs in O(n log log n) time, so it seems that Eratosthenes is preferable. However, that is just a very superficial evaluation. Are there other factors (aside from ease of implementation) to be considered? Which is the 'better' algorithm?

$\endgroup$
  • $\begingroup$ A practical approach that might work: use whatever algorithm (or look primes up from some database) and precompute a (large) array $P$ of primes. You could then index the array and get the $i$th prime from $P[i]$ in $O(1)$ time. $\endgroup$ – Juho Dec 19 '13 at 10:44
  • 2
    $\begingroup$ The question "Are there other factors (aside from ease of implementation) to be considered?" is practical. The question "Which is the 'better' algorithm?" is not practical an subjective which is not a good fit for a question on this site. I would recommend that you remove the second question or reword it from a subjective question into a practical question that can be answered with a practical answer. $\endgroup$ – Guy Coder Dec 19 '13 at 11:12
  • 2
    $\begingroup$ What have you tried? Have you tried implementing both of them and benchmarking them to see how fast they run? Seems like a straightforward and obvious thing to try. $\endgroup$ – D.W. Dec 19 '13 at 18:39
  • $\begingroup$ Since the question compares two of the common prime sieving algorithms, the Sieve of Atkin should really also be included to complete the common considerations as I do in my answer... $\endgroup$ – GordonBGood Apr 21 at 7:49
3
$\begingroup$

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:

  1. 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.
  2. 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.
  3. 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:

  1. The Sieve of Eratosthenes (SoE) - O(N log(log (N)))
  2. The Sieve of Sundaram (SoS) - O(N log(N))
  3. The Sieve of Atkin (SoA) - O(N) (i've added this one as it is usually considered...)

Let's consider these in order:

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

  2. The unmodified SoS algorithm can never approach the performance of other sieves due to not specifying the proper limits for the i and 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.

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

In conclusion, for large sieving ranges using page segmentation, the Page Segmented SoE is a clear winner with the number of cull operations ranging only up to about 0.35 to very large ranges of 1e16 or more and the number of machine cycles when efficiently compiled to native machine code as little as under two CPU clock cycles per operation for small ranges under a billion and only increasing to the order of ten CPU cycles per operation for very large ranges (of about 1e19) in some common implementations such as primesieve, which can also be multi-threaded for even faster execution times. Even when compiled in Just-In-Time (JIT) environments such as the Java Virtual Machine (JVM), Microsoft's DotNet, or even JavaScript engines as are builtin to modern browsers, the performance is still only about ten CPU cycles per operation with the number of operations the same. In contrast, the unmodified SoS is many times slower and when fully optimized just becomes the SoE with its only feature over the SoE that it doesn't need the secondary primes feed for a page segmented version and thus the code optimized to the same extent is somewhat simpler, and the SoA never comes anywhere close to the number of CPU clock cycles per cull operation at any point as for larger culling ranges such that the reduced number of culling operations is never enough lower to make up for this discrepancy nor for the increased complexity of implementation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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