{"id":4947,"date":"2024-02-28T19:40:20","date_gmt":"2024-02-29T00:40:20","guid":{"rendered":"https:\/\/ikriv.com\/blog\/?p=4947"},"modified":"2024-10-04T14:04:48","modified_gmt":"2024-10-04T18:04:48","slug":"logarithmic-fibonacci","status":"publish","type":"post","link":"https:\/\/ikriv.com\/blog\/?p=4947","title":{"rendered":"Logarithmic Fibonacci"},"content":{"rendered":"<p>Code: <a href=\"https:\/\/github.com\/ikriv-samples\/logarthmic-fibonacci\">https:\/\/github.com\/ikriv-samples\/logarthmic-fibonacci<\/a>.<\/p>\n<p>Fibonacci sequence is defined as a sequence starting with 0, 1 where each subsequent member is calculated as <code>fib(n) = fib(n-1)+fib(n-2)<\/code>. This yields an infinite sequence 0, 1, 1, 2, 3, 5, 8, 13, &#8230;<\/p>\n<p>This repository compares several approaches to calculating n<em>th<\/em>\u00a0Fibonacci number:<\/p>\n<ul dir=\"auto\">\n<li>A na\u00efve recursive solution<\/li>\n<li>A simple linear solution<\/li>\n<li>A solution that runs in logarithmic time<\/li>\n<\/ul>\n<h1>Running The Samples<\/h1>\n<p><code>python main.py {algorithm} n<\/code>\u00a0<\/p>\n<p>Algorithm can be one of\u00a0<code>linear<\/code>,\u00a0<code>recursive<\/code>, or\u00a0<code>logarithmic<\/code>. If the algorithm is omitted,\u00a0<code>logarthmic<\/code>\u00a0is used.<\/p>\n<h1>Na\u00efve Solution<\/h1>\n<p>It is very easy to program Fibonacci sequence exactly as defined, but it leads to a slow and inefficient solution:<\/p>\n<pre class=\"brush: python; title: ; notranslate\" title=\"\">\r\ndef fib(n: int) -&gt; int:\r\n    if n==0: return 0\r\n    if n==1: return 1\r\n    return fib(n-1)+fib(n-2)\r\n<\/pre>\n<p>This solution has exponential runtime, so it hits extremely long calculation times for relatively small values of n. On my machine\u00a0<code>python main.py recursive 40<\/code>\u00a0takes over 20 seconds.<\/p>\n<h1>Linear Solution<\/h1>\n<pre class=\"brush: python; title: ; notranslate\" title=\"\">\r\ndef fib(n: int) -&gt; int:\r\n    if n==0: return 0\r\n    if n==1: return 1\r\n    prev,current=0,1\r\n    for i in range(n-1):\r\n       prev,current=current,prev+current\r\n    return current\r\n<\/pre>\n<p>This solution works well up to n=100,000 or so, but then it starts to lag.<\/p>\n<h1>Logarithmic Solution<\/h1>\n<p>This solution is based on the fact that 2&#215;2 matrix<\/p>\n<pre><code>    | 1    1 |\r\nA = |        |\r\n    | 1    0 |\r\n<\/code><\/pre>\n<p>when raised to the power of n yields<\/p>\n<pre><code>        | fib(n+1) fib(n)   |\r\nA**n == |                   |\r\n        | fib(n)   fib(n-1) |\r\n<\/code><\/pre>\n<h2>Proof<\/h2>\n<p>The above property can be proved by induction. It is obviously true for n=1. Now, supposed it is true for n=k, so<\/p>\n<pre><code>        | fib(k+1) fib(k)   |\r\nA**k == |                   |\r\n        | fib(k)   fib(k-1) |\r\n<\/code><\/pre>\n<div class=\"zeroclipboard-container\"><\/div>\n<\/div>\n<p dir=\"auto\">Then\u00a0<code>A**(k+1)<\/code>\u00a0is\u00a0<code>(A**k)*A<\/code>, or<\/p>\n<div class=\"snippet-clipboard-content notranslate position-relative overflow-auto\">\n<pre class=\"notranslate\"><code>           | fib(k+1) fib(k)   |   | 1   1 |    | fib(k+1)+fib(k)    fib(k+1) |\r\nA**(k+1) = |                   | * |       | == |                             |\r\n           | fib(k)   fib(k-1) |   | 1   0 |    | fib(k)+fib(k-1)    fib(k)   |\r\n<\/code><\/pre>\n<div class=\"zeroclipboard-container\"><\/div>\n<\/div>\n<p dir=\"auto\">Simplifying this, we get<\/p>\n<div class=\"snippet-clipboard-content notranslate position-relative overflow-auto\">\n<pre class=\"notranslate\"><code>           | fib(k+2)  fib(k+1) |\r\nA**(k+1) = |                    |\r\n           |  fib(k+1)  fib(k)  |\r\n<\/code><\/pre>\n<div class=\"zeroclipboard-container\"><\/div>\n<\/div>\n<p dir=\"auto\">So, the property is proved by induction.<\/p>\n<h2>OK, we proved it. So?<\/h2>\n<p>We can exploit the fact that matrix multiplication is associative to make the number of computations logarithmic. If n is a power of 2, we can compute A**n in log2(n) steps. For example, if n=16, we can compute it in 4 steps:<\/p>\n<pre><code>A2=A*A\r\nA4=A2*A2\r\nA8=A4*A4\r\nA16=A8*A8\r\n<\/code><\/pre>\n<p>If n is not a power of 2, we will assemble A**n from parts using binary representation of n:<\/p>\n<pre><code>n = 11 == 1011b\r\nA2=A*A\r\nA4=A2*A2\r\nA8=A4*A4\r\nAn=A*A2*A8\r\n<\/code><\/pre>\n<p>We can build the result gradually, there is no need to keep the intermediate values:<\/p>\n<pre><code>result=A\r\nA2=A*A\r\nresult=result*A2\r\nA4=A2*A2\r\nA8=A4*A4\r\nresult=result*A8\r\n<\/code><\/pre>\n<p>The same code in Python:<\/p>\n<pre class=\"brush: python; title: ; notranslate\" title=\"\">\r\ndef power(m: Matrix, n: int) -&gt; Matrix:\r\n    result=Matrix(1,0,0,1)\r\n    currentPower=m\r\n    while n&gt;0:\r\n        if n%2==1:\r\n            result=result*currentPower\r\n        n=n\/\/2\r\n        if n&gt;0:\r\n            currentPower=currentPower*currentPower\r\n    return result\r\n\r\ndef fib(n: int) -&gt; int:\r\n    if n==0: return 0\r\n    return power(Matrix(1,1,1,0), n-1)&#x5B;0]\r\n<\/pre>\n<p>The complete code is in\u00a0<a href=\"https:\/\/github.com\/ikriv-samples\/logarthmic-fibonacci\/blob\/main\/logarithmic.py\">logarithmic.py<\/a><\/p>\n<h2>Execution Times<\/h2>\n<p>Recursive approaches runtime increases exponentially. It becomes over 20 seconds for n=40. Linear approach works well up to n~=100,000. Logarithmic approach can calculate value of fib(10_000_000) in a few seconds. We must remember that logarithmic approach is logarithmic only in terms of the number of Python integer multiplications. Since Python integers have arbitrary length, multiplications get slower and slower as the numbers become bigger, so the actual wall clock times will not be truly logarithmic.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Code: https:\/\/github.com\/ikriv-samples\/logarthmic-fibonacci. Fibonacci sequence is defined as a sequence starting with 0, 1 where each subsequent member is calculated as fib(n) = fib(n-1)+fib(n-2). This yields an infinite sequence 0, 1, <a href=\"https:\/\/ikriv.com\/blog\/?p=4947\" class=\"more-link\">[&hellip;]<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"Layout":"","footnotes":""},"categories":[16,26,5],"tags":[],"class_list":["entry","author-ikriv","post-4947","post","type-post","status-publish","format-standard","category-demos","category-python","category-dev"],"_links":{"self":[{"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/4947","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4947"}],"version-history":[{"count":5,"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/4947\/revisions"}],"predecessor-version":[{"id":4952,"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/4947\/revisions\/4952"}],"wp:attachment":[{"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4947"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4947"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/ikriv.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4947"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}