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. Re: Performance of Prime Generator (Zhi-Qiang Lei)
2. Re: Performance of Prime Generator (Ertugrul S?ylemez)
3. Re: Performance of Prime Generator (Zhi-Qiang Lei)
4. Re: Performance of Prime Generator (Zhi-Qiang Lei)
5. Re: Performance of Prime Generator (Ertugrul S?ylemez)
----------------------------------------------------------------------
Message: 1
Date: Sat, 21 Jan 2012 19:08:16 +0800
From: Zhi-Qiang Lei <[email protected]>
Subject: Re: [Haskell-beginners] Performance of Prime Generator
To: Haskell Beginer <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset=iso-8859-1
Hi, what do you mean "more naive wheel trial division"?
On Jan 21, 2012, at 5:44 PM, Ertugrul S?ylemez wrote:
> Zhi-Qiang Lei <[email protected]> wrote:
>
>> I have bungled the Prime Generator on SPOJ for many times. Although
>> the program is faster and faster on my machine, but it keeps "time
>> limited exceeded" on SPOJ (6 seconds limit). Now my approach is for
>> every number in the range, check if it is prime by checking if can be
>> divided by all the primes smaller than or equal its square root. For
>> the numbers between 999900000 and 1000000000, it take 0.64 seconds on
>> my laptop. Could anyone give me some hints to enhance it? Thanks.
>
> Although intuitively that sounds like a great idea, in practice it's
> not. To quickly generate a large number of small primes you should
> either use a sieve or use the more naive wheel trial division. This is
> for small numbers up to perhaps 2^18 or 2^20, where this method is
> feasible and usually fastest.
>
>
> Greets,
> Ertugrul
>
> --
> nightmare = unsafePerformIO (getWrongWife >>= sex)
> http://ertes.de/
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
------------------------------
Message: 2
Date: Sat, 21 Jan 2012 15:38:31 +0100
From: Ertugrul S?ylemez <[email protected]>
Subject: Re: [Haskell-beginners] Performance of Prime Generator
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
Zhi-Qiang Lei <[email protected]> wrote:
> Hi, what do you mean "more naive wheel trial division"?
Just use a wheel like 2*3*5 and don't bother only dividing by primes.
Trying to divide only by primes takes more time than just living with
the few percent nonprimes that slip through the wheel.
Or better yet, use a sieve like the Sieve of Eratosthenes or the Sieve
of Atkin. Those are fairly easy to implement in Haskell.
Greets,
Ertugrul
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120121/c247404c/attachment-0001.pgp>
------------------------------
Message: 3
Date: Sat, 21 Jan 2012 23:23:42 +0800
From: Zhi-Qiang Lei <[email protected]>
Subject: Re: [Haskell-beginners] Performance of Prime Generator
To: Haskell Beginer <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset=windows-1252
Thanks, I'll look into it.
On Jan 21, 2012, at 4:50 PM, Yucheng Zhang wrote:
> On Sat, Jan 21, 2012 at 4:27 PM, Zhi-Qiang Lei <[email protected]> wrote:
>> Could anyone give me some hints to enhance it? Thanks.
>
> You could use a faster primality test algorithm such as Miller-Rabin [1].
>
> [1] http://en.wikipedia.org/wiki/Miller?Rabin_primality_test
Best regards,
Zhi-Qiang Lei
[email protected]
------------------------------
Message: 4
Date: Sun, 22 Jan 2012 00:28:34 +0800
From: Zhi-Qiang Lei <[email protected]>
Subject: Re: [Haskell-beginners] Performance of Prime Generator
To: Haskell Beginer <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset=iso-8859-1
Well, thanks, so far I have tried wheel only and Sieve of Eratosthenes only
approaches. They both failed. When the numbers is between 999900000 and
1000000000, they can take more than a hour on my laptop.
On Jan 21, 2012, at 10:38 PM, Ertugrul S?ylemez wrote:
> Zhi-Qiang Lei <[email protected]> wrote:
>
>> Hi, what do you mean "more naive wheel trial division"?
>
> Just use a wheel like 2*3*5 and don't bother only dividing by primes.
> Trying to divide only by primes takes more time than just living with
> the few percent nonprimes that slip through the wheel.
>
> Or better yet, use a sieve like the Sieve of Eratosthenes or the Sieve
> of Atkin. Those are fairly easy to implement in Haskell.
>
>
> Greets,
> Ertugrul
>
> --
> nightmare = unsafePerformIO (getWrongWife >>= sex)
> http://ertes.de/
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
Best regards,
Zhi-Qiang Lei
[email protected]
------------------------------
Message: 5
Date: Sat, 21 Jan 2012 23:18:23 +0100
From: Ertugrul S?ylemez <[email protected]>
Subject: Re: [Haskell-beginners] Performance of Prime Generator
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
Zhi-Qiang Lei <[email protected]> wrote:
> Well, thanks, so far I have tried wheel only and Sieve of Eratosthenes
> only approaches. They both failed. When the numbers is between
> 999900000 and 1000000000, they can take more than a hour on my laptop.
Indeed, you're right. The method is too slow for numbers of that scale.
I suggest trying the Sieve of Atkin, which performs quadratically faster
than the Sieve of Eratosthenes.
I haven't tried it, but an equivalent C implementation can easily
compute the first 10^9 prime numbers within seconds.
Greets,
Ertugrul
--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120121/2497bdd5/attachment-0001.pgp>
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 43, Issue 26
*****************************************
