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

[apfelmus at quantentunnel.de]

Yitzchak Gale wrote:

> Melissa O'Neill 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.

Yes, thanks Yitzchak, that's exactly the point. In order to cross off a
number, one has to find it and then to cross it. The trouble comes from
the fact that both notions are somewhat interchangeable. In a sense,
'deleteOrd' searches all subsequent numbers to find the next one to
cross off. At the same time, it considers all subsequent numbers whether
they should be crossed off or not. Melissa's priority queue walks all
numbers and decides in O(log n) whether the scrutinee is the next number
to be crossed. It's the 'find' part that is algorithmically expensive.

The point about "Eratosthenes's sieve" is that it does not specify
algorithmically how to find the next number to be crossed. It does not
even define how to store (crossed) numbers, it stores them "on paper".
Of course, the computer needs to know both and there is freedom of
interpretation how to implement it. But I'm glad that Melissa pointed
out that this implementation has to be chosen consciously.

So, I argue that Yitzchak's 'deleteOrd' is a genuine "sieve of
Eratosthenes". The naive 'filter (\x -> x `mod` p /= 0)' is it as well.
But I agree that the latter deserves more a name like "transposed sieve
of Eratosthenes".

Regards,
apfelmus