[Haskell-cafe] how to make haskell faster than python at finding
primes?
Janis Voigtlaender
voigt at tcs.inf.tu-dresden.de
Mon Aug 6 06:17:22 EDT 2007
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
More information about the Haskell-Cafe
mailing list