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 (Daniel Fischer)
----------------------------------------------------------------------
Message: 1
Date: Sun, 22 Jan 2012 23:57:52 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Performance of Prime Generator
To: [email protected], "Zhi-Qiang Lei" <[email protected]>
Cc: Ertugrul S?ylemez <[email protected]>
Message-ID: <[email protected]>
Content-Type: Text/Plain; charset="utf-8"
On Saturday 21 January 2012, 23:18:23, Ertugrul S?ylemez wrote:
> 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.
They shouldn't. But you have to use the right data structures.
For a prime sieve, you need unboxed mutable arrays if you want it to be
fast. You can use STUArrays from Data.Array.ST or mutable unboxed vectors
from Data.Vector.Mutable.Unboxed.
In principle you could also do the sieving in C and use the FFI, but afair
SPOJ only accepts single source files.
A decent sieve should sieve up to 10^9 in less than 30 seconds. A good
sieve less than 10.
But that's still too slow, there is a trick you have to use. To find the
primes in the range from m to n, you don't need to find all primes below m.
(No more hints to not completely spoil the problem.)
>
> Indeed, you're right. The method is too slow for numbers of that scale.
No, works fine with the right trick.
> I suggest trying the Sieve of Atkin, which performs quadratically faster
> than the Sieve of Eratosthenes.
No, the complexities differ by a factor of about log (log n) (details
depend on the implementations).
Without the hinted-at trick, an Atkin sieve would also need to be heavily
optimised to stand a chance of meeting the time limit. Don't forget that
the machines used by SPOJ are slow (and on top of that, SPOJ uses ghc-6.10,
which is far less good at optimising such computations than 6.12 and the
7.x series).
>
> I haven't tried it, but an equivalent C implementation can easily
> compute the first 10^9 prime numbers within seconds.
You mean the primes up to 10^9 here?
For the heavily optimised primegen by D. Bernstein, the first 10^9 primes
take 31.6 seconds here when customised to exploit the full L1 cache; 46
seconds with the vanilla block size. My segmented Eratosthenes sieve takes
83.5 seconds for that (but it overtakes primegen for somewhat higher
limits).
For the primes up to 10^9, the times are 0.675/1.378s for primegen, 3.29s
for Eratosthenes.
Based on my (limited) experience with the SPOJ machines, I'd estimate that
primegen would take about 10 seconds there to sieve up to 10^9.
Cheers,
Daniel
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 43, Issue 27
*****************************************
