Talk:Sieve of Eratosthenes: Difference between revisions
Content added Content deleted
(→Trial division sieves should be moved from here: rename it as "span"?) |
(→Trial division sieves should be moved from here: reply to old remark that I missed) |
||
| Line 217: | Line 217: | ||
::::::::: 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.) |
::::::::: 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) |
::::::::: 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) |
||
:::::::::: Elibarzilay: (sorry, missed your remark before): the big conceptual difference is that it's using the [http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29#Linear_vs._tree-like_folds tree-like folding] function [http://en.wikipedia.org/wiki/Fold_(higher-order_function)#Tree-like_folds ''foldi''] instead of the linear folding of ''foldr'', for the logarithmic complexity advantage. M.O'Neill derives Bird sieve's complexity at above n^1.5 (in ''n'' primes produced) but the tree folding code runs empirically at the same orders of growth (~ n^1.2..1.25) as her PQ-based code, which is probably ''n (log n)^2 log(log n)''. Earliest such code that I know of is [https://www.haskell.org/pipermail/haskell-cafe/2007-July/029077.html Jul 16 2007 post by Dave Bayer]. -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 21:46, 10 November 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?? |
::::::: 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?? |
||