为什么斐波那契数列在一定数量后结果开始发散？

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

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

Answer 2

正如其他人已经提到的，舍入误差会迅速累积，所以你应该坚持使用整数算法，使用 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 在其参数中是 二次方，而它仅必须是线性.

为什么斐波那契数列在一定数量后结果开始发散？

Why result starts diverging after certain number for Fibonacci sequence?

sbcl

common-lisp