对于大n，如何提高斐波那契实现的精度？

Question

我正在使用Binet公式计算大n的斐波那契数

Binet的公式：

我的代码：

#!/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.py200280571172992512015699912586503521521798784。（（错误）

正确的结果是：280571172992510140037611932413038677189525

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

Answer 1

Binet公式的问题是，您需要提高准确性来进行计算，而浮点数不能满足您的要求。

有几种方法可以有效地计算斐波那契数。这是我的最爱，它不是（显式）迭代的，并且具有适当的运行时复杂度：

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

[这使用具有随n线性增长的位数的算术，我认为这是可以的，因为结果的位数线性增长。

替代log（n）方法将使用加倍公式，使用Binet公式的整数形式（通常在代数环中）或矩阵幂。我有一篇博客文章更详细地描述了它们：https://blog.paulhankin.net/fibonacci2/

Answer 2

我认为您想根据公式更正alpha_n：

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