[Haskell-cafe] how to make haskell faster than python at finding primes?

[Janis Voigtlaender]

Vimal wrote:
>>Why not just:
>>
>>    primes         = sieve [2..]
>>
>>    sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]
>>
>>    main           = print (take 1000 primes)
>>
> 
> 
> I am unable to see how exactly this will run. Given that primes is an infinite
> list, and that when it reaches numbers say, as large as 10000, it will have to
> keep track of all the numbers (essentially prime numbers, which is the answer),
> whose mutliples it has to remove!
> 
> Say for eg: I give
> 
>>take 100 primes
> 
> 2 : [ 3...]
> then 2:3:[4 ... ]
> It will *now* have to remove 4,
> 2:3:[5...]
> Then 2:3:5:[6 ...]
> Now. It has to remove 6, based on the fact that it was a multiple of 2 ...
> (or 3? Which one comes first?)
> 
> This happens in a different order than what would be expected
> generally in a sieve :-)

To get a grip on the order in which things are sieved, try the following
little experiment (should also work for other sieves):

The original

   sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]

is equivalent (by desugaring the list comprehension) to

   sieve (p : xs) = p : sieve (filter (\x -> x `mod` p > 0) xs)

To see the non-primes as well, replace the filter with a map, where the
result type is an Either, with Left for primes and Right for non-primes.
To keep track of which modules have been tested for each given number,
let the element type of the Either-alternatives be a pair consisting of
the number and the list of checked modules. This gives:

sieve (Left l@(p,_) : xs) = Left l : sieve (map (either (\(x,e) -> (if x
`mod` p > 0 then Left else Right) (x,p:e)) Right) xs)
sieve (r : xs) = r : sieve xs

Now try:

> sieve [Left (i,[]) | i <-[2..]]
[Left (2,[]),Left (3,[2]),Right (4,[2]),Left (5,[3,2]),Right
(6,[2]),Left (7,[5,3,2]),Right (8,[2]),Right (9,[3,2]),Right
(10,[2]),Left (11,[7,5,3,2]),...

The Left-entries are primes, the Right-entries are non-primes, and the
second element of each pair shows against which modules the first pair
element has been checked (in reverse order).

Ciao, Janis.

-- 
Dr. Janis Voigtlaender
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:voigt at tcs.inf.tu-dresden.de