Python implementation of solving Fibonacci's nth term (including matrix multiplication + fast powers)

Fibonacci sequence

First let's define the Fibonacci series:

which is the 0th term of the series:

Algorithm 1: Recursion

The number of nodes for recursive computation is of the order of O(2ⁿ), which is very inefficient and there is a lot of repeated computation.

For example:

f(10) = f(9) + f(8)

f(9) = f(8) + f(7) Repeat 8

f(8) = f(7) + f(6) repeat 7

Time complexity is O(2ⁿ), extremely slow

def F1(n):
    if n <= 1: return max(n, 0)  # The first two
    return F1(n-1)+F1(n-2)  # recursive (calculation)

Algorithm 2: Memorized Search

Open a large array to record intermediate results, if a state has been computed, check the table directly, otherwise recursively compute it again.

There are n states in total, and the complexity of computing each state is O(1), so the time complexity is O(n). However, since it is a recursive computation, too many layers of recursion will burst the stack.

res = [None]*100000
def F2(n):
    if n <= 1: return max(n, 0)
    if res[n]: return res[n]  # Direct lookup returns results if they already exist
    res[n] = F2(n-1)+F2(n-2)  # Calculated if not present
    return res[n]

Algorithm 3: Recursion

Open a large array and record the value of each number. Calculate it recursively with a loop.

A total of n states are computed, so the time complexity is O(n). However, an array of length n needs to be opened and memory will be the bottleneck.

def F3(n):
    if n <= 1: return max(n, 0)
    res = [0, 1]
    for i in range(2,n+1):
        (res[i-1]+res[i-2])
    return res[n]

Algorithm 4: Recursion + Rolling Variables

One of the better solutions. On closer inspection we see that when recursing we only need to record the values of the first two items, there is no need to record all the values, so we can recursively use rolling variables.

The time complexity is still O(n), but the space complexity becomes O(1).

def F4(n):
    if n <= 1: return max(n, 0)
    fn, f0, f1 = 0, 1, 0  # fn is the final result, f0 is item 0 and f1 is the first item.
    for i in range(2, n+1):
        fn = f0 + f1  # The first two and
        f0, f1 = f1, fn  # Recursive variables
    return fn

Algorithm 5: Matrix Multiplication + Fast Powers

Use the properties of matrix operations to turn the generalized formula into power form and then solve for the nth term by squaring multiplication (fast power).

Let's start with the general formula:

Prove it using mathematical induction:

Here a0,a1,a2 corresponds to the first Fibonacci term.

Testify to the end.

So all we want to get An is to find Aⁿ and take the second element of the first row.

If one simply loops through the nth power from 0, the time complexity is still O(n), and not faster than the previous one. We can consider the following property of multiplication, i.e., fast powers:

This requires only logn operations to get the result, with a time complexity of O(logn)

def mul(a, b):  # First define the second-order matrix multiplication operation
    c = [[0, 0], [0, 0]]  # Define an empty second-order matrix and store the result
    for i in range(2):  # row
        for j in range(2):  # col
            for k in range(2):  # Calculate the value of a new second-order matrix
                c[i][j] += a[i][k] * b[k][j]
    return c
def F5(n):
    if n <= 1: return max(n, 0)
    res = [[1, 0], [0, 1]]  # The unit matrix, equivalent to 1
    A = [[1, 1], [1, 0]]  # A matrix
    while n:
        if n & 1: res = mul(res, A)  # If n is odd, or until n=1 stopping condition
        A = mul(A, A)  # Fast powers
        n >>= 1  # Divide by 2 and round down
    return res[0][1]

Overall not very difficult and good for expanding ideas. For more information about Python please follow my other related articles! I hope you will support me more in the future!