如何在 Clojure 中实现这种快速翻倍斐波那契算法？

Question

这是我查找第 n 个斐波那契数的方法：

(defn fib-pair [[a b]]
  "Return the next Fibonacci pair number based on input pair."
  [b (+' a b)])    ; Use +' for automatic handle large numbers (Long -> BigInt).

(defn fib-nth [x]
  "Return the nth Fibonacci number."
  (nth (map first (iterate fib-pair [0 1])) x))

我知道这可能不是最有效的方法，并且我找到了快速加倍算法。

该算法包含矩阵和数学方程，我不知道如何在Stack Overflow中设置它们，请访问：

https://www.nayuki.io/page/fast-fibonacci-algorithms

我尝试了该网站提供的Python实现，速度非常快。如何在 Clojure 中实现它？

编辑：该网站提供的Python实现：

# Returns F(n)
def fibonacci(n):
    if n < 0:
        raise ValueError("Negative arguments not implemented")
    return _fib(n)[0]


# Returns a tuple (F(n), F(n+1))
def _fib(n):
    if n == 0:
        return (0, 1)
    else:
        a, b = _fib(n // 2)
        c = a * (2 * b - a)
        d = b * b + a * a
        if n % 2 == 0:
            return (c, d)
        else:
            return (d, c + d)

Answer 1

我还没有检查性能，但这似乎是 Clojure 中的忠实实现：

(defn fib [n]
  (letfn [(fib* [n]
            (if (zero? n)
              [0 1]
              (let [[a b] (fib* (quot n 2))
                    c (*' a (-' (*' 2 b) a))
                    d (+' (*' b b) (*' a a))]
                (if (even? n)
                  [c d]
                  [d (+' c d)]))))]
    (first (fib* n))))