Talk:Sieve of Eratosthenes: Difference between revisions
→Trial division sieves should be moved from here: respond
Line 230:
::: WillNess: Sorry, but continuing down here... What I did now is: (1) Removed the sequence versions from the PbTD page since they're on the new page; (2) I first edited your version on the SoE page, but then realized that my attempt at doing the same to the Bird code is shorter and faster, so I dropped both in *instead* of your code -- I don't like removing other people's code, but I decided on doing that because it's better on speed, clarity, and being more idiomatic (feel free to tweak it however you like, specifically, the timings might be off); (3) On the new page, I've added a version that is optimized with the postponement trick.
::: FWIW, I'm getting results that still don't go in-line with the conclusion that a proper SoE should be faster: the "unfaithful" plain sieve with the postponement trick <1> is about twice faster than my Bird implementation with the same trick <3>, and that is a tiny bit faster than my Bird implementation without the trick <2>, while your version of the proper SoE with the trick is about three times slower than <1>. Based on the paper and what you said, I'd expect <1> and and <2> to be roughly the same, and <3>/<4> to be much faster. --[[User:Elibarzilay|Elibarzilay]] ([[User talk:Elibarzilay|talk]]) 20:16, 13 September 2014 (UTC)
::::Elibarzilay: good to have a discussion with you. :) About Bird (your <2>) (and it's Richard Bird, not William Byrd): O'Neill actually derives the complexity for it too, and proves it's slightly worse than the optimal TD (your <1>). The trick to making it yet faster (which isn't in the paper) is to fold the composites ''in a tree'', substituting [https://en.wikipedia.org/wiki/Fold_(higher-order_function)#Tree-like_folds "foldi" for "foldr"]. I have a Scheme entry with SICP styled streams, that does that (and of course [[Sieve_of_Eratosthenes#List-based_tree-merging_incremental_sieve|the Haskell entry]] itself). The original version at [http://www.haskell.org/haskellwiki/Prime_numbers_miscellaneous#Implicit_Heap haskellwiki].
::::And of course what we should be comparing are [http://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth empirical orders of growth], not constant factors. So if one is constantly slower than the other by the same factor ''at several size points'', it's fine. TD with postponement (i.e. the optimal TD, your <1>) runs pretty well for lower ranges (10k-20k primes) in Haskell too. It's because its complexity is O(n^1.5/(log n)^0.5) and at low ranges ''log'' is approximated by higher power law coefficient, i.e. its influence can be sizeable (I've commonly seen n^1.3 for low ranges of OTD, going steadily to n^1.45..49 for higher ranges, as it should).
::::About your edits: there's no need to add postponement to Bird's code; it achieves the same effect on its own, because it folds to the right. Postponement achieves the same effect laboriously, and should still be worse computationally [http://www.haskell.org/haskellwiki/Prime_numbers#Linear_merging because it folds from the left]. My version should probably be restored (or maybe you have a tweak on it) because it is a stepping stone from the simple lazy version ''to'' the Bird's version. (It's strange that your "postponed Bird" is slightly faster than the straight version of it.) -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 09:17, 14 September 2014 (UTC)
| |||