User talk:GordonBGood
Hi GordonBGood and welcome to Rosetta code :-)
I wonder if you would consider putting your longer comments on efficiency in a new section of the tasks comments page? You could then refer to your argument succinctly from the task page as you add your code. The RC task pages are normally kept discussion-light, (and a few pages have more interesting discussion pages, such as algorithms and performance on Talk:Knight's tour for example). --Paddy3118 (talk) 05:42, 23 June 2014 (UTC)
- Sorry, I had only read a few discussions and was modelling my comments on others I saw on the pages to which I contributed. I won't go back and change my contributions except for the last, but I will do as you suggest for any new longer comments.--GordonBGood (talk) 13:22, 23 June 2014 (UTC)
Sieve of Eratosthenes - Haskell.
Hi, I've reverted back most of the previous stuff there. Much careful thought went into the gradual presentation; no function was missing. If you could discuss your future Haskell changes first on the talk page of that article, I'd appreciate it; please ping me on SO if I'm unresponsive here on Rosettacode. I'm going to add more explanation for the reasons for my edit on the article's talk page shortly. Thanks, -- WillNess (talk) 14:00, 10 April 2015 (UTC)
- please see the discussion in the talk page. -- WillNess (talk) 14:18, 10 April 2015 (UTC)
- what I meant was, if you're going to change the existing code, then please if possible discuss it first on the talk page; you should of course feel free to add any new code as you please. :) Thanks. -- WillNess (talk) 14:40, 10 April 2015 (UTC)
Priority queue implementation
In case you missed it, you can see exactly what PQ implementation was used in the article, in http://www.cs.hmc.edu/~oneill/code/haskell-primes.zip. Also, the code in the ZIP is optimized compared to the article, using "hybrid queue" for the second feed, IIRC. WillNess (talk) 10:43, 30 April 2015 (UTC)
- Thanks for the link, Will. I had found the implementation of the PriorityQ, including the HybridQ in one of your ideone entries, but not the original source for "PriorityQ.hs"; BTW, I had seen the minor slip-up in the implementation of PriorityQ (forgetting to reverse the order of the left and right branches in one place), which would only affect deletions as the original algorithm does not use and therefore would not affect its primes generation. My improved entry does not use HybridQ as it seems to be an alternate method of compensating for the over-eagerness of adding primes, nor do I use the SPECIALIZE'ations to compensate for the various numeric ranges required, as the method as you use in your second "Unbounded" entry seems so much cleaner. My entry uses some fusion to avoid list processing, but there are likely other optimizations that could be used; my point is not really that this is the fastest way to implement a Priority Queue version but to show that it is relatively clean and easy to avoid over-eager primes adding and excessive list processing.
Comment Signing on Talk pages
Please sign your comment on Y Comb. Thanks. --Paddy3118 (talk) 07:21, 31 July 2016 (UTC)
Space complexity improvement -- Hamming numbers
Hi, great stuff on the band size complexity reduction to n^(1/3)!! Very interesting!
I couldn't understand the exact specifics of it just by skimming through your code; so did my own thinking. Eventually I've arrived at the following; see if it's similar to what you have.
We are given n = log(M sqrt(30))^3 / (6log2log3log5) + O( log(M) ). (M is the magnitude of the nth Hamming number).
O((x+dx)^3) = O(x^3 + x^2 dx + x dx^2 + dx^3) so if we have dx ~= (1/x) we get O((x+1/x)^3) = O(x^3 + x + 1/x + 1/x^3) = O(x^3) + O(x), exactly what is needed. This means, we are to introduce the variance in logM which is ~ 1 / logM. Ta-da! The precision of this is uncanny; check the ideone entry (q3fma) at the bottom, for the data. I've edited the new stuff in.
BTW for up to 100 billionth on Ideone the savings due to the size reduction are negligible, about 20% speedup. What indeed gives the enormous 20x speedup is going with the Ints instead of the default Integers. This works if we're on 64-bits; otherwise Int is not sufficient. I tried using Word64, following your lead; but on the 32-bit Ideone it was as slow as plain old Integer. Thinking about it for a moment, I got back to Integer only where it is properly needed, and Ints everywhere else. It now runs about 2x slower than the all Ints version (in ranges were applicable), and has the advantage of not failing in upper ranges. :) Thanks for that, too. I'm always too reluctant to add type signatures! It got me this time too.
Thanks again! -- WillNess (talk) 18:52, 18 August 2016 (UTC)
Y combinator
Could you move the none Y combinator solution maybe to the talk page. The task is about Y comb. not other ways of performing Fib. You could direct people to the talk page for a more performant way of calculating Fibs if you think it necessary, but leave the main page to Y comb. versions for language comparison.