Module gopy.matrix.nth_fibonacci_using_matrix_exponentiation

Implementation of finding nth fibonacci number using matrix exponentiation. Time Complexity is about O(log(n)*8), where 8 is the complexity of matrix multiplication of size 2 by 2. And on the other hand complexity of bruteforce solution is O(n). As we know f[n] = f[n-1] + f[n-1] Converting to matrix, [f(n),f(n-1)] = [[1,1],[1,0]] * [f(n-1),f(n-2)] -> [f(n),f(n-1)] = [[1,1],[1,0]]^2 * [f(n-2),f(n-3)] … … -> [f(n),f(n-1)] = [[1,1],[1,0]]^(n-1) * [f(1),f(0)] So we just need the n times multiplication of the matrix [1,1],[1,0]]. We can decrease the n times multiplication by following the divide and conquer approach.

"""
Implementation of finding nth fibonacci number using matrix exponentiation.
Time Complexity is about O(log(n)*8), where 8 is the complexity of matrix multiplication of size 2 by 2.
And on the other hand complexity of bruteforce solution is O(n).
As we know
    f[n] = f[n-1] + f[n-1]
Converting to matrix,
    [f(n),f(n-1)] = [[1,1],[1,0]] * [f(n-1),f(n-2)]
->  [f(n),f(n-1)] = [[1,1],[1,0]]^2 * [f(n-2),f(n-3)]
    ...
    ...
->  [f(n),f(n-1)] = [[1,1],[1,0]]^(n-1) * [f(1),f(0)]
So we just need the n times multiplication of the matrix [1,1],[1,0]].
We can decrease the n times multiplication by following the divide and conquer approach.
"""


def multiply(matrix_a, matrix_b):
    matrix_c = []
    n = len(matrix_a)
    for i in range(n):
        list_1 = []
        for j in range(n):
            val = 0
            for k in range(n):
                val = val + matrix_a[i][k] * matrix_b[k][j]
            list_1.append(val)
        matrix_c.append(list_1)
    return matrix_c


def identity(n):
    return [[int(row == column) for column in range(n)] for row in range(n)]


def nth_fibonacci_matrix(n):
    """
    >>> nth_fibonacci_matrix(100)
    354224848179261915075
    >>> nth_fibonacci_matrix(-100)
    -100
    """
    if n <= 1:
        return n
    res_matrix = identity(2)
    fibonacci_matrix = [[1, 1], [1, 0]]
    n = n - 1
    while n > 0:
        if n % 2 == 1:
            res_matrix = multiply(res_matrix, fibonacci_matrix)
        fibonacci_matrix = multiply(fibonacci_matrix, fibonacci_matrix)
        n = int(n / 2)
    return res_matrix[0][0]


def nth_fibonacci_bruteforce(n):
    """
    >>> nth_fibonacci_bruteforce(100)
    354224848179261915075
    >>> nth_fibonacci_bruteforce(-100)
    -100
    """
    if n <= 1:
        return n
    fib0 = 0
    fib1 = 1
    for i in range(2, n + 1):
        fib0, fib1 = fib1, fib0 + fib1
    return fib1


def main():
    fmt = "{} fibonacci number using matrix exponentiation is {} and using bruteforce is {}\n"
    for ordinal in "0th 1st 2nd 3rd 10th 100th 1000th".split():
        n = int("".join(c for c in ordinal if c in "0123456789"))  # 1000th --> 1000
        print(fmt.format(ordinal, nth_fibonacci_matrix(n), nth_fibonacci_bruteforce(n)))
    # from timeit import timeit
    # print(timeit("nth_fibonacci_matrix(1000000)",
    #              "from main import nth_fibonacci_matrix", number=5))
    # print(timeit("nth_fibonacci_bruteforce(1000000)",
    #              "from main import nth_fibonacci_bruteforce", number=5))
    # 2.3342058970001744
    # 57.256506615000035


if __name__ == "__main__":
    main()

Functions

def identity(n)

Expand source code

def identity(n):
    return [[int(row == column) for column in range(n)] for row in range(n)]

def main()

Expand source code

def main():
    fmt = "{} fibonacci number using matrix exponentiation is {} and using bruteforce is {}\n"
    for ordinal in "0th 1st 2nd 3rd 10th 100th 1000th".split():
        n = int("".join(c for c in ordinal if c in "0123456789"))  # 1000th --> 1000
        print(fmt.format(ordinal, nth_fibonacci_matrix(n), nth_fibonacci_bruteforce(n)))

def multiply(matrix_a, matrix_b)

Expand source code

def multiply(matrix_a, matrix_b):
    matrix_c = []
    n = len(matrix_a)
    for i in range(n):
        list_1 = []
        for j in range(n):
            val = 0
            for k in range(n):
                val = val + matrix_a[i][k] * matrix_b[k][j]
            list_1.append(val)
        matrix_c.append(list_1)
    return matrix_c

def nth_fibonacci_bruteforce(n)

>>> nth_fibonacci_bruteforce(100)
354224848179261915075
>>> nth_fibonacci_bruteforce(-100)
-100

Expand source code

def nth_fibonacci_bruteforce(n):
    """
    >>> nth_fibonacci_bruteforce(100)
    354224848179261915075
    >>> nth_fibonacci_bruteforce(-100)
    -100
    """
    if n <= 1:
        return n
    fib0 = 0
    fib1 = 1
    for i in range(2, n + 1):
        fib0, fib1 = fib1, fib0 + fib1
    return fib1

def nth_fibonacci_matrix(n)

>>> nth_fibonacci_matrix(100)
354224848179261915075
>>> nth_fibonacci_matrix(-100)
-100

Expand source code

def nth_fibonacci_matrix(n):
    """
    >>> nth_fibonacci_matrix(100)
    354224848179261915075
    >>> nth_fibonacci_matrix(-100)
    -100
    """
    if n <= 1:
        return n
    res_matrix = identity(2)
    fibonacci_matrix = [[1, 1], [1, 0]]
    n = n - 1
    while n > 0:
        if n % 2 == 1:
            res_matrix = multiply(res_matrix, fibonacci_matrix)
        fibonacci_matrix = multiply(fibonacci_matrix, fibonacci_matrix)
        n = int(n / 2)
    return res_matrix[0][0]