Как я могу повысить точность реализации Фибоначчи для больших n?

Question

Я использую формулу B inet для вычисления числа Фибоначчи для больших n

B inet Формула:

мой код:

#!/usr/bin/env python3
def calc_fib(n):
  if (n <= 1):
  return n

  root_5    = 5 ** 0.5
  phi_n   = ((root_5 + 1) / 2) ** n
  alpha_n = ((root_5 - 1) / 2) ** n

  fn = round((phi_n - alpha_n) / root_5)
  return fn

n = int(input())
print(calc_fib(n))

$ ./fibonacci.py 200 280571172992512015699912586503521287798784. (неверный)

правильный результат: 280571172992510140037611932413038677189525

1014 * для этой большой проблемы n = 1014 * 1014 скажем, n = 200, результат не точный, я думаю, из-за вычислений с плавающей точкой, как я могу изменить свой код, чтобы я мог получить более точные результаты?

Answer 1

Проблема с формулой B inet состоит в том, что вам требуется повышенная точность для выполнения вычислений, а с плавающей запятой это вам не предоставляется.

Существует несколько способов эффективного вычисления чисел Фибоначчи. Вот мой любимый, он не является (явно) итеративным и имеет примерно правильную сложность времени выполнения:

def fib(n):
    X = 1<<(n+2)
    return pow(X, n+1, X*X-X-1) % X

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

Альтернативные подходы log (n) - использовать формулы удвоения, использовать целочисленную версию формулы B inet (обычно в алгебре * 1015). * кольцо) или матрица питания. У меня есть запись в блоге, описывающая их более подробно: https://blog.paulhankin.net/fibonacci2/

Answer 2

Я думаю, что вы хотите исправить alpha_n по формуле:

alpha_n = ((1 - root_5) / 2) ** n