Почему результат начинает расходиться после определенного числа для последовательности Фибоначчи?

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)

И когда я увеличиваю предел l oop, результаты начинают расходиться гораздо больше.

~$ 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 - это quadrati c в своем аргументе, в то время как он должен быть только линейным .

Answer 2

fibonaccip даст приблизительное значение, поскольку у вас нет точных значений для квадрата root из 5. При увеличении значения n ошибка также будет увеличиваться.