Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. parallelizing a function for generating prime numbers
(Norbert Melzer)
2. parallelizing a function for generating prime numbers
(Benjamin Edwards)
3. Re: parallelizing a function for generating prime numbers
(Norbert Melzer)
----------------------------------------------------------------------
Message: 1
Date: Fri, 16 May 2014 17:53:31 +0200
From: Norbert Melzer <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] parallelizing a function for generating
prime numbers
Message-ID:
<ca+bcvstrtqotrso3esaw3mm13z8dqqpofw6pqzqagyillye...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi there!
I am trying to enhence the speed of my Project Euler solutions?
My original function is this:
```haskell
problem10' :: Integer
problem10' = sum $ takeWhile (<=2000000) primes
where
primes = filter isPrime possiblePrimes
isPrime n = n == head (primeFactors n)
possiblePrimes = (2:3:concat [ [6*pp-1, 6*pp+1] | pp <- [1..]
])
primeFactors m = pf 2 m
pf n m | n*n > m = [m]
| n*n == m = [n,n]
| m `mod` n == 0 = n:pf n (m `div` n)
| otherwise = pf (n+1) m
```
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:
```haskell
parFilter :: (a -> Bool) -> [a] -> [a]
parFilter _ [] = []
parFilter f (x:xs) =
let px = f x
pxs = parFilter f xs
in par px $ par pxs $ case px of True -> x : pxs
False -> pxs
problem10' :: Integer
problem10' = sum $ takeWhile (<=2000000) primes
where
primes = parFilter isPrime possiblePrimes
isPrime n = n == head (primeFactors n)
possiblePrimes = (2:3:concat [ [6*pp-1, 6*pp+1] | pp <- [1..]
])
primeFactors m = pf 2 m
pf n m | n*n > m = [m]
| n*n == m = [n,n]
| m `mod` n == 0 = n:pf n (m `div` n)
| otherwise = pf (n+1) m
```
This approach was about half as slow as the first solution (~15 seconds
old, ~30 the new one!).
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?
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?
Only thing I could imagine to parallelize any further would be the
takeWhile, but then I don't get how I should do it?
Any ideas how to do it?
TIA
Norbert
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140516/13cfe18e/attachment-0001.html>
------------------------------
Message: 2
Date: Fri, 16 May 2014 16:33:14 +0000
From: Benjamin Edwards <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] parallelizing a function for generating
prime numbers
Message-ID:
<can6k4niyqnq+p8vgd_6cf+ojzfbs+9azrphr2znsv5emsqa...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Given the linear dependencies in prime number generation, shy of using a
probabilistic sieving method, I'm not sure that it'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.
Ben
On Fri May 16 2014 at 16:53:38, Norbert Melzer <[email protected]> wrote:
> Hi there!
>
> I am trying to enhence the speed of my Project Euler solutions?
>
> My original function is this:
>
> ```haskell
> problem10' :: Integer
> problem10' = sum $ takeWhile (<=2000000) primes
> where
> primes = filter isPrime possiblePrimes
> isPrime n = n == head (primeFactors n)
> possiblePrimes = (2:3:concat [ [6*pp-1, 6*pp+1] | pp <- [1..]
> ])
> primeFactors m = pf 2 m
> pf n m | n*n > m = [m]
> | n*n == m = [n,n]
> | m `mod` n == 0 = n:pf n (m `div` n)
> | otherwise = pf (n+1) m
> ```
>
> 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:
>
> ```haskell
> parFilter :: (a -> Bool) -> [a] -> [a]
> parFilter _ [] = []
> parFilter f (x:xs) =
> let px = f x
> pxs = parFilter f xs
> in par px $ par pxs $ case px of True -> x : pxs
> False -> pxs
>
> problem10' :: Integer
> problem10' = sum $ takeWhile (<=2000000) primes
> where
> primes = parFilter isPrime possiblePrimes
> isPrime n = n == head (primeFactors n)
> possiblePrimes = (2:3:concat [ [6*pp-1, 6*pp+1] | pp <- [1..]
> ])
> primeFactors m = pf 2 m
> pf n m | n*n > m = [m]
> | n*n == m = [n,n]
> | m `mod` n == 0 = n:pf n (m `div` n)
> | otherwise = pf (n+1) m
> ```
>
> This approach was about half as slow as the first solution (~15 seconds
> old, ~30 the new one!).
>
> 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?
>
> 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?
>
> Only thing I could imagine to parallelize any further would be the
> takeWhile, but then I don't get how I should do it?
>
> Any ideas how to do it?
>
> TIA
> Norbert
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140516/6fefe7e8/attachment-0001.html>
------------------------------
Message: 3
Date: Fri, 16 May 2014 22:13:09 +0200
From: Norbert Melzer <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] parallelizing a function for
generating prime numbers
Message-ID:
<ca+bcvstluy8agnvzt1uzc_ygdzxtad0ihgknwq+zrahcu4c...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
I had some fears, that there will be answers like this ;)
The problem with improving the generation itself is, that I don't
understand the faster implementations that I found (namely the
implementation of `Data.Numbers.Primes` in the `primes`-package and some
other Wheel-Sieves).
And for the Project-Euler-Problems I only use code that I have created
myself or at least I have a small idea how it works if it is from a package?
2014-05-16 18:33 GMT+02:00 Benjamin Edwards <[email protected]>:
> Given the linear dependencies in prime number generation, shy of using a
> probabilistic sieving method, I'm not sure that it'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.
>
> Ben
>
> On Fri May 16 2014 at 16:53:38, Norbert Melzer <[email protected]>
> wrote:
>
>> Hi there!
>>
>> I am trying to enhence the speed of my Project Euler solutions?
>>
>> My original function is this:
>>
>> ```haskell
>> problem10' :: Integer
>> problem10' = sum $ takeWhile (<=2000000) primes
>> where
>> primes = filter isPrime possiblePrimes
>> isPrime n = n == head (primeFactors n)
>> possiblePrimes = (2:3:concat [ [6*pp-1, 6*pp+1] | pp <-
>> [1..] ])
>> primeFactors m = pf 2 m
>> pf n m | n*n > m = [m]
>> | n*n == m = [n,n]
>> | m `mod` n == 0 = n:pf n (m `div` n)
>> | otherwise = pf (n+1) m
>> ```
>>
>> 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:
>>
>> ```haskell
>> parFilter :: (a -> Bool) -> [a] -> [a]
>> parFilter _ [] = []
>> parFilter f (x:xs) =
>> let px = f x
>> pxs = parFilter f xs
>> in par px $ par pxs $ case px of True -> x : pxs
>> False -> pxs
>>
>> problem10' :: Integer
>> problem10' = sum $ takeWhile (<=2000000) primes
>> where
>> primes = parFilter isPrime possiblePrimes
>> isPrime n = n == head (primeFactors n)
>> possiblePrimes = (2:3:concat [ [6*pp-1, 6*pp+1] | pp <-
>> [1..] ])
>> primeFactors m = pf 2 m
>> pf n m | n*n > m = [m]
>> | n*n == m = [n,n]
>> | m `mod` n == 0 = n:pf n (m `div` n)
>> | otherwise = pf (n+1) m
>> ```
>>
>> This approach was about half as slow as the first solution (~15 seconds
>> old, ~30 the new one!).
>>
>> 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?
>>
>> 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?
>>
>> Only thing I could imagine to parallelize any further would be the
>> takeWhile, but then I don't get how I should do it?
>>
>> Any ideas how to do it?
>>
>> TIA
>> Norbert
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140516/a8be9f8b/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 71, Issue 19
*****************************************
