为什么斐波那契数列的结果在一定数之后开始发散?

Question

我对通过不同方式计算序列的结果感到困惑：

(defun fig-square-p (n)
"Check if the given N is a perfect square number.
A000290 in the OEIS"
(check-type n (integer 0 *))
(= (floor (sqrt n)) (ceiling (sqrt n))))
(defun fibonaccip (n)
"Check if the given number N is a Fibonacci number."
(check-type n (integer 0 *))
(or (fig-square-p (+ (* 5 (expt n 2)) 4))
(fig-square-p (- (* 5 (expt n 2)) 4))))
(defun fibonacci (n)
"Compute N's Fibonacci number."
(check-type n (integer 0 *))
(loop :for f1 = 0 :then f2
:and f2 = 1 :then (+ f1 f2)
:repeat n :finally (return f1)))
(defun seq-fibonaccies (n)
"Return sequence of Fibonacci numbers upto N."
(check-type n (integer 0 *))
(loop :for i :from 1 :upto n
:collect (fib i)))

CL-USER> (loop :for i :from 0 :upto 7070 :when (fibonaccip i) :collect i)
(0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 2889 3876 4181 5473
6765 7070)
CL-USER> (seq-fibonaccies 21)
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946)

当我增加循环的极限时，结果开始出现更大的分歧。

~$ sbcl --version
SBCL 1.4.14-3.fc31

Answer 1

正如其他人已经提到的，舍入误差会迅速累积， 所以你应该坚持使用整数算术，使用isqrt：

(defun squarep (n)
"Check if the given N is a perfect square number.
https://oeis.org/A000290"
(check-type n (integer 0 *))
(let ((sqrt (isqrt n)))
(= n (* sqrt sqrt))))

此外，您在seq-fibonaccies中有一个拼写错误(fib而不是fibonacci(。

最后，seq-fibonaccies的论点是二次的，而它只有 必须是线性的。

Answer 2

fibonaccip将给出一个估计值，因为您没有 5 平方根的精确值。随着n值的增加，误差也会增加。