如何提高大 n 的 Fibonacci 实现的准确性？

Question

我正在使用 Binet 公式计算大 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

我想你要根据公式更正alpha_n：

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

Answer 2

Binet 公式的问题在于您需要提高计算的准确性，而浮点数无法满足您的要求。

有几种方法可以有效地计算斐波那契数列。这是我最喜欢的，它不是（明确地）迭代的，并且具有大致正确的运行时复杂性：

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

这使用了一些位数随 n 线性增长的算术，我认为这没问题，因为结果的位数线性增长。

替代的 log(n) 方法是使用加倍公式、使用比奈公式的整数版本（通常在代数环中）或矩阵幂。我有一个博客 post 更详细地描述了它们：https://blog.paulhankin.net/fibonacci2/

如何提高大 n 的 Fibonacci 实现的准确性？

How can I increase the accuracy of Fibonacci implementation for large n?

python

fibonacci