Millionth Fibonacci Number - Numpy Python Implementation

Question

I am trying to implement a code which works for retrieving Millionth Fibonacci number or beyond. I am using Matrix Multiplication with Numpy for faster calculations.

According to my understanding it should take O(logN) time and worst case for a million should result in: Nearly 6secs which should be alright.

Following is my implementation:

def fib(n):
    import numpy as np
    matrix = np.matrix([[1, 1], [1, 0]]) ** abs(n)
    if n%2 == 0 and n < 0:
        return -matrix[0,1]
    return matrix[0, 1]

However, leave 1million, it is not even generating correct response for 1000

Actual response:

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

My Response:

817770325994397771

Why is Python truncating the responses generally from the docs it should be capable of calulating even 10**1000 values. Where did I go wrong?

Answer 1

Numpy can handle numbers and calculations in a high-performance way (both memory efficiency and computing time). So while Python can process sufficiently large numbers, Numpy can't. You can let Python do the calculation and get the result, exchanging with performance reduction.

Sample code:

import numpy as np

def fib(n):
    # the difference is dtype=object, it will let python do the calculation
    matrix = np.matrix([[1, 1], [1, 0]], dtype=object) ** abs(n)
    if n%2 == 0 and n < 0:
        return -matrix[0,1]
    return matrix[0, 1]

print(fib(1000))

Output:

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

PS: Warning

Milionth Fibonacci number is extremely large, you should make sure that Python can handle it. If not, you will have to implement/find some module to handle these large numbers.