User talk:Elibarzilay: Difference between revisions
Content added Content deleted
No edit summary |
(→Sieve vs trial division.: Hard to determine.) |
||
| Line 24: | Line 24: | ||
::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. |
::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) |
--[[User:Elibarzilay|Elibarzilay]] ([[User talk:Elibarzilay|talk]]) 23:03, 24 July 2014 (UTC) |
||
::Hi again. [[Sieve_of_Eratosthenes#Odds-Only_.22infinite.22_generator_sieve_using_Streams_and_Co-Inductive_Streams|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). --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 23:48, 24 July 2014 (UTC) |
|||