Anonymous user
User talk:Elibarzilay: Difference between revisions
no edit summary
No edit summary |
|||
Line 16:
:Yep. Trial division should be on [[Primality by trial division]]. --[[User:Paddy3118|Paddy3118]] ([[User talk: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.
--[[User:Elibarzilay|Elibarzilay]] ([[User talk:Elibarzilay|talk]]) 23:03, 24 July 2014 (UTC)
| |||