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