[Haskell-beginners] Question about time consume when calculate prime numbers

[Yi Cheng]

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 <lbolla at gmail.com> wrote:

>
>
> On Wed, Sep 12, 2012 at 1:17 PM, Yi Cheng <chengyidna at gmail.com> 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<<sum<<endl;
>>     return 0;
>>
>> }
>>
>>
> 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 <lbolla at gmail.com> wrote:
>>
>>>
>>>
>>> On Wed, Sep 12, 2012 at 9:06 AM, Yi Cheng <chengyidna at gmail.com> 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 at haskell.org
>>>> http://www.haskell.org/mailman/listinfo/beginners
>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120912/868e18c1/attachment-0001.htm>