<br><br><div class="gmail_quote">On Wed, Sep 12, 2012 at 9:06 AM, Yi Cheng <span dir="ltr">&lt;<a href="mailto:chengyidna@gmail.com" target="_blank">chengyidna@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Recently, I&#39;m trying to solve some problems in project euler using haskell. When it came to problem 10, calculating the sum of all primes below 20000000, I try to write a program which can generate primes.<br>In my memory Eratosthenes is faster than just whether a number can be divided by the number less then the square root of it.<br>

Firstly, I wrote the following programs:<br><br>module Main where<br>isPrime x = isPrime&#39; 3 x (round . sqrt. fromIntegral $ x)<br>isPrime&#39; d target maxd<br>  | d &gt; maxd = True<br>  | mod target d == 0 = False<br>

  | otherwise = isPrime&#39; (d + 2) target maxd<br><br>main = print $ (sum (filter isPrime [3,5..2000000]) + 2)<br><br>And it consume about 11s in my computer.<br>Then, I tried to figure out how to solve the problem by Eratosthenes, but failed. Later, I find a program implemented by others, meeting my purpose and I&#39;ve used it to solve the problem:<br>

<br>primes :: [Int]<br>primes = primes&#39; [2..]<br><br>primes&#39; :: [Int] -&gt; [Int]<br>primes&#39; [] = []<br>primes&#39; (n:ns) = n : primes&#39; (filter (\v -&gt; v `mod` n /= 0) ns)<br><br>solve x = sum $ primes&#39; [2..x]<br>

<br>main = print $ solve 2000000<br><br>Well, although the code is beautiful, it is slow. Even waiting for a minute, no answer was printed.<br><br>In C version, Eratosthenes is faster than the method implemented in my earlier code, which only consume 0.3s(the earlier method consume 1.6s).<br>

<br>So I want to know, why Eratosthenes implemented in Haskell is slow than the ugly code implemented by me.<br>Could anyone tell me?<br><br></blockquote><div><br></div><div>Eratosthenes&#39;s complexity is O(n^2) (both space and time), whereas the &quot;ugly&quot; one has a sub-quadratic running complexity and linear in space.</div>
<div><br></div><div>Try to profile them:</div><div>$&gt; ghc -O2 --make -prof -auto-all &lt;filename&gt;</div><div>$&gt; ./primes +RTS -p -hc</div><div>$&gt; hp2ps primes.hp</div><div> </div><div>You&#39;ll see that most of the time is spent allocating space which is never released.</div>
<div>You could play a bit with strictness, but the main problem is the awful complexity of the algorithm.</div><div><br></div><div>hth,</div><div>L.</div><div><br></div><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>Thank you<span class="HOEnZb"><font color="#888888"><br>Yi Cheng<br>
</font></span><br>_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/mailman/listinfo/beginners</a><br>
<br></blockquote></div><br>