Anonymous user
User talk:Elibarzilay: Difference between revisions
→Sieve vs trial division.
Line 34:
: Hello, I'd also like to participate in this discussion. I've added my reply on [[Talk:Sieve of Eratosthenes#Trial division sieves should be moved from here|the page's talk page]]. Let's continue the discussion there, where it is more likely to be noticed. Thanks. -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 20:00, 10 September 2014 (UTC)
:: (Answered there.)
: BTW, about your remark that Turner's sieve calculates the wheels as it operates. I don't think it's right, because a wheel is finite - its when we ''roll'' a wheel that we get the infinite stream, equally calculated by the Turner sieve at each step. But the wheel itself is finite - [3] for 2; [5,7] for 2*3; [7,11,13,17,19,23, 29,31 ] for 2*3*5, etc. And the point to it is that we ''roll'' it by repeated additions, without any need for repeated test divisions. That's where the savings come from, it wouldn't be an optimization otherwise. -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 21:42, 10 September 2014 (UTC)
:: What I meant is that it's similar to using a wheel -- and yes, it would be an infinite wheel, of course.
:Hi again, I've read the Scala entry now to which you refer, and I think you've misread it. It has only '''''one''''' very short entry with a trial division sieve, (under [[Sieve_of_Eratosthenes#Odds-Only "infinite" generator sieve using Streams and Co-Inductive Streams|Odds-Only "infinite" generator sieve using Streams and Co-Inductive Streams]]), serving as a backdrop for the discussion that follows. All the others are '''''not''''' based on trial division and are in fact variations of the proper sieve of Eratosthenes - because they ''generate'' their multiples from primes, not ''test'' their input to find the multiples (the modulo op that you see in the "segmented" version is just to calculate the starting offset on the array). --- The Racket entry though has full ''three'' variations of trial division sieve, standing on their own, with no follow-up discussion or examples of the proper SoE using them for comparison (like the Scala entry has). -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 11:40, 11 September 2014 (UTC)
:: The three racket entries are basically one (the first) with two translations of the exact same thing to use channels & threads and to use generators. This is a website for showing different techniques for approaching a single problem, and therefore IMO this kind of thing is a perfect example of what should be encouraged. --[[User:Elibarzilay|Elibarzilay]] ([[User talk:Elibarzilay|talk]]) 18:25, 11 September 2014 (UTC)
| |||