Anonymous user
Talk:Sieve of Eratosthenes: Difference between revisions
→Trial division sieves should be moved from here
(→Trial division sieves should be moved from here: new draft task page created) |
|||
Line 214:
:::::::: 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)
::::::::: Well, the postponement trick is nice, but I don't see how it can apply to the SoE code. As a quick experiment, I implemented it for the plain (non-E) sieve, and indeed it made it much faster. I then implemented the Bird SoE algorithm and it's faster than the version I had before -- but the plain sieve + postponement trick is about twice faster than my Bird implementation. (I'll put both of the new things on the two pages, if you care to look at them.)
::::::::: Also, looking at your SO answer, I don't see the conceptual difference between what you refer to as the Bird algorithm and the one at the end of the answer: the two minor differences that I see are (a) it works only on non-even numbers; (b) you use the union' thing to always spit out the first element which is done in Bird's code by pulling out the first p*p out of the union code (in fact, I first didn't do this pulling-out, and resolved the resulting infinite loop by making my merge do the same thing that your union' does). --[[User:Elibarzilay|Elibarzilay]] ([[User talk:Elibarzilay|talk]]) 19:32, 13 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??
Line 222 ⟶ 225:
:* I was being bold and went ahead and created a draft task page as discussed above: [[Sequence of primes by Trial Division]]. I don't want to be ''too'' bold, so someone else please remove the draft status, if you agree. -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 14:06, 13 September 2014 (UTC)
:: I don't consider myself active enough to remove the draft thing too... but of course I think that it's the right thing. --[[User:Elibarzilay|Elibarzilay]] ([[User talk:Elibarzilay|talk]]) 19:32, 13 September 2014 (UTC)
| |||