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

[Melissa O'Neill]

apfelmus wrote:
> I think that the `mod`-algorithm counts as sieve, it just does a  
> bad job at organizing the "crossing off".

I'd say that it might count as "a sieve", but *algorithmically* it is  
not "The Sieve of Eratosthenes".  If you abstract away the  
algorithmic details to a mathematical essence, you can argue they're  
the same, but I'd argue that the algorithmic details are what make  
people want to use the Sieve of Eratosthenes in the first place.

Algorithmically, when you say "remove all the multiples of 17" it  
really matters *how* you do it (c.f., an abstract mathematical  
perspective, where we might not care).  I'd argue that Eratosthenes  
did say how to do it, and doing it a different way is misleading  
enough that we should NOT call the resulting code "The Sieve of  
Eratosthenes".

Yitzchak Gale:
> We did not cross out any number more than once. But we did consider  
> each multiple of every prime, moving on if we found it already  
> crossed off. My algorithm does exactly the same.

Actually it doesn't.  Every composite gets handled by a stack of  
deleteOrd filters, each one trying to remove multiples of one prime.   
Whether you write
   sieve (x:xs) = x : sieve (deleteOrd [x+x,x+x+x..] xs)
or
   sieve (x:xs) = x : sieve (filter (\c ->  c `mod` x > 0) xs)
you're essentially doing the same amount of work.  Both ``deleteOrd [x 
+x,x+x+x..]'' and ``filter (\c ->  c `mod` x > 0)'' do exactly the  
same job -- your version goes faster because it avoids division, but  
that's all.

As I showed in my earlier post, with the worked example of removing  
all the multiples of 17,
   - 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
   - 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

The first way of crossing off multiples of 17 is inefficient -- it  
checks each composite against all the primes up to its smallest  
factor.  That is exactly what the classic naive primes algorithm  
does.  The second method is efficient -- it touches each composite  
once for each unique factor it has.

Of course, the first is easy to implement as a one-liner and the  
second isn't, but (sadly), that doesn't make the first way right and  
the second way wrong.

Yitzchak Gale also wrote:
> It is true that I have never read Eritosthenes in the original, but  
> my deleteOrd algorithm was meant to reproduce faithfully the sieve  
> algorithm as I was taught it in grade school.

I don't know which version you learned in grade school.  If you  
learned it as a mathematical abstraction (e.g., as a way to define  
what the primes are), you have faithfully reproduced that  
abstraction.  If you learned it as a technique for people to use to  
efficiently produce lists of primes, you have *not* reproduced it,  
because I'll bet in grade school you never checked 19 for  
divisibility by 17.

The bait and switch occurs when people remember only the mathematical  
abstraction and then look for elegant ways to recreate (only) that  
abstraction.  If you do that in a way that is fundamentally different  
at an algorithmic level, it shouldn't come as a surprise when that  
implementation doesn't run as efficiently as the original algorithm.   
You also shouldn't be surprised when someone complains that you  
haven't really implemented that original algorithm.

> A few days ago, I taught the sieve to my 6 year old daughter, the  
> same way I learned it. She loved it!

Unless you broke out the set notation with your six year old, you  
probably explained it operationally.  Thus you explained the  
algorithm, not a mathematical abstraction drawn from the algorithm.   
As such I'm sure you taught her the real thing.

And if you want to teach her cool Haskell one-liners, the "sieve"  
example that began this thread is delightfully brief.  But don't  
expect it to run quickly.  And you'd be doing her a disservice and  
propagating confusion if you tell her that it's algorithmically the  
same as the genuine Sieve of Eratosthenes.

     Melissa.