<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' :: Integer</div>
<div>problem10' = sum $ takeWhile (<=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 <- [1..] ])</div><div> primeFactors m = pf 2 m</div><div> pf n m | n*n > 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 -> Bool) -> [a] -> [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 -> x : pxs</div><div> False -> pxs</div><div><br></div><div>problem10' :: Integer</div><div>problem10' = sum $ takeWhile (<=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 <- [1..] ])</div>
<div> primeFactors m = pf 2 m</div><div> pf n m | n*n > 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'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>