如何提高Fibonacci实现对大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. （错）

正确的结果是：28057117299251014003761193241038677189525

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

Answer 1

比奈公式的问题是，你需要提高计算的精度，而浮点运算并不能给你这个

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

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

这使用了一个位数随n线性增长的算术，我认为这是可以的，因为结果的位数是线性增长的

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

Answer 2

我认为您需要根据以下公式更正alpha_n：

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