Sieve of Eratosthenes: Difference between revisions
m
→With Wheel: Haskell - correctly accidentally merging two sections, corrected comments...
GordonBGood (talk | contribs) m (→With Wheel: Haskell - minor touch-ups and comments...) |
GordonBGood (talk | contribs) m (→With Wheel: Haskell - correctly accidentally merging two sections, corrected comments...) |
||
Line 5,666:
| x < y = x : union xs' ys
| y < x = y : union xs ys'
| otherwise = x : union xs' ys' -- x and y must be equal!</lang>
When compiled with -O2 optimization and -fllvm (the LLVM back end), the above code is over twice as fast as the Odds-Only version as it should be as that is about the ratio of reduced operations minus some slightly increased operation complexity, sieving the primes to a hundred million in about seven seconds on a modern middle range desktop computer. It is almost twice as fast as the "primesW" version due to the increased algorithmic efficiency!
Line 5,762:
where (c, adv) = case peekMinPQ table of Just ct -> ct `seq` ct</lang>
The above code is over five times faster than the previous (O'Neill) Priority Queue code
Since the Tree-Folding version above includes the minor changes to work with a factorization wheel, this should have the same minor modifications for comparison purposes, with the code as follows:
Line 5,798:
where (c, (a:as')) = case peekMinPQ table of Just ct -> ct `seq` ct</lang>
Compiled with -O2 optimization and -fllvm (the LLVM back end), this code gains about the expected ratio in performance in sieving to a range of a hundred million, sieving to this range in about five seconds on a modern medium range desktop computer. This is likely the fastest purely functional incremental type SoE useful for moderate ranges up to about a hundred million to a billion.
===Page Segmented Sieve using a mutable unboxed array===
| |||