On Wed, Sep 12, 2012 at 1:17 PM, Yi Cheng wrote:

Thanks for answering my question, but I'm still confused by some details. I don't quite agree with you that Eratosthenes algorithm must be implemented with a complexity of O(n^2) in space. When the n is used to calculate the primes below it, it can be implemented in space complexity O(n). For example, in languages, like C/C++, we can allocate a array. So I think the the complexity of O(n^2) in space you mentioned, is the complexity of "the beautiful code". So here's the question, can Eratosthenes algorithm be implemented in a more gentle way?

Correct: I referred to your implementation. See here ( http://www.haskell.org/haskellwiki/Prime_numbers#Sieve_of_Eratosthenes) for many different (and more efficient) implementations of Eratosthenes. Then I think maybe there is a more beautiful and practical way to implement

it. One method of mine is trying to judge whether a number is a prime just by the primes less than it, such as if the greatest common divisor of the number and the product of the primes less than it equals to 1. But the product of the primes is too large.

So I wander if there is a concise method to solve the problem with a faster method. In my C++ version, the Eratosthenes is implemented in linear space complexity, and optimize in filtering the numbers which can be divided by a prime. This code is faster than the original algorithm implemented by me(It was also implemented it in C++, and slower than the following code). I know, when writing Haskell code, it would be better to forget some experience in command-line language, but I want to know whether there is a faster method to solve the problem.

Thank you. Yi. Cheng

The code in my c++ version. #include <iostream> using namespace std; int main(){ int p[2000000] = {0}; long sum = 0; int f = 1; for(long i=2; i <= 2000000; ++i){ if(p[i] == 0){ sum += i; for(long j = i * i; j < 2000000; j += i) p[j] = 1; } } cout<

}

This implementation looks like the one here: http://www.haskell.org/haskellwiki/Prime_numbers#From_Squares, with the difference that in C++ you are modifying your array in-place instead of generating it lazily. It's not equivalent to your "beautiful" version in Haskell. hth, L.

On Wed, Sep 12, 2012 at 5:26 PM, Lorenzo Bolla wrote:

...

On Wed, Sep 12, 2012 at 9:06 AM, Yi Cheng wrote:

...

Recently, I'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. In my memory Eratosthenes is faster than just whether a number can be divided by the number less then the square root of it. Firstly, I wrote the following programs:

module Main where isPrime x = isPrime' 3 x (round . sqrt. fromIntegral $ x) isPrime' d target maxd | d > maxd = True | mod target d == 0 = False | otherwise = isPrime' (d + 2) target maxd

main = print $ (sum (filter isPrime [3,5..2000000]) + 2)

And it consume about 11s in my computer. 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've used it to solve the problem:

primes :: [Int] primes = primes' [2..]

primes' :: [Int] -> [Int] primes' [] = [] primes' (n:ns) = n : primes' (filter (\v -> v `mod` n /= 0) ns)

solve x = sum $ primes' [2..x]

main = print $ solve 2000000

Well, although the code is beautiful, it is slow. Even waiting for a minute, no answer was printed.

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).

So I want to know, why Eratosthenes implemented in Haskell is slow than the ugly code implemented by me. Could anyone tell me?

Eratosthenes's complexity is O(n^2) (both space and time), whereas the "ugly" one has a sub-quadratic running complexity and linear in space.

Try to profile them: $> ghc -O2 --make -prof -auto-all <filename> $> ./primes +RTS -p -hc $> hp2ps primes.hp

You'll see that most of the time is spent allocating space which is never released. You could play a bit with strictness, but the main problem is the awful complexity of the algorithm.

hth, L.

...

Thank you Yi Cheng

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

You might also be interested in this paper: www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf . I thought it was a good analysis/ On Wed, Sep 12, 2012 at 8:53 AM, Yi Cheng wrote:

Thank you, very much. It's exactly the thing I want to know.

Yi. Cheng

On Wed, Sep 12, 2012 at 8:41 PM, Lorenzo Bolla wrote:

...

On Wed, Sep 12, 2012 at 1:17 PM, Yi Cheng wrote:

...

Thanks for answering my question, but I'm still confused by some details. I don't quite agree with you that Eratosthenes algorithm must be implemented with a complexity of O(n^2) in space. When the n is used to calculate the primes below it, it can be implemented in space complexity O(n). For example, in languages, like C/C++, we can allocate a array. So I think the the complexity of O(n^2) in space you mentioned, is the complexity of "the beautiful code". So here's the question, can Eratosthenes algorithm be implemented in a more gentle way?

Correct: I referred to your implementation. See here (http://www.haskell.org/haskellwiki/Prime_numbers#Sieve_of_Eratosthenes) for many different (and more efficient) implementations of Eratosthenes.

...

Then I think maybe there is a more beautiful and practical way to implement it. One method of mine is trying to judge whether a number is a prime just by the primes less than it, such as if the greatest common divisor of the number and the product of the primes less than it equals to 1. But the product of the primes is too large.

So I wander if there is a concise method to solve the problem with a faster method. In my C++ version, the Eratosthenes is implemented in linear space complexity, and optimize in filtering the numbers which can be divided by a prime. This code is faster than the original algorithm implemented by me(It was also implemented it in C++, and slower than the following code). I know, when writing Haskell code, it would be better to forget some experience in command-line language, but I want to know whether there is a faster method to solve the problem.

Thank you. Yi. Cheng

The code in my c++ version. #include <iostream> using namespace std; int main(){ int p[2000000] = {0}; long sum = 0; int f = 1; for(long i=2; i <= 2000000; ++i){ if(p[i] == 0){ sum += i; for(long j = i * i; j < 2000000; j += i) p[j] = 1; } } cout<

}

This implementation looks like the one here: http://www.haskell.org/haskellwiki/Prime_numbers#From_Squares, with the difference that in C++ you are modifying your array in-place instead of generating it lazily. It's not equivalent to your "beautiful" version in Haskell.

hth, L.

...

On Wed, Sep 12, 2012 at 5:26 PM, Lorenzo Bolla wrote:

...

On Wed, Sep 12, 2012 at 9:06 AM, Yi Cheng wrote:

...

Recently, I'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. In my memory Eratosthenes is faster than just whether a number can be divided by the number less then the square root of it. Firstly, I wrote the following programs:

module Main where isPrime x = isPrime' 3 x (round . sqrt. fromIntegral $ x) isPrime' d target maxd | d > maxd = True | mod target d == 0 = False | otherwise = isPrime' (d + 2) target maxd

main = print $ (sum (filter isPrime [3,5..2000000]) + 2)

And it consume about 11s in my computer. 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've used it to solve the problem:

primes :: [Int] primes = primes' [2..]

primes' :: [Int] -> [Int] primes' [] = [] primes' (n:ns) = n : primes' (filter (\v -> v `mod` n /= 0) ns)

solve x = sum $ primes' [2..x]

main = print $ solve 2000000

Well, although the code is beautiful, it is slow. Even waiting for a minute, no answer was printed.

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).

So I want to know, why Eratosthenes implemented in Haskell is slow than the ugly code implemented by me. Could anyone tell me?

Eratosthenes's complexity is O(n^2) (both space and time), whereas the "ugly" one has a sub-quadratic running complexity and linear in space.

Try to profile them: $> ghc -O2 --make -prof -auto-all <filename> $> ./primes +RTS -p -hc $> hp2ps primes.hp

You'll see that most of the time is spent allocating space which is never released. You could play a bit with strictness, but the main problem is the awful complexity of the algorithm.

hth, L.

...

Thank you Yi Cheng

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners

_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners