如何检查一个数字是否为Clojure中的Fibonacci数？

Question

输入:一个正整数。

输出:基于测试的真/假。

以下是我的尝试：

(defn is-a-fib? [x]
  "Check whether x is a fibonacci number.
   Algorithm: test whether 5x^2+4 or 5x^2-4 is a perfect square."
  (let [a (+' (*' (Math/pow x 2) 5) 4)                      ; 5x^2+4
        b (-' (*' (Math/pow x 2) 5) 4)                      ; 5x^2-4
        sqrt-a (Math/sqrt a)
        sqrt-b (Math/sqrt b)]
    (or (== (*' sqrt-a sqrt-a)
            (*' (Math/floor sqrt-a) (Math/floor sqrt-a)))  ; Test whether n is a perfect square
        (== (*' sqrt-b sqrt-b)
            (*' (Math/floor sqrt-b) (Math/floor sqrt-b))))))

问题是:这段代码不适用于大量的代码。我认为它可能会导致堆栈溢出。有更好的办法吗？

Answer 1

Math/pow、Math/sqrt和Math/floor操作在精度范围有限的double上工作，对它们的操作将有舍入错误。

如果你从这个角度来看，事情可能会因为四舍五入而脱轨，但是当你用完精度(15到17小数位数)时，它们真的会出错。

第一个n_th Fibonnacci (该算法为后续整数提供假正数)是与_n = 74相关联的16位整数。

(is-a-fib? 1304969544928657)
=> true
(is-a-fib? 1304969544928658)
=> true

编辑：添加避免double的任意精度解决方案：

主要的困难在于缺乏整数平方根算法。

这个Java实现可以被翻译成Clojure：

(defn integer-sqrt [n]
  (let [n (biginteger n)]
    (loop [a BigInteger/ONE
           b (-> n (.shiftRight 5) (.add (biginteger 8)))]
      (if (>= (.compareTo b a) 0)
        (let [mid (-> a (.add b) (.shiftRight 1))]
          (if (pos? (-> mid (.multiply mid) (.compareTo n)))
            (recur a (.subtract mid BigInteger/ONE))
            (recur (.add mid BigInteger/ONE) b)))
        (dec a)))))

在此之后，您可以定义任意精度的完美平方测试：

(defn perfect-square? [n]
  (let [x (integer-sqrt n)]
    (= (*' x x) n)))

并更新您的实现以使用它：

(defn is-a-fib? [x]
  "Check whether x is a fibonacci number.
   Algorithm: test whether 5x^2+4 or 5x^2-4 is a perfect square."
  (let [a (+' (*' (*' x x) 5) 4)                            ; 5x^2+4
        b (-' (*' (*' x x) 5) 4)]                           ; 5x^2-4
    (or (perfect-square? a)
        (perfect-square? b))))