Given the linear dependencies in prime number generation, shy of using a probabilistic sieving method, I&#39;m not sure that it&#39;s possible to hope for any kind of parallel number generation. All you are going to do is for yourself to eat the cost of synchronisation for no gain.<br>
<div><br></div><div>Ben</div><br><div>On Fri May 16 2014 at 16:53:38, Norbert Melzer &lt;<a href="mailto:timmelzer@gmail.com">timmelzer@gmail.com</a>&gt; wrote:</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Hi there!<div><br></div><div>I am trying to enhence the speed of my Project Euler solutions…</div><div><br></div><div>My original function is this:</div><div><br></div><div>```haskell</div><div><div>problem10&#39; ::  Integer</div>

<div>problem10&#39; = sum $ takeWhile (&lt;=2000000) primes</div><div>  where</div><div>    primes                  = filter isPrime possiblePrimes</div><div>    isPrime n               = n == head (primeFactors n)</div>
<div>
    possiblePrimes          = (2:3:concat [ [6*pp-1, 6*pp+1] | pp &lt;- [1..] ])</div><div>    primeFactors m          = pf 2 m</div><div>    pf n m | n*n &gt; m        = [m]</div><div>           | n*n       == m  = [n,n]</div>

<div>           | m `mod` n == 0  = n:pf n (m `div` n)</div><div>           | otherwise      = pf (n+1) m</div></div><div>```</div><div><br></div><div>Even if the generation of primes is relatively slow and could be much better, I want to focus on parallelization, so I tried the following:<br>

</div><div><br></div><div>```haskell</div><div><div>parFilter :: (a -&gt; Bool) -&gt; [a] -&gt; [a]</div><div>parFilter _ [] = []</div><div>parFilter f (x:xs) =</div><div>  let px = f x</div><div>      pxs = parFilter f xs</div>

<div>  in par px $ par pxs $ case px of True -&gt; x : pxs</div><div>                                   False -&gt; pxs</div><div><br></div><div>problem10&#39; ::  Integer</div><div>problem10&#39; = sum $ takeWhile (&lt;=2000000) primes</div>

<div>  where</div><div>    primes                  = parFilter isPrime possiblePrimes</div><div>    isPrime n               = n == head (primeFactors n)</div><div>    possiblePrimes          = (2:3:concat [ [6*pp-1, 6*pp+1] | pp &lt;- [1..] ])</div>

<div>    primeFactors m          = pf 2 m</div><div>    pf n m | n*n &gt; m        = [m]</div><div>           | n*n       == m  = [n,n]</div><div>           | m `mod` n == 0  = n:pf n (m `div` n)</div><div>           | otherwise      = pf (n+1) m</div>

</div><div>```</div><div><br></div><div>This approach was about half as slow as the first solution (~15 seconds old, ~30 the new one!).</div><div><br></div><div>Trying to use `Control.Parallel.Strategies.evalList` for `possiblePrimes` resulted in a huge waste of memory, since it forced to generate an endless list, and does not stop…</div>

<div><br></div><div>Trying the same for `primeFactors` did not gain any speed, but was not much slower at least, but I did not expect much, since I look at its head only…</div><div><br></div><div>Only thing I could imagine to parallelize any further would be the takeWhile, but then I don&#39;t get how I should do it…</div>

<div><br></div><div>Any ideas how to do it?</div><div><br></div><div>TIA</div><div>Norbert</div><div><br></div></div>
______________________________<u></u>_________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/beginners" target="_blank">http://www.haskell.org/<u></u>mailman/listinfo/beginners</a><br>
</blockquote>