{"id":17548,"date":"2016-07-09T17:34:05","date_gmt":"2016-07-09T22:34:05","guid":{"rendered":"http:\/\/blog.kenperlin.com\/?p=17548"},"modified":"2016-07-09T17:52:18","modified_gmt":"2016-07-09T22:52:18","slug":"fibonacci-fibonacci","status":"publish","type":"post","link":"http:\/\/blog.kenperlin.com\/?p=17548","title":{"rendered":"Fibonacci fibonacci"},"content":{"rendered":"<p>I was typing stuff into node.js today, and I was curious to know what would happen if I fed the Fibonacci function into itself.  Feeling lazy, I first implemented the function the easy way, which takes an exponential time to compute:<\/p>\n<pre>\r\nfib = function(n) { return n < 2 ? n : fib(n-2) + fib(n-1); }\r\n<\/pre>\n<p>But when I ran it on numbers from 1 to 10, it hung after 9:<\/p>\n<pre>\r\n1 1\r\n2 1\r\n3 1\r\n4 2\r\n5 5\r\n6 21\r\n7 233\r\n8 10946\r\n9 5702887\r\n<\/pre>\n<p>So I decided to do it properly, using the non-recursive way of computing the Fibonacci sequence:<\/p>\n<pre>\r\nfunction fib(n) {\r\n   var a, b = 1, c = 1;\r\n   while (--n) {\r\n      a = b;\r\n      b = c;\r\n      c = a + b;\r\n   }\r\n   return b;\r\n}\r\n<\/pre>\n<p>This time everything computed immediately.  Here are the first 11 results of fib(fib(n)):<\/p>\n<pre>\r\n1  1\r\n2  1\r\n3  1\r\n4  2\r\n5  5\r\n6  21\r\n7  233\r\n8  10946\r\n9  5702887\r\n10  139583862445\r\n11  1779979416004714000\r\n<\/pre>\n<p>After that it totally blows up.  fib(fib(12)) is about 10<sup>30<\/sup>, fib(fib(16)) is about 10<sup>206<\/sup>, and from 17 onward the result is so huge that node.js just returns Infinity.<\/p>\n<p>Now I know. \ud83d\ude42<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I was typing stuff into node.js today, and I was curious to know what would happen if I fed the Fibonacci function into itself. Feeling lazy, I first implemented the function the easy way, which takes an exponential time to compute: fib = function(n) { return n < 2 ? n : fib(n-2) + fib(n-1); &hellip; <a href=\"http:\/\/blog.kenperlin.com\/?p=17548\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Fibonacci fibonacci&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"http:\/\/blog.kenperlin.com\/index.php?rest_route=\/wp\/v2\/posts\/17548"}],"collection":[{"href":"http:\/\/blog.kenperlin.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.kenperlin.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.kenperlin.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.kenperlin.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=17548"}],"version-history":[{"count":11,"href":"http:\/\/blog.kenperlin.com\/index.php?rest_route=\/wp\/v2\/posts\/17548\/revisions"}],"predecessor-version":[{"id":17559,"href":"http:\/\/blog.kenperlin.com\/index.php?rest_route=\/wp\/v2\/posts\/17548\/revisions\/17559"}],"wp:attachment":[{"href":"http:\/\/blog.kenperlin.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=17548"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.kenperlin.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=17548"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.kenperlin.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=17548"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}