[Haskell-cafe] Re: Genuine Eratosthenes sieve [Was: Optimization fun]

[Yitzchak Gale]

Hi Melissa,

You wrote:
>    - Eratosthenes's sieve never says the equivalent of, "Hmm, I
> wonder if 19 is a multiple of 17" -- but both the basic "sieve" we
> began with and the deleteOrd version do

So then maybe I taught my daughter the wrong thing.
When she does 17, she moves ahead one number at
a time. When she gets to a multiple of 17, she crosses
it off. So yes, she does consider whether 19 is a multiple
of 17.

I tried to get her to use my way of deciding what is the
next multiple. Then she could do something a little
more like what you are saying by using the layout of
the sieve to jump ahead more quickly to the next
multiple. But she insists on using apfelmus' way.

>    - Eratosthenes's sieve crosses-off/looks-at 459 (i.e., 17 * 27),
> even though we crossed it off already when we crossed off multiples
> of 3 -- whether you call that crossing it off a second time, or
> merely stepping over it, it still needs to alight on 459 to get to
> 493 (17 * 29), which hasn't been crossed off yet

True, the deleteOrd algorithm has that extra optimization.
So I guess my sieve is actually:

crossOff :: Ord a => [a] -> [Either a a] -> [Either a a]
crossOff xs@(x:xs') ys@(y:ys')
 | x < y'    = crossOff xs' ys
 | x > y'    = y : crossOff xs  ys'
 | otherwise = Left y' : crossOff xs' ys'
 where y' = fromEither y
crossOff _ y = y

sieve (Right x:xs) = Right x : sieve (crossOff [x+x,x+x+x..] xs)
sieve (Left  x:xs) = Left  x : sieve xs

primes = catRights $ sieve $ map Right [2..]

fromEither = either id id

catRights :: [Either a b] -> [b]
catRights (Right x:xs) = x : catRights xs
catRights (      _:xs) =     catRights xs
catRights _            = []

That is the Sieve of Yitzchak. My daughter is
using the Sieve of Apfelmus. I guess you can
still claim that neither is the Sieve of Eratosthenes.

Regards,
Yitz