直接与递归计算给定的斐波那契号的错误

Question

当我注意到以下内容时，我很无聊，正在使用一些数学和Python编码，

递归（或使用for loop），您只需将整数添加在一起即可获得给定的fibonacci编号。但是，还有一个用于计算斐波那契数的直接方程，对于大n，该方程将给出的答案，坦率地说，相对于递归计算的斐波那契数，这是完全错误的。

我想这是由于圆形和浮点算术（SQRT（5）毕竟是不合理的），如果是这样，有人可以将我指向我如何修改fibo_calc_direct函数以返回更准确的结果的方向？

谢谢！

def fib_calc_recur(n, ii = 0, jj = 1): 
    #n is the index of the nth fibonacci number, F_n, where F_0 = 0, F_1 = 1, ...
    if n == 0: #use recursion
        return ii
    if n == 1:
        return jj
    else:
        return(fib_calc_recur(n -1, jj, ii + jj))

def fib_calc_direct(n):

    a = (1 + np.sqrt(5))/2
    b = (1 - np.sqrt(5))/2

    f = (1/np.sqrt(5)) * (a**n - b**n)
    return(f)

Answer 1

您可以使用根据n

而不是您的问题，设置其精度，但我会使用添加方法的迭代版本。这是一个对n的值进行的计算（幼稚的添加，直接添加，用小数）进行的脚本，最高为4000：

def fib_calc_iter(n): 
    a, b = 0, 1
    
    if n < 2:
        return n
    for _ in range(1, n):
        a, b = b, a + b
    return b

from decimal import Decimal, getcontext

def fib_calc_decimal(n):
    getcontext().prec = n // 4 + 3  # Choose a precision good enough for this n
    sqrt5 = Decimal(5).sqrt()
    da = (1 + sqrt5) / 2
    db = (1 - sqrt5) / 2
    f = (da**n - db**n) / sqrt5
    return int(f + Decimal(0.5))  # Round to nearest int

# Test it...
for n in range(1, 4000):
    x = fib_calc_iter(n)
    y = fib_calc_decimal(n)
    if x != y:
        print(f"Difference found for n={n}.\nNaive method={x}.\nDecimal method={y}")
        break
else:
    print("No differences found")