Anonymous user
User talk:Elibarzilay: Difference between revisions
→Fibonacci_n-step_number_sequences#Racket: Thanks.
No edit summary |
(→Fibonacci_n-step_number_sequences#Racket: Thanks.) |
||
| (10 intermediate revisions by 3 users not shown) | |||
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.
--[[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)
:::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.)
::: --[[User:Elibarzilay|Elibarzilay]] ([[User talk:Elibarzilay|talk]]) 07:33, 12 August 2014 (UTC)
: 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)
:::Absolutely, this is exactly what this site is for. Thanks. -- [[User:WillNess|WillNess]] ([[User talk:WillNess|talk]]) 06:56, 12 September 2014 (UTC)
==[[Fibonacci_n-step_number_sequences#Racket]]==
A polite reminder that the Lucas series is still not attempted in Racket. Thanks. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 18:09, 9 March 2015 (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... --[[User:Elibarzilay|Elibarzilay]] ([[User talk:Elibarzilay|talk]]) 18:36, 9 March 2015 (UTC)
::Thanks again. (And sorry for my impatience). --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 23:05, 9 March 2015 (UTC)
| |||