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.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
