nth fibonacci using matrix exponentiation Algorithm
Fibonacci numbers are strongly related to the golden ratio: Binet's formula expresses the nth Fibonacci number in terms of N and the golden ratio, and imply that the ratio of two consecutive Fibonacci numbers tends to the golden ratio as n increases. In his 1202 book Liber Abaci, Fibonacci introduced the sequence to Western European mathematics, although the sequence had been described earlier in Indian mathematics, as early as 200 BC in work by Pingala on enumerating possible shapes of Sanskrit poetry formed from syllables of two lengths.
At the end of the nth month, the number of pairs of rabbits is equal to the number of mature pairs (that is, the number of pairs in month N – 2) plus the number of pairs alive last month (month N – 1). At the end of the fourth month, the original pair has produced yet another new pair, and the pair birth two months ago also produces their first pair, make 5 pairs. Fibonacci considers the increase of an idealized (biologically unrealistic) rabbit population, assume that: a newly birth breeding pair of rabbits are put in a field; each breeding pair mates at the age of one month, and at the end of their second month they always produce another pair of rabbits; and rabbits never die, but continue breeding forever.
"""
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()
