Talk:Sieve of Eratosthenes

Optimizations

My Forth is very rusty, but it looks like your Forth version of the Sieve_of_Eratosthenes lacks both important features of the sieve: The outer loop should stop at the sqrt of the total limit, and the inner loop should start with the square of the just detected prime (any other multiples must already have been crossed out). Without those, the sieve won't be faster than to trial division for each number. Some other implementations seem to have the same problem. (And some only sieve odd numbers, while others don't, making overall comparison between languages more difficult). Maybe all this should also be clarified in the task description? Dirkt 02:48, 2 December 2007 (MST)

I"m ambivalent about these optimizations. The half dozen or so sieve implementations I based this on did not contain these optimizations (including those on similar comparison sites, such as the Computer Language Shootout). Also when I measured this a while ago, the speedup of these optimizations was minimal. For small ranges, the other optimization to assume 2 is prime (i.e. only examine odd numbers) had a greater effect, both in time and space. (Out of curiosity, did Eratosthenes himself document these optimizations, or were they found later?)

As to trial division, you are assuming division and square root are cheap. The simple implementation only uses addition (multiplication may not be implemented on a given processor).

I think keeping the tasks simple should be a goal of Rosetta Code. Keeping things simple encourages folks to donate their time in writing task solutions.

I agree that the examples should all use the same algorithm. The algorithm we decide upon should be described in the task description. --IanOsgood 07:53, 2 December 2007 (MST)

The difference only starts to kick in for large numbers. It's a similar story with the purely functional Haskell version I mentioned - nobody really tried this for large numbers, so nobody discovered it was flawed for a long time. And yes, only examining odd numbers (or using wheels other than this simple one that is only based on the prime 2) do indeed speed up things quite a lot, even for large limits.

By "trial division", I didn't mean actual cost, but asymptotic cost. The 'trick' behind the Sieve of Eratosthenes is to avoid checking whether a prime p divides some remaining candidate k if it is already known that k is composite. Trial division, in contrast, performs this check for every p and every k. And because the sieve only does a fraction of those checks, it's much faster.

The above is wrong! Real difference between trial division and sieve is that in trial division most divisons is "useless": when dividing n by k we just learn that k is not a divisor of n. Sieve only looks at pairs n,k such that n divides k. Even most naive Sieve of Eratosthenes has complexity n*log(n), while using trial division and stopping at sqare root we are close to n*sqrt(n). Stopping sieve at sqrt(n) saves half of the work, so it is really comparable to looking only at odd numbers. Starting inner loop at p^2 has negligable effect.

The actual cost of sum versus multiplication is recovered quickly by the better asymptotic behavior (I can do the math for you, if you want me to).

I agree that things should be kept simple (and therefore I would prefer to simply test for all numbers, not only odd, or not those with remainder 1 or 5 (mod 6), etc.), but these two things (which are really two sides of the same idea - if you start crossing at p*p for each prime p, than of course you can stop crossing once p*p is over the limit) are really easy to implement and do affect asymptotic cost, so I'd like to see them included. Dirkt 09:24, 2 December 2007 (MST)

FYI, if you apply the outer loop optimization (loop from 2 to sqrt n), then you must also print the primes in a second loop from 2 to n. Many of the examples are now incorrect as they stand. --IanOsgood 10:15, 2 December 2007 (MST)

Yes, if one insists that the primes must actually be printed. But the task only says "find all the primes", and keeping the sieve around is actually the less space intensive way to store them (as I found out the hard way some time ago).

Anyway, I think that's not the main point :-) And the examples are first of all *different*. If you think that from the point of view of comparing languages, an inefficient Sieve of Eratosthenes is better, then the task should clearly say so, and all examples should be adapted. However, as I said, I think that those two optimasations are simple enough, and worth including. Dirkt 01:38, 3 December 2007 (MST)

If I might chime in...

I'm not really familiar with the Sieve of Eratosthenes, but perhaps a page could be taken from FizzBuzz and 100 Doors? Language sections in those pages are subsected to reflect optimized vs unoptimized approaches. For the purposes of easy comparison, perhaps such a subsection would be appropriate here?--Short Circuit 12:23, 3 December 2007 (MST)

I personally think the 100 doors "optimized" solutions are useless, adding nothing compared to the random number task, and cluttering up the table of contents. In fact, I suggested the Sieve of Eratosthenes task because I didn't like 100 doors in the first place!

I don't really have anything against the optimized bounds for the sieve (Wikipedia mentions it, and I have a Forth program ready to go). Just make sure the algorithm is documented in the task description. --IanOsgood 16:56, 3 December 2007 (MST)

In the task description: "you shouldn't optimize by using pre-computed wheels, i.e. assume you need only to cross out odd numbers (wheel based on 2), numbers equal to 1 or 5 modulo 6 (wheel based on 2 and 3)"

This might be clearer if it read "don't assume". The word "shouldn't" is supposed to apply distributively: you shouldn't optimize ... you shouldn't assume. But it's actually open to being interpreted as the opposite of the intended meaning, which is: Don't assume that the only numbers you need to sieve are those supplied by a pre-computed wheel. Adding the word "don't" would eliminate the ambiguity. Should I change it? --Snoman 01:26, 16 July 2010 (UTC)

I went ahead and made this change. Please feel free to undo. --Snoman 18:26, 16 July 2010 (UTC)

Also, I noticed that the Ruby function was misspelled. Fixed. :-) --Snoman 03:34, 16 July 2010 (UTC)

Python

This task can also be handled by the NZMATH modules prime and arith1 to enable its generator_eratosthenes function.--Billymac00 02:45, 3 January 2011 (UTC)

You can add a code example that shows the use of the module, as long as there's already a code example that satisfies the task as written. --Michael Mol 04:13, 3 January 2011 (UTC)

The not-a-sieve method

The first code sample under Perl is indeed not a sieve method. Is there a proper procedure to remove it--or can I just remove it? (and who in the world uses a one space indent?) --Ledrug 09:13, 12 June 2011 (UTC)

Sometimes we might leave an example that deviates from the task especially if it says how it deviates from the task. If someone did a proper Perl sieve, then that would definitely be the time to consider removing this one. As it stands, its good to ask/inform the original author? --Paddy3118 12:07, 12 June 2011 (UTC)

The wrong code was added by an IP with it being his only contrib, a long time ago. The note was added by someone else, the code was edited by someone else (for stylistic reasons, and it's still bad looking), and there are three other, correct implementations in the same section, by someone else. This really screams "delete" IMO. --Ledrug 00:27, 13 June 2011 (UTC)

I have replaced that code with a sieve implementation. --Rdm 14:35, 13 June 2011 (UTC)

Question zkl: It has been marked as incorrect. Could you (the marker) explain why this is? The code implements the animated algorithm illustrated in the Wikipedia article very closely. -- resolved, thank you.

unix shell versions

User:Kernigh has added a note that the shell version use trial division (I don't quite understand how they actually works, it's difficult to trace), I have added on version that is actually using the sieve operation at the end. --AlexLehm 23:09, 28 October 2011 (UTC)

NetRexx Performance ??

Better performing program requested

Got a dramatically better version from Kermit Kiser (thanks) and shall post it later

when I have understood the changes.

--Walterpachl 04:58, 24 July 2012 (UTC)

Added the improved version.

For high=200000 0.6 instead of 6.8 seconds.

--Walterpachl 16:22, 24 July 2012 (UTC)

Please re-check with more memory

It looks like it has spent most of the time in garbage collection before failing, explaining this performance. Please rerun with -Xms256M -Xmx512M at least. rvjansen 10:27, 23 July 2012 (UTC)

I shall try this in the evening. Thanks --

but couldn't

by the way for high=500000 PL/I needs 5 milliseconds on TSO!

for high=600000 it bombs with the storage I have

Walterpachl 10:40, 23 July 2012 (UTC)

Java

Please replace the horribly inefficient published Java code with the following:

<lang java5>import java.util.ArrayList; import java.util.List;

public class Eratosthenes {

   public List<Integer> sieve(Integer n) {
       
       List<Integer> primes = new ArrayList<Integer>(n);
       
       boolean[] isComposite = new boolean[n + 1];
       
       for(int i = 2; i <= n; i++) {
           
           if(!isComposite[i]) {
               
               primes.add(i);
               
               for(int j = i * i; j >= 0 && j <= n; j += i) {
                   isComposite[j] = true;
               }
           }
       }
       
       return primes;
   }
   

}</lang>

The problem here is the concept of removing values. Even the "optimisation" of filling nums with odd values is no optimisation at all. Trying to sieve 40004 for the posted algorithm takes around 3.292s ("optimised") while the algorithm above takes 0.006s and the bitset sieve clocks at 0.008s. Thanks --xelamitchell 19:50, 7 October 2013 (UTC)

... Except that the above Java code isn't a Sieve of Eratosthenes.   A SoE algorithm doesn't TEST for primality, it just removes all composites (and sometimes unity);   what's left is a (somehow marked/indicated) list/array of primes [up to the (original) highest element in the list/array of integers]. -- Gerard Schildberger (talk) 22:50, 7 October 2013 (UTC)

Hmm, I'm not sure. If by primality check you mean the line "if(!isComposite[i])" then it is doing the same work of the posted code's "nums.remove()" (finding the next valid prime to begin marking, it is not a method merely a reference to the array) only much more efficiently. Also my code is truer to the algorithm (in terms of algorithmic description, pseudocode, end representation (having a marked list of values and a separate list of collected primes by the end of the run) and performance) as described in Wikipedia - Sieve of Eratosthenes than the posted code. I don't know where you got the requirement that composites must be removed, the original algorithm merely states they must be marked iteratively. --xelamitchell 10:22, 8 October 2013 (UTC)

My bad.   I should've said something like:   ... it "just" removes/marks/indicates all composites ...     And then, the primes are those integers not marked (or the integers that are left remaining). -- Gerard Schildberger (talk) 20:12, 10 October 2013 (UTC)

So what exactly do you mean by "primality check" in this case? If you check most of the sieve codes for other languages they are very close to my code (check the array of values to see if the current value is a prime (by the fact that it is marked true), if it is a prime mark all it's multiples as composites iteratively). --xelamitchell 10:18, 11 October 2013 (UTC)

I think the BitSet approach at the bottom of the Java example does something like this. I bet the timings would be similar. --Mwn3d (talk) 18:33, 11 March 2014 (UTC)

Python translated to Java

The Java incremental "infinite" generator as translated from the Python version uses the short 32-bit int type and thus suffers from an early overflow problem limiting the useful sieve range. This is because in Java, short fixed range 32-bit two's complement int's have a range from -2^31 or -2,147,483,648 to 2^31 - 1 or 2,147,483,647 and by default don't have an error exception on overflow, so "roll over" from the highest maximum positive value to negative numbers when that value is exceeded. Java's default integer literals are these short 32-bit integers unless suffixes are used along with type designations to change to the "Long/long" types or to the "BigInteger" (arbitrary precision) type. This is unlike Python 2, which automatically promotes the type to the arbitrary precision "long" integer type when the value exceeds the "sys.maxint" value. For the Incremental Sieve of Eratosthenes using 32-bit signed integers as described above, this Java overflow starts for the next prime above the floor of the square root of 2 ^ 31 - 1 or the prime value 46349, for which the square is 2148229801, and due to roll over will be recorded as -2146737495. This negative number then becomes the highest priority (lowest value) in the Priority Queue, at least until some other square value produces a number even closer to the negative minimum value. No positive prime candidate will ever match the top of the queue, meaning that all subsequent positive candidate numbers will be flagged as primes, the prime multiple culling sequences will never be advanced, and the algorithm is incorrect from that point on.

The development of the incremental sieve as per Melissa O'Neill's orginal paper in Haskell from which most of these algorithms are derived would have had the same problem except that Haskell defaults to the infinite precision Integer type rather than to Int32, which would have masked the problem. O'Neill went on to do further work using postponed adding of base primes to data structures as done for the improved algorithms. Doing this greatly increases the sieve range for a given number precision without overflow and possible removing the requirement for the less efficient infinite precision Integer type while greatly reducing the memory footprint and improving the run efficiency.

With the fix to a higher precision type, the Priority Queue code is adequate for sieving trivial ranges of primes up to a few million as for solving Euler problems but for higher ranges of a billion or higher, the use of a hash table based HashMap is somewhat better because it does not have the additional log n computational complexity overhead for sequence re-insertions, but even that is 10's of times slower than using an "infinite" generator/iterator using page segmentation as per the JavaScript example due to the constant overhead of the hashing computations as compared to direct array access.

This bug highlights a problem with the task as described since even if there is a output shown, showing the primes up to 100 doesn't show that the algorithm has been tested over various subsets of the full range or any consideration of the limitations of the algorithm has been made.

Python 2.x int's automatically extend to longs, and so may not show the problem you state above. (Sorry that it has taken me so long to look into this):

<lang python>Python 2.7.5 (default, May 15 2013, 22:43:36) [MSC v.1500 32 bit (Intel)] on win32

Type "copyright", "credits" or "license()" for more information. >>> x = 2147483647 >>> x 2147483647 >>> type(x) <type 'int'> >>> x = x + 1 >>> type(x) <type 'long'> >>> x 2147483648L >>> </lang>

--Paddy3118 (talk) 09:06, 24 June 2014 (UTC)

Yes, I looked into it further as well and the problem does not apply to Python but only to the Java implementation in its current form using 32-bit int's. I have corrected the comment above to match these findings, leaving the comment as related to the Java code.--GordonBGood (talk) 11:07, 24 June 2014 (UTC)

Classic REXX timings

It might be a better idea to time the Classic REXX programs with a classic REXX   (if it serves a useful purpose).

ooRexx programs should be entered under the ooRexx language entry (and their timings, if any).

As I understand the Rosetta Code philosophy (theology? [sic]), it isn't considered kosher to compare timings for different languages, that's not the purpose of this forum.   Comparing two different versions of (and in) the same language is (maybe) supposedly OK, but maybe the absolute times should be expressed as percentages instead (if at all).   Another possibility is to just move the relative speed merits of the pertinent programming language entries to this talk/discussion page (with caveats).   It doesn't make sense to me to execute a (classic) REXX program using ooRexx (for timing purposes) under the (Classic) REXX language entry   (even though it can't execute as-is anyway). -- Gerard Schildberger (talk) 23:06, 24 July 2014 (UTC)

All the Classic REXX programs that I programmed and entered were designed/written to be run with a Classic REXX interpreter, not ooRexx.   I very rarely post timings for the REXX programs I enter, except to sometimes say that   a   version is   xxx%   times faster (or just faster) than a previous entry that I wrote/entered.   If it's slower (and a CPU hog), I almost never enter it unless it demonstrates a different or novel technique, or adds more function.   Sometimes, I add a very heavily commentized version. -- Gerard Schildberger (talk) 23:06, 24 July 2014 (UTC)

I would not be adverse to the idea of removing the whole timing business.   As improvements (or any changes,for that matter) are made, the timings become obsolete (or at least, outdated). -- Gerard Schildberger (talk) 23:06, 24 July 2014 (UTC)

---

Trial division sieves should be moved from here

As the title says. The context for this is the discussion at Eli Barzilay's talk page.

Here's my response to that discussion.

It is most definitely a sieve, just not the sieve of Eratosthenes as it is understood today, and at least as early as 1772 -- time of publication of the article by Horsley, referenced in the Wikipedia article, in which he much trashes Nicomachus (yes, trashes, it is beyond criticism), incidentally, for being unable to convey clearly the essence of Eratosthenes's method. Horsley in fact says that the impression as if it was about testing divisibility of each number in separation, is "preposterous" and that a brilliant mind such as Eratosthenes's couldn't possibly have chosen such lowly route when in fact the bright gem, a treasure of a true formulation was possible - IIRC. I'm paraphrasing.

It indeed is a trial division sieve - a sieve where the removal is done by trying out the divisions by primes, one prime after another, as opposed to the "true" sieve of Eratosthenes finding out the composites as primes' multiples, and getting the primes for free, in the gaps between the multiples, as "what's left" after all the numbers are let through "the sieve" (when holes are made under the composites).

I.e. the sieve is constructed from primes, by counting (i.e. by repeated additions); no number needs be attempted to be divided by any other number. And that's the difference between the two.

A defining characteristic of an algorithm is its theoretical time complexity. The sieve of Eratosthenes' complexity is N log (log N) ~ n log n log (log n), for n primes below N; the (optimal) trial division sieve's - N^1.5/(log N)^2 ~ n^1.5/(log n)^0.5, as derived in M. O'Neill's paper. Granted, that paper is short on clear-cut explanations, but it has the needed math derivations nonetheless.

The real question we're left with here, is whether to open up a new page for "trial division sieves", or to add - both Scala and Racket, and any other entry's there might be - to the Primality by trial division page. Which I did, incidentally, for the Haskell entry, long time ago, where we can find this unoptimized simple famous code both in its original, and optimized formulation.

I propose all such entries are, indeed, moved to Primality by trial division, for now; and if the special page gets created for them later, they can be further moved there. Right now, having trial division sieves under the heading of "sieve of Eratosthenes", on the page which explicitly forbids anything other than the proper algorithm, seems to be a no-go proposition. -- WillNess (talk) 19:59, 10 September 2014 (UTC)

+1 --Paddy3118 (talk) 20:18, 10 September 2014 (UTC)