[Haskell-cafe] Re: Simple FAST lazy functional primes
Steve
stevech1097 at yahoo.com.au
Tue Nov 3 04:45:56 EST 2009
Hi Will,
I had previously tested the Melissa O'Neil prime function (using the
primes 0.1.1 package) and found it to be fast (for a functional
approach), but with high memory use.
To fully test a prime function, I think you should:
1. Test for more than the first 10^6 primes.
Generating all primes to 10^6 is quite easy for modern computers. Most
prime generating functions will run in less than 1 sec and look fast.
Try generating all primes to 10^7 and 10^8 then you will see how 'fast'
these lazy functional methods really are.
2. Measure memory use.
As you move above 10^6 and test primes up to 10^7, 10^8, and 10^9,
memory use becomes very important. A prime function with excessive
memory use will soon consume all of the system's memory.
Here's another primes function which performs quite well.
primes :: [Int]
primes = 2 : filter (isPrime primes) [3,5..] where
isPrime (p:ps) n
| mod n p == 0 = False
| p*p > n = True
| otherwise = isPrime ps n
isPrime [] _ = False -- never used, but avoids compiler warning
Here's some results from my PC, for generating primes to 10^8.
10**6 10**7 10**8
secs MiB secs MiB secs MiB
-------------------------------
1 0.01 0 0.1 2 2 14
2 0.56 7 11.1 43 270 306
3 0.61 7 11.8 44 260 342
4 0.43 36 5.4 345 900 not finished
1 using a Haskell ST Array
2 your primes function
3 my primes function, listed above
4 Melissa O'Neil method from primes 0.1.1 package
To summarise the results from the tests I've run:
- if you want fast functional primes, forget it, its not possible.
- if you just want fast primes, then use C, or a Haskell array.
- if performance does not matter and slow primes are acceptable, then
use the purely functional approach.
Regards,
Steve
More information about the Haskell-Cafe
mailing list