Anonymous user
User talk:GordonBGood: Difference between revisions
→Y combinator
(Comment signing?) |
|||
| (One intermediate revision by one other user not shown) | |||
Line 25:
==Comment Signing on Talk pages==
Please sign your comment on Y Comb. Thanks. --[[User:Paddy3118|Paddy3118]] ([[User talk: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 ''n''th 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! -- [[User:WillNess|WillNess]] ([[User talk: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.
Thanks. [[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 13:27, 11 October 2018 (UTC)
| |||