Hi. May I ask what would that be? Isn't the purpose of the code is to be as clear as possible in terms of both logic and implementation? --cmpitg
cmpitg: What is this in reference to?
Sieve vs trial division.
Hi, I note that you just removed the incorrect flags on Sieve of Eratosthenes without changing the algorithm. If it isn't a true Sieve then the incorrect flag should be put back until the code is updated, or the code removed. The task specifies that a particular algorithm should be used in the finding of primes. Thanks. --Paddy3118 (talk) 14:08, 24 July 2014 (UTC)
Paddy3118: I changed it with an explicit mention of the algorithm, with a mention of the Scala alternative that does the exact same thing (without an incorrect flag) and I also added a reference to the same paper that is cited in the Scala section. (Sorry if there's some other way to communicate replies.) --Elibarzilay (talk) 14:38, 24 July 2014 (UTC)
- I took a look at the Scala. You need to put back the incorrect flags. The difference is that the Scalaputs a lot of effort into several proper sieves then adds an "oh by the way, here's a trial division", whereas Racket hides that information. When someone checked, they found trial division masquerading as Sieve and quite rightly flagged that. The Racket needs some work; many sieves followed by one *clearly labelled* trial division might satisfy the community, but really, it might be argued that all trial division algorithms should not be present. --Paddy3118 (talk) 15:02, 24 July 2014 (UTC)
- Yep. Trial division should be on Primality by trial division. --Paddy3118 (talk) 15:04, 24 July 2014 (UTC)
- Um, sorry, but this is going to be a long answer.
- After an even more thorough reading of the Scala entry, I don't see anything that makes the Scala entries any more special. There are three implementations of a regular sieve (two actually, since one is just a remake using tail recursion), and the Racket version has two. Then there are two implementations of the method in question (one with several variants, and one in the last section), and we have three in the Racket version -- but these three are really the same algorithm implemented with lazy lists, async channels, and generators (which is a perfect example for what the rosetta site is: a showcase of programming techniques, and this goes beyond that into comparing three methodologies applied to the same problem). Note that I'm ignoring "puts a lot of effort" since this is a subjective opinion and cannot be the basis of a proper decision.
- Secondly, the "oh by the way" that you refer to in the Scala section is exactly the same as in the Racket section, and in fact I edited the latter based on the former: there's a heading that mentions streams (in our case its laziness), then there's a paragraph that mentions the issue with a reference that I added, and then there is another entry that is stated to be an implementation of the same. My edit did the same, and it certainly does not hide that reference (and IMO, the debate on what *is* a "proper Sieve of Eratosthenes" is something that the refernce does *not* address (I'd expect that to come from from a history dept), so I think that the reference gets more weight than it should, yet I put it in to avoid complaints about fairness).
- (As a sidenote, I also find the claims in that paper questionable: it claims that finding the 19th prime number with this algorithm takes a significant amount of time, and I haven't seen any implementation of it that gets anywhere near that kind of disastrous runtime. But that's not too related, just my overall impression that the issue it talks about is blown out of proportions.)
- Third, this kind of algorithm has absolutely nothing to do with the problem stated in Primality by trial division, it is not a test of a single number, it is not testing divisibility with smaller numbers against a bigger one to determine primality, and its output is pretty much the same as any Sieve implementation -- only better since it's an infinite list, and it is most definitely a "Sieve". (If there was some way to describe the difference between the two sieves, a good solution would be to add a page for that kind Sieve, but I don't see how such a definition can be stated clearly for the crowd of RC hackers.) Yet another important point here is that this algorithm is extremely well-known as a "Sieve of Eratosthenes" in many functional programming courses using many languages -- yes, this is a dubious "argument by majority" but since Eratosthenes had been dead for plenty of time, so is the very definition of his Sieve.
- Finally, to talk about the algorithm itself, note that the problem statement explicitly forbids "pre-computed wheels". If you take a few minutes to read and understand it and how it works, you'll see that the algorithm in question is very much like an implementation that computes "self-optimizing" wheels. (Note: computes when it runs, *not* precomputes.) To see this, note that after the first round, the leftover infinite list is made of odd numbers (equivalent to a wheel of 2), then you have a list of 1mod6 and 5mod6 (eq. to a wheel of 3) etc. (The reference is correct that the runtime is different, but this is not really a proper comparison, since by its nature this method does more work for bigger primes, and since it's functional, but that's a side issue.) This could be grounds for an objection based on the stated restriction, but the thing that does *not* happen here is some kind of precomputation. In any case, this is just like the regular sieve implementations, only it's not possible to count and delete elements since the redundant elements are already deleted, and therefore a divisibility test is needed -- and yet it has nothing to do with the primality by division problem. A shallow reading of code and banging on all mentions of a modulo function is therefore not a proper thing to do in this case.
--Elibarzilay (talk) 23:03, 24 July 2014 (UTC)
- Hi again. Scala:Odds-Only "infinite" generator sieve using Streams and Co-Inductive Streams clearly states it is "Not a sieve of Eratosthenes.". If you are using that algorithm then maybe you should state the same?
- If your algorithm is not striking out multiples of the next largest available integer, (as the wikipedia entry mentions), then it is likely to be flagged. If your algorithm has a modulo in it then it may well be flagged as well because the trial division algorithm would use modulo.
- I suggest if your code is a Sieve you add a short, prominent, note of that. (You can add or copy your explanation here to a section in the pages discussion page as a reference as well). --Paddy3118 (talk) 23:48, 24 July 2014 (UTC)
- I can only say again that I added text very similar to the one in the Scala entry, with a reference to the same paper. I only qualified it with "some has claimed" since I'm personally not convinced by its point, and I believe that it is. But either way, it's most definitely a "sieve", due to its striking-out technique -- it just happens that only unstricken numbers are kept so a test is needed -- but it is definitely, absolutely, most positively, assuredly, reliably, and other "X-ly"s *not* a trial division algorithm, and it has nothing to do with that. (Like I said earlier, see the Racket code there, it's something completely different.)
- In any case, since it has been contested, I'm fine with keeping the added objection instead of trying to argue that it is and risk more fighting on a topic that is ultimately not too interesting. (In contrast, for example, to the programming techniques which are RC's main focus, and the thing that I enjoyed doing in those three entries.)
- --Elibarzilay (talk) 07:33, 12 August 2014 (UTC)
- Hello, I'd also like to participate in this discussion. I've added my reply on the page's talk page. Let's continue the discussion there, where it is more likely to be noticed. Thanks. -- 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 -  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. -- 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 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). -- 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. --Elibarzilay (talk) 18:25, 11 September 2014 (UTC)
- Sure it does, I just didn't want to obliterate the previous code in one big change, and you caught it in the middle of these sequence of changes... --Elibarzilay (talk) 18:36, 9 March 2015 (UTC)