Talk:Sieve of Eratosthenes: Difference between revisions
→Trial division sieves should be moved from here
Line 212:
::::::: The "magic" trick is in postponement - check [[Primality by trial division#Postponed sieve by trial division|the Haskell entry]] to see what I mean (also [http://stackoverflow.com/questions/6802112/why-is-this-scala-prime-generation-so-slow-memory-intensive/14821313#14821313 explained here], among other places). I've also wrote quite a lot of verbiage on the haskellwiki prime numbers page about that. The author just missed that small step, and went all the way to do the proper implementation (which still had no postponement, in the article, but the priority queue kept the issue hidden, for a while), saw the enormous speed difference, and wrote about it (I guess). But there really is no giant leap, because there is an intermediate step that the author glossed over, so there are two big steps instead of one giant jump. Still impressive, but not that ''flabbergasting''. And unfortunately, her explanations were lacking in clarity. The basics of it is, coming back full circle, the distinction between TD-sieve and "genuine" ;) SoE: the first tests each number by ''all primes'' below it (or its square root), potentially, whereas the other generates for each prime its multiples starting from it (or its square) - and thus generates each composite only from ''its actual prime factors''. The first ever corecursive algorithm. Exciting stuff. :)
:::::::: The author didn't say as much, but she did say that the Turner's sieve is equivalent to the trial division which uses all the primes below the test number. Hence the complexity of ''O(n^2)'' to produce ''n'' primes. Then she actually derived the complexity of producing primes with filtering by trial division up to the ''sqrt'' of the test number (which is achieved with the postponement technique). Which is ''O(n^2/(log n)^0.5)''. She didn't show any code in the form of ''sieve'' that would achieve that, but instead the one with ''filter'', AFAICR. --[[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 15:03, 12 September 2014 (UTC)
::::::: I'm having second thoughts about the new page now (bear with me). See, the Greek "koskinon" is a noun; it is "sieve" in English, but "sieve" in English is also a verb, a synonym of "filter". I think, ''that'' was the cause of much confusion about this issue. With the Trial Division, it is very easy and natural to use it to produce sequences of primes, unbound as well as bound, by means of filtering. And Turner's code is only "sieve" in as much as it is "filter", it doesn't build "a sieve". And how will we distinguish between the TD "sieve" and TD "filter"? The first does it in separate steps, filtering separately by each prime, and the other does that by testing against a list of primes, by a short-circuiting logic? That's not a ''basic'' distinction, [[Primality by trial division#Segmented Generate and Test|that's an optimization]]! What will we do, allow the former but forbid the latter, on the new page??
| |||