User talk:Elibarzilay: Difference between revisions
→Sieve vs trial division.
(→Sieve vs trial division.: correct the indentation) |
|||
Line 36:
: 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)
: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)
| |||