последовательность Фибоначчи отрицательный ответ после 92 питона

Question

Я пытаюсь создать функцию, которая дает мне последовательность Фибоначчи для любого значения n.Однако после n = 92 я получаю неправильные ответы.

eg. For n = 93
Expected output = 12200160415121876738
Actual Output = -6246583658587674878

Мой код ниже:

import numpy as np
def Power(M, n):
         if not n:
                 return 1
         elif n % 2:
                 return M*Power(M, n-1)
         else:
                 sqrt = Power(M, n//2)
                 return sqrt**2

  def _fib(n):
     G = np.matrix([[1,1],[1,0]])
     F = Power(G, n)
     return F[0,1]   

Я думаю, что это как-то связано с целочисленным переполнением, связанным с ограничением библиотеки матриц.Я не уверен, как это исправить.Пожалуйста, помогите мне.Я бы предпочел, чтобы этот алгоритм был улучшен.

Используемый алгоритм:

Answer 1

Вы должны установить явное dtype, чтобы учесть большие числа в вашей матрице:

G = np.matrix([[1,1],[1,0]], dtype=np.uint64)

Однако это поднимает планку лишь незначительно (если ваша система даже не использует это по умолчанию)и скоро тоже переполнится, и вы даже не заметите это так же легко, как числа не станут отрицательными ...

@ Ответ Михаила работает намного лучше.

Answer 2

Вы должны разрешить числа с большим числом, иначе вы ограничены 63 битами по умолчанию (+ знак бита) или np.uint64, который только на 1 бит больше:

import numpy as np
def Power(M, n):
   if not n:
      # Original 'return 1' does not work with n=0
      return np.identity(2, dtype=object)
   elif n % 2:
      return M*Power(M, n-1)
   else:
      sqrt = Power(M, n//2)
      return sqrt**2

def fib(n):
     # This allows for big-int
     G = np.matrix([[1,1],[1,0]], dtype=object)
     F = Power(G, n)
     return F[0,1]

Answer 3

Звучит так, будто вы сталкиваетесь с проблемами точности с плавающей запятой.

Целые числа Python 3 имеют произвольную точность, поэтому вы можете просто использовать их и lru_cache для запоминания:

from functools import lru_cache


@lru_cache()
def fib(n):
    if n <= 1:
        return 1
    return fib(n - 2) + fib(n - 1)


for x in range(1, 95):
    print(x, fib(x - 1))

выходы

1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89
12 144
13 233
14 377
15 610
16 987
...
92 7540113804746346429
93 12200160415121876738
94 19740274219868223167