Melissa, thank you for taking my comments as constructively as they were meant. and not to worry, i'm sure i'm not the only one who enjoyed this little exercise and learned a lot from it!-) and even if we've found more that you expected, you're quite right, one doesn't get anywhere unless someone starts, noticing that something interesting is going on, raising questions about it, supplying the first answers, and documenting the results when the discussion quiets down.
I think modulus is a bit of a red herring -- its a symptom, not the disease.
you mean i'm distracting the primates with smoked fish?-) perhaps you're right, but let me illustrate what i meant anyway. assuming that mod is not a primitive, but has to be computed some way, perhaps by a fragment of gcd, here's a look at the recursion for computing mod x y: mods a b | b>a = [(a,b)] | otherwise = (a,b):mods (a-b) b now, if we take that folklore code again, and have a look at the sieves for 5 and 7, after 70 has already been filtered out by the sieve for 2 (first column has the input list, followed by the unfolded mod-recursion for each element): Main> putStrLn $ unlines [show $ mods x 5|x<-[3,5..90],(x`mod`3)>0] [(5,5),(0,5)] [(7,5),(2,5)] .. [(67,5),(62,5),(57,5),(52,5),(47,5),(42,5),(37,5),(32,5),(27,5),(22,5),(17,5),(12,5),(7,5),(2,5)] [(71,5),(66,5),(61,5),(56,5),(51,5),(46,5),(41,5),(36,5),(31,5),(26,5),(21,5),(16,5),(11,5),(6,5),(1,5)] .. [(85,5),(80,5),(75,5),(70,5),(65,5),(60,5),..,(20,5),(15,5),(10,5),(5,5),(0,5)] [(89,5),(84,5),(79,5),(74,5),(69,5),(64,5),(59,5),..,(19,5),(14,5),(9,5),(4,5)] Main> putStrLn $ unlines [show $ mods x 7|x<-[3,5..90],(x`mod`3)>0,x`mod`5>0] [(7,7),(0,7)] [(11,7),(4,7)] .. [(67,7),(60,7),(53,7),(46,7),(39,7),(32,7),(25,7),(18,7),(11,7),(4,7)] [(71,7),(64,7),(57,7),(50,7),(43,7),(36,7),(29,7),(22,7),(15,7),(8,7),(1,7)] [(73,7),(66,7),(59,7),(52,7),(45,7),(38,7),(31,7),(24,7),(17,7),(10,7),(3,7)] [(77,7),(70,7),(63,7),(56,7),(49,7),(42,7),(35,7),(28,7),(21,7),(14,7),(7,7),(0,7)] [(79,7),(72,7),(65,7),(58,7),(51,7),(44,7),(37,7),(30,7),(23,7),(16,7),(9,7),(2,7)] [(83,7),(76,7),(69,7),(62,7),(55,7),(48,7),(41,7),(34,7),(27,7),(20,7),(13,7),(6,7)] [(89,7),(82,7),(75,7),(68,7),(61,7),(54,7),(47,7),(40,7),(33,7),(26,7),(19,7),(12,7),(5,7)] we find that 70 is indeed revisted by both (eg, 85 and 77), even though it is no longer in the input list (first columns). by aligning the mod-recursion with going through the list of prime candidates, we save ourselves a lot of recomputation by sharing, eg the recursion for mod 91 7 overlaps with, and can share that of mod 77 7, and so on Main> mods 91 7 [(91,7),(84,7),(77,7),(70,7),(63,7),(56,7),(49,7),(42,7),(35,7),(28,7),(21,7),(14,7),(7,7),(0,7)] which is what i meant with incrementally computing the modulus (if i know the result of mod 77 7, i can use that to compute mod 91 7), instead of doing it from scratch for each candidate. both versions have to pass by 70 at least three times, even though the first filter is sufficient to remove that number as a candidate, again in both versions. different people think differently, and i found the idea of incremental vs from-scratch modulus helpful in explaining the performance differences, and the idea of explicit vs implicit sieves helpful in explaining the resource usage difference between the folklore and the so-called naive version. but others might find the cross-out footprint more helpful. going beyond simple sieves, wheel sieves are all about using the advantages of incremental computations, but they still make their wheels explicit, and suffer resource usage problems, which indirectly harm their performance. i still suspect that there's an incremental and implicit variant of the incremental, but explicit wheel sieve.
[transforming sieve variants into each other] At some point in the middle, you'll have something that can be viewed from both perspectives. But the existence of such a progression of algorithms between algorithm A and algorithm B doesn't mean that A and B are fundamentally the same.
i would hope that one of two things would happen: either one could get from A to B via equivalence-preserving transformations (for a suitably chosen form of equivalence), in which case A and B would be equivalent, or one would need to do non-equivalence-perserving transformations at some point in the middle, clearly exposing the implementation decisions that distinguish B from A (if B is simply more concrete than A, prescribing efficient behaviour where A just allows it, then we are into the subject of refinement).
Perhaps we're saying the same thing and misunderstanding each other,
quite possibly, so i'll stop here, with a closing remark
From an operational behavior standpoint, the ``folklore sieve'' just doesn't do the same thing. Every expectation people have about the behavior of the Sieve of Eratosthenes is confounded by the ``folklore sieve''. Although, if all you're looking for is a short and elegant- looking *specification* that brings to mind the Sieve of Eratosthenes, the ``folklore sieve'' will suit just fine. To me though, the Sieve of Eratosthenes doesn't exist as a specification for primality -- their are easier definitions -- it serves as a clever way to find primes (and factor composites) efficiently. The fundamental operational details matter.
indeed, there are specifications of properties (1), specifications of algorithms (2), and specifications of operational behaviour (3), in order of decreasing abstraction/increasing detail. functional languages are declarative, but encourage/require us to be more concrete about operational behaviour than, say, search-based languages. haskellers don't specify a property, then hope that the implementation will find an algorithm, but neither do they usually pin down the operational behaviour precisely enough to ensure efficient realisation. and it does often surprise people that (2) is easy and beautiful, but potentially horribly inefficient, and that efficiency can be improved substantially by being more concrete in the direction of (3), without changing the language, but after investing some thought into the difference between default behaviour and desired behaviour. and it did surprise me to see so many different approaches, which got me started thinking about how they might be linked to each other, rather than invented separately. so, yes, i agree that a suitably expanded paper documenting the issues for prime sieves, perhaps linking to similar cases, such as the infamous quicksort, would be valuable. claus