{"id":1282,"date":"2020-02-28T03:05:17","date_gmt":"2020-02-28T03:05:17","guid":{"rendered":"https:\/\/muthu.co\/?p=1282"},"modified":"2021-05-24T02:36:03","modified_gmt":"2021-05-24T02:36:03","slug":"fast-nth-fibonacci-number-algorithm","status":"publish","type":"post","link":"http:\/\/write.muthu.co\/fast-nth-fibonacci-number-algorithm\/","title":{"rendered":"Fast nth Fibonacci number algorithm"},"content":{"rendered":"\n

Definition: The Fibonacci sequence is defined by the equation,<\/p>\n\n\n\n

\"\"<\/a><\/figure><\/div>\n\n\n\n

where \\(F(0) = 0 \\), \\(F(1) = 1 \\) and \\(F(n) = F(n-1) + F(n-2) \\text{for } n \\geq 2 \\). This gives us the sequence 0,1,1,2,3,5,8,13 … called the Fibonacci Sequence.<\/p>\n\n\n\n

This post is about how fast we can find the nth number in the Fibonacci series.<\/p>\n\n\n\n

Textbook Algorithm<\/h2>\n\n\n\n

Most textbooks present a simple algorithm for computing the nth Fibonacci number which quickly becomes super slow for larger N. See the implementation below.<\/p>\n\n\n\n

# naive fibonacci \niterations = 0\ndef fib(n):\n    global iterations\n    \n    if n == 0:\n        return 0\n    elif n == 1:\n        iterations+=1\n        return 1\n    else:\n        iterations+=1\n        return fib(n-1) + fib(n-2)\n\nprint(\"sum:\", fib(40)) # sum: 102334155\nprint(\"total iterations\", iterations)  # total iterations 267914295\n<\/code><\/pre>\n\n\n\n
I have also given the output of the execution in the comment next to the print statement. As you can see, the number of iterations is quite large and if you are running the code in your system you would also notice it takes a few seconds to finish the execution. The running time of this algorithm is exponential which clearly indicates slowness.<\/p>\n\n\n\n
Dynamic Programming<\/h2>\n\n\n\n
Now to make this algorithm run faster we will have to first look at the recursive calls our algorithm makes to arrive at the nth Fibonacci number.<\/p>\n\n\n\n
\"\"<\/a>
The recursion tree for computing F7; arrows represent recursive calls 
Source:http:\/\/jeffe.cs.illinois.edu\/teaching\/algorithms\/<\/span><\/figcaption><\/figure><\/div>\n\n\n\n
As you can see In the recursion tree above, most of the values of the right sub tree are calculated more than once, which means, it is computing the same Fibonacci number many times over. So, If we could reduce those calculations we should be able to significantly speed up our algorithm. This is where we use Memoization technique from Dynamic Programming, which is nothing but memorising each new Fibonacci number and  using it in our algorithm to reduce duplicate operations.<\/p>\n\n\n\n
Code with memoization<\/p>\n\n\n\n
# memoization fibonacci\niterations = 0\ndef memoize(f):\n    memo = {}\n    def helper(x):\n        if x not in memo:            \n            memo[x] = f(x)\n        return memo[x]\n    return helper\n\nfib = memoize(fib)\nprint(\"sum:\", fib(40)) # sum: 102334155\nprint(\"total iterations\", iterations) # total iterations 40<\/code><\/pre>\n\n\n\n
The code only ran 40 iterations! On my machine, the result came instantly. If you trace the calls done after memoization you would notice that most of the right sub tree calculations have been memorised and reused during our computation.<\/p>\n\n\n\n
\"\"<\/a><\/figure><\/div>\n\n\n\n
The running time comes down to \\(O(n) \\) which is evident from the iteration counter.<\/p>\n\n\n\n
Another way of memorising the values without using recursion is to keep track of the last two numbers in the fibonacci series. This also runs with the same time complexity of \\(O(n) \\). Code is given below.<\/p>\n\n\n\n
iterations = 0\ndef fib(n):\n    global iterations\n    new, old = 1, 0\n    for i in range(n):\n            new, old = old, new + old\n            iterations+=1 #keep track of how many times its run\n    return old\nprint(\"sum:\", fib(40)) #sum:102334155\nprint(\"total iterations:\", iterations) #total iterations 40<\/code><\/pre>\n\n\n\n
In both the linear and recursive method we calculated the Fibonacci numbers using our knowledge or already calculated Fibonacci numbers. Can we make this algorithm run even more faster? Which takes us to another interesting method using matrices.<\/p>\n\n\n\n
Matrix Exponentiation<\/h2>\n\n\n\n
Take a look at the below matrix:<\/p>\n\n\n\n
\\begin{align}
\\begin{bmatrix}
0 & 1 \\\\
1 & 1
\\end{bmatrix} \\begin{bmatrix}
x \\\\
y
\\end{bmatrix} = \\begin{bmatrix}
y \\\\
x + y
\\end{bmatrix}
\\end{align}<\/p>\n\n\n\n
What the above matrix means is, if we multiply a two dimensional vector by \\(\\begin{bmatrix} 0 & 1 \\\\  1 & 1 \\end{bmatrix} \\) we get the same result as we get from our Fibonacci function. So multiplying the matrix n times is the same as iterating the loop n times which implies:<\/p>\n\n\n\n
\\begin{align}
\\begin{bmatrix}
0 & 1 \\\\
1 & 1
\\end{bmatrix}^{n} \\begin{bmatrix}
1 \\\\
0
\\end{bmatrix} = \\begin{bmatrix}
F_{n-1} \\\\
F_{n}
\\end{bmatrix}
\\end{align}<\/p>\n\n\n\n
Python code for the matrix method is as below:<\/p>\n\n\n\n
import numpy as np\nfrom numpy.linalg import matrix_power\n\ndef fibmat(n):\n    i = np.array([[0, 1], [1, 1]])\n    return np.matmul(matrix_power(i, n), np.array([1, 0]))[1]\n\nprint(fibmat(40)) #output : 102334155<\/code><\/pre>\n\n\n\n
Since we are repeatedly squaring and the nth power only takes \\(O(logn) \\) time. The complexity of our algorithm now reduces to \\(O(logn) \\) which is a significant improvement over our slow and linear time algorithms.<\/p>\n\n\n\n
Double Fibonacci<\/h2>\n\n\n\n
We can further improve the speed using the below formulas which reduces the number of computations if not the time complexity.<\/p>\n\n\n\n
\\(F_{2n-1} = F_{n-1}^{2} + F_{n}^{2} \\)
\\(F_{2n} = F_{n}(2F_{n-1} + F_{n}) \\)<\/p>\n\n\n\n
The above formula is derived from the Matrix Exponentiation. The code for Double Fibonacci is as given below.<\/p>\n\n\n\n
def fib(n):\n    if n%2 == 0:#even\n        return fib_even(n)\n    return fib_odd(n)\n\ndef fib_odd(N):\n    n = int((N+1)\/2)\n    Fn = fibmat(n) \n    Fn1 = fibmat(n-1)\n    return Fn1**2 + Fn**2\n\ndef fib_even(N):\n    n = int(N\/2)\n    Fn = fibmat(n) \n    Fn1 = fibmat(n-1)\n    return Fn * (2*Fn1 + Fn)\n\nprint(fib(40)) #op: 102334155\nprint(fib(39)) #op: 63245986<\/code><\/pre>\n\n\n\n
References:<\/p>\n\n\n\n
http:\/\/jeffe.cs.illinois.edu\/teaching\/algorithms\/book\/03-dynprog.pdf
https:\/\/docs.scipy.org\/doc\/numpy\/reference\/generated\/numpy.linalg.matrix_power.html
https:\/\/www.nayuki.io\/page\/fast-fibonacci-algorithms<\/p>\n","protected":false},"excerpt":{"rendered":"
Definition: The Fibonacci sequence is defined by the equation, where \\(F(0) = 0 \\), \\(F(1) = 1 \\) and \\(F(n) = F(n-1) + F(n-2) \\text{for } n \\geq 2 \\). This gives us the sequence 0,1,1,2,3,5,8,13 … called the Fibonacci Sequence. This post is about how fast we can find the nth number in the […]<\/p>\n","protected":false},"author":1,"featured_media":1323,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[41,6,32],"tags":[44,54,58],"_links":{"self":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1282"}],"collection":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/comments?post=1282"}],"version-history":[{"count":3,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1282\/revisions"}],"predecessor-version":[{"id":1849,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1282\/revisions\/1849"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/media\/1323"}],"wp:attachment":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/media?parent=1282"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/categories?post=1282"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/tags?post=1282"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}