On 11/27/07, <b class="gmail_sendername">Andrew Coppin</b> &lt;<a href="mailto:andrewcoppin@btinternet.com">andrewcoppin@btinternet.com</a>&gt; wrote:<div><span class="gmail_quote"></span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hi guys.<br><br>Somebody just introduced me to a thing called &quot;Project Euler&quot;. I gather<br>it&#39;s well known around here...<br><br>Anyway, I was a little bit concerned about problem #7. The problem is<br>basically &quot;figure out what the 10,001st prime number is&quot;. Consider the
<br>following two programs for solving this:<br><br>First, somebody else wrote this in C:<br><br>int n = 2 , m , primesFound = 0;<br><br>for( n=0;n &lt; MAX_NUMBERS;n++ )<br>if( prime[n] )<br>{<br> primesFound++;<br><br> if( primesFound == 10001 )
<br>&nbsp;&nbsp; cout &lt;&lt; n &lt;&lt; &quot; is the 10001st prime.&quot; &lt;&lt; endl;<br><br> for(m=2*n;m&lt;MAX_NUMBERS;m+=n)<br>&nbsp;&nbsp; prime[m]=false;<br>}<br><br>Second, my implementation in Haskell:<br><br>primes :: [Integer]
<br>primes = seive [2..]<br>&nbsp;&nbsp;&nbsp;&nbsp;where<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;seive (p:xs) = p : seive (filter (\x -&gt; x `mod` p &gt; 0) xs)<br><br>main = print (primes !! 10000)<br><br>Well, we know who&#39;s winning the beauty contest. But here&#39;s the worrying
<br>thing:<br><br>&nbsp;&nbsp;C program: 0.016 seconds<br>&nbsp;&nbsp;Haskell program: 41 seconds<br><br>Eeeps! o_O That&#39;s Not Good(tm).<br><br>Replacing &quot;primes :: [Integer]&quot; with &quot;primes :: [Word32]&quot; speeds the<br>Haskell version up to 18 seconds, which is much faster but still a joke
<br>compared to C.<br><br>Running the Haskell code on a 2.2 GHz AMD Athlon64 X2 instead of a 1.5<br>GHz AMD Athlon drops the execution time down to 3 seconds. (So clearly<br>the box I was using in my lunch break at work is *seriously* slow...
<br>presumably the PC running the C code isn&#39;t.)<br><br>So, now I have a Haskell version that&#39;s &quot;only&quot; several hundred times<br>slower. Neither program is especially optimised, yet the C version is<br>drastically faster. This makes me sad. :-(
<br><br>By the way... I tried using Data.List.Stream instead. This made the<br>program about 40% slower. I also tried both -fasm and -fvia-c. The<br>difference was statistically insignificant. (Hey guys, nice work on the<br>
native codegen!) The difference in compilation speed was fairly drastic<br>though, needless to say. (The machine is kinda low on RAM, so trying to<br>call GCC makes it thrash like hell. So does linking, actually...)<br><br>
<br>Also, I&#39;m stuck with problem #10. (Find the sum of all primes less than<br>1 million.) I&#39;ve let the program run for well over 15 minutes, and still<br>no answer is forthcomming. It&#39;s implemented using the same primes
<br>function as above, with a simple filter and sum. (The type has to be<br>changed to [Word64] to avoid overflowing the result though.) The other<br>guy claims to have a C solution that takes 12 ms. There&#39;s a hell of a
<br>difference between 12 ms and over half an hour...(!) Clearly something<br>is horribly wrong here. Uh... help?<br><br>_______________________________________________<br>Haskell-Cafe mailing list<br><a href="mailto:Haskell-Cafe@haskell.org">
Haskell-Cafe@haskell.org</a><br><a href="http://www.haskell.org/mailman/listinfo/haskell-cafe">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br></blockquote></div><br>Hi Andrew,<br>
<br>
I don&#39;t remember who I stole this prime computation from, but it is
very fast (10001&#39;s prime in 0.06 sec with Int and 0.2 with Integer on
my machine) and not overly complex:<br>
<br>
primes :: [Integer]<br>
primes = 2 : filter (l1 . primeFactors) [3,5..]<br>
&nbsp;&nbsp;&nbsp; where<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; l1 (_:[]) = True<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; l1&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; _ = False<br>
<br>
primeFactors :: Integer -&gt; [Integer]<br>
primeFactors n = factor n primes<br>
&nbsp;&nbsp;&nbsp; where<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; factor _ [] = []<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; factor m (p:ps) | p*p &gt; m&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = [m]<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | m `mod` p == 0 = p : factor (m `div` p) (p:ps)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; | otherwise&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; = factor m ps<br>
<br>I used it a lot while playing with Euler Project. Many of the problems require prime calculation.<br><br>
Cheers,<br>
<br>
Olivier.<br><br><span class="gmail_quote"></span><br>