2007/7/15, Hugh Perkins
There's really a tendency in this newsgroup to point people to huge documents, when a small copy and paste would make the answer so much more accessible ;-)
I was pointing you on a document of quite honest size in my opinion, and not really hard to read... But well if you want a piece of code, here it is : -- merge xs@(x:xt) ys@(y:yt) = case compare x y of LT -> x : (merge xt ys) EQ -> x : (merge xt yt) GT -> y : (merge xs yt) diff xs@(x:xt) ys@(y:yt) = case compare x y of LT -> x : (diff xt ys) EQ -> diff xt yt GT -> diff xs yt primes, nonprimes :: [Int] primes = [2,3,5] ++ (diff [7,9..] nonprimes) nonprimes = foldr1 f . map g $ tail primes where f (x:xt) ys = x : (merge xt ys) g p = [ n*p | n <- [p,p+2..]] -- The HaskellWiki repertory it under "primes" and it's at least 170 times faster than the extra-naive sieve you used in your comparison on my computer... (I have some doubts on the accuracy of the benchmark and System.Time at this level of precision, especially on Windows) An implementation with DiffArray (not even DiffUArray since there's no instance for Bool ? Is there a bitvector implementation somewhere to make up for this ?) and exactly your algorithm is already more than 20 times faster than the naive sieve. Note that this kind of benchmark is pretty pointless anyway since you're not really using C# in your program : you're using a subset of C# that's almost immediately translatable in the corresponding C code, and indeed the JIT compiler must compile to the same code as the equivalent C code, so it's no surprise at all that the performances are similar ! Due to the nature of Haskell, it's not so easy to do the same thing (write a C program in Haskell as you wrote a C program in C#), so the conclusion is obviously to Haskell disadvantage. -- Jedaï