[Haskell-cafe] Re: Simple FAST lazy functional primes

[Steve]

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