tag:blogger.com,1999:blog-1777990983847811806.post8948542367026898409..comments2020-05-22T09:08:49.932-07:00Comments on Haskell for all: Blazing fast Fibonacci numbers using MonoidsGabriel Gonzalezhttp://www.blogger.com/profile/01917800488530923694noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-1777990983847811806.post-62195169974290106012020-04-25T18:59:34.002-07:002020-04-25T18:59:34.002-07:00I used GHCi to try the memoized fib there vs. the ...I used GHCi to try the memoized fib there vs. the strict & smaller version given by Kanashima below (albeit with a Semigroup instance and `stimes` instead of Num and `(^)`), and the memoized fib takes too long even on 10^5, while the multiplication-by-squaring one handles even 10^6 just fine, and starts taking too long on 10^8 (seven seconds). I'm not sure why you call that "performs just as well". What am I missing here?Anonymoushttps://www.blogger.com/profile/10589431808421112834noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-80800914400419971522020-04-24T16:08:05.175-07:002020-04-24T16:08:05.175-07:00-- Or you can do this
Phi = Phi !Integer !Integer...-- Or you can do this<br /><br />Phi = Phi !Integer !Integer<br /> deriving (Eq, Show)<br /><br />instance Num Phi where<br /> (Phi a b) * (Phi c d)<br /> = Phi (a*c+b*d) (a*d+b*c+b*d)<br /> <br />fib n = x where<br /> Phi _ x = Phi 0 1 ^ n<br /><br />main = print $ fib 10000000Kanashimiahttps://www.blogger.com/profile/01213175212235443350noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-46166396159656552022020-04-23T13:39:45.135-07:002020-04-23T13:39:45.135-07:00I ran this code vs the memoized version of fib whi...I ran this code vs the memoized version of fib which can be seen at https://wiki.haskell.org/Memoization. It turns out the latter generates nearly 1/3 as much assembly. It also performs just as well. Do check it outwbrighthttps://www.blogger.com/profile/13006932359739432427noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-59665645369870698472020-04-23T13:30:33.665-07:002020-04-23T13:30:33.665-07:00Interesting mathematical note: the Binet formula c...Interesting mathematical note: the Binet formula can be done in the ring of numbers m+nφ with m and n integers; with the same repeated squaring trick, you'll actually get the same values as the matrix solution but with less redundancy in the representation. Admittedly you have to be a little more clever with extracting the result, since you don't actually want to divide, but for m+nφ, because the other solution is 1-φ, you can see it turns out to be nWilliamhttps://www.blogger.com/profile/11620499500613863262noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-6758179260943958832020-04-23T11:23:24.286-07:002020-04-23T11:23:24.286-07:00Hi, Fibonacci are just a never ending source of fu...Hi, Fibonacci are just a never ending source of fun and the monoid route is cool! I did Fibonacci numbers via continued fractions and the Golden ratio. http://gitcommit.co.uk/2017/11/16/fractions-to-phi-to-fibonacci/ Anonymoushttps://www.blogger.com/profile/11613070735607358905noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-88308363307908072212020-04-22T01:27:02.708-07:002020-04-22T01:27:02.708-07:00Neat use of exponentiating by squaring on `mtimesD...Neat use of exponentiating by squaring on `mtimesDefault` taking advantage of `x` being a semigroup. It would be great to see that reflected on the docs :-)Anonymoushttps://www.blogger.com/profile/14750617662698462786noreply@blogger.comtag:blogger.com,1999:blog-1777990983847811806.post-77441479092010697222020-04-21T08:41:04.895-07:002020-04-21T08:41:04.895-07:00I was about to mention printing it in hex would be...I was about to mention printing it in hex would be faster. And then I noticed the Integer Show instance is actually *much* faster than Numeric showHex.<br /><br />One's divide and conquer; the other is linear iterated division by base. Joke's on me. :-)<br />Jean-Baptistehttps://www.blogger.com/profile/08518357846553262412noreply@blogger.com