{"id":1045,"date":"2010-12-19T17:07:59","date_gmt":"2010-12-19T17:07:59","guid":{"rendered":"http:\/\/www.navision-blog.de\/2010\/12\/19\/compute-fibn-in-olog-n\/"},"modified":"2010-12-19T17:07:59","modified_gmt":"2010-12-19T17:07:59","slug":"compute-fibn-in-olog-n","status":"publish","type":"post","link":"http:\/\/www.navision-blog.de\/blog\/2010\/12\/19\/compute-fibn-in-olog-n\/","title":{"rendered":"Compute Fib(n) in O(log n)"},"content":{"rendered":"<p>Today I learned a neat way to compute the n.th Fibonacci number in O(log n) time. The idea is that we can compute the <a href=\"http:\/\/mathworld.wolfram.com\/FibonacciQ-Matrix.html\">Fibonacci Q-Matrix<\/a> in O(log n) by using recursive powering:<\/p>\n<p><img loading=\"lazy\" style=\"border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px\" title=\"Fibonacci Q-Matrix\" border=\"0\" alt=\"Fibonacci Q-Matrix\" src=\"http:\/\/www.navision-blog.de\/images\/ComputeFibninOlogn_FEFC\/q.png\" width=\"240\" height=\"89\" \/><\/p>\n<p>And here is a simple implementation in F#:<\/p>\n<pre>let q1 = 1I,1I,1I,0I\n\nlet mult (a11,a12,a21,a22) (b11,b12,b21,b22) = \n    a11 * b11 + a12 * b21,\n    a11 * b12 + a12 * b22,\n    a21 * b11 + a22 * b21,\n    a21 * b12 + a22 * b22\n\nlet sq x = mult x x\n\nlet rec pow x n =\n    match n with\n    | 1 -&gt; x\n    | z when z % 2 = 0 -&gt; pow x (n\/2) |&gt; sq\n    | _ -&gt; pow x ((n-1)\/2) |&gt; sq |&gt; mult x\n         \nlet fib n =\n    let _,x,_,_ = pow q1 n\n    x\n\nprintfn &quot;%A&quot; (fib 49)<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Today I learned a neat way to compute the n.th Fibonacci number in O(log n) time. The idea is that we can compute the Fibonacci Q-Matrix in O(log n) by using recursive powering: And here is a simple implementation in F#: let q1 = 1I,1I,1I,0I let mult (a11,a12,a21,a22) (b11,b12,b21,b22) = a11 * b11 + a12 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[448],"tags":[604,664,605],"_links":{"self":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/1045"}],"collection":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/comments?post=1045"}],"version-history":[{"count":0,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/1045\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/media?parent=1045"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/categories?post=1045"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/tags?post=1045"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}