Talk:Sieve of Eratosthenes: Difference between revisions
→Trial division sieves should be moved from here: typos
Line 211:
::::::Well, I think that the main difficulty in a new page is explaining what it is, but it sounds like you have that part clear. Probably also good to make it close enough to the SoE page, maybe have references from each one to the other which can also simplify the explanation. Moving the entries should be easy then, since they're not too linked to the current text around them (perhaps except for Haskell if you've done that a while ago). BTW, I've added SoE versions now, with the same three versions -- it's just that their additional verbosity makes the equivalence between the three versions harder to see. They're also roughly as fast as the other version, mostly because I'm too lazy to find out if there's some magic possible that's supposed to make it much faster. (In any case, they're both fast enough to make finding the 19th prime number very fast, and Racket's Lazy language is really not something that can be considered "fast" -- so I still have no idea what that paper mumbled about.) --[[User:Elibarzilay|Elibarzilay]] ([[User talk:Elibarzilay|talk]]) 08:22, 12 September 2014 (UTC)
::::::: 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
::::::: 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
::::::: So I'm not sure about this. What do you think? I proposed to amend the description of TD page to include generating sequences; we may mention the word "sieve" there, and of course discuss the similarity and distinction etc.... (???) -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 10:03, 12 September 2014 (UTC)
| |||