如何提高大 n 的斐波那契实现的准确性？

Question

我正在使用比奈公式来计算大n的斐波那契数列

比奈公式：

我的代码：

#!/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

问题是，对于非常大的n，比如说n = 200，结果不准确，我认为由于浮点计算，我该如何更改我的代码，以便我可以获得更准确的结果？

Answer 1

Binet公式的问题在于，您需要提高准确性才能进行计算，而浮点数并不能为您提供这一点。有几种方法可以有效地计算斐波那契数列。这是我最喜欢的，它不是（明确地）迭代的，并且具有大致正确的运行时复杂性：def fib(n):&nbsp; &nbsp; X = 1<<(n+2)&nbsp; &nbsp; return pow(X, n+1, X*X-X-1) % X这使用具有与n线性增长的位数的算术，我认为这是可以的，因为结果的位数线性增长。替代的 log（n） 方法是使用加倍公式，使用 Binet 公式的整数版本（通常在代数环中）或矩阵幂。我有一篇博客文章更详细地描述了它们：https://blog.paulhankin.net/fibonacci2/

Answer 2

我想你想根据公式纠正：alpha_nalpha_n&nbsp;=&nbsp;((1&nbsp;-&nbsp;root_5)&nbsp;/&nbsp;2)&nbsp;**&nbsp;n