你确实看到了舍入错误.

矩阵形式是更准确和更快的算法. Literateprograms.org列出了一个很好的实现,但它还列出了基于Lucas数的以下算法：

def powLF(n):

if n == 1: return (1, 1)

L, F = powLF(n//2)

L, F = (L**2 + 5*F**2) >> 1, L*F

if n & 1:

return ((L + 5*F)>>1, (L + F) >>1)

else:

return (L, F)

def fib(n):

if n & 1:

return powLF(n)[1]

else:

L, F = powLF(n // 2)

return L * F

上述算法和矩阵方法都具有Θ(lg n)复杂度,就像您使用的朴素递归平方方法一样,但没有舍入问题. Lucas数字方法具有最低的常数成本,使其成为更快的算法(大约是矩阵方法的两倍)：

>>> timeit.timeit('fib(1000)', 'from __main__ import fibM as fib', number=10000)

0.40711593627929688

>>> timeit.timeit('fib(1000)', 'from __main__ import fibL as fib', number=10000)

0.20211100578308105