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

Question

我正在使用比奈公式来计算大n的斐波那契数列比奈公式：我的代码：#!/usr/bin/env python3def 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 fnn = int(input())print(calc_fib(n))$ ./fibonacci.py 200 280571172992512015699912586503521287798784.（错误）正确的结果是：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