Как проверить, является ли число Фибоначчи в Clojure?

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 десятичных цифр).

Это первое п й Fibonnacci, где этот алгоритм дает ложный положительный результат для последующего целого числа для 16-разрядного целого числа, связанного с п = 74.

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

Edit: Добавление произвольного прецизионное решение, которое позволяет избежать double s:

Основная трудность заключается в отсутствии целочисленного алгоритма с квадратным корнем.

This Java implementation может быть переведен на 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))))