fibonacci with matrix exponentiation

deps.edn

{:paths ["."]
 :deps {org.clojure/algo.generic {:mvn/version "0.1.2"}}}

fib_matrix.clj

(ns fib-matrix
  (:require [clojure.algo.generic.arithmetic :refer [*]])
  (:refer-clojure :exclude [*]))

(defrecord Mat [a b
                c d])

(defmethod * [Mat Mat]
  [{:keys [a b
           c d]}
   {x :a, y :b,
    z :c, w :d}]
  (->Mat (+ (* a x) (* b z)) (+ (* a y) (* b w))
         (+ (* c x) (* d z)) (+ (* c y) (* d w))))

(defn fast-expt [b n]
  (cond
    (zero? n) (->Mat 1 0
                     0 1)
    (even? n) (let [x (fast-expt b (/ n 2))]
                (* x x))
    :else (* b (fast-expt b (dec n)))))

(defn fib [n]
  (-> (->Mat 1 1
             1 0)
      (fast-expt n)
      :b))

;; fib-matrix> (map fib (range 10))
;; (0 1 1 2 3 5 8 13 21 34)

;; tail-recursive implementation
(defn fast-expt' [b n]
  (letfn [(fib-iter [b n a]
            (cond
              (zero? n) a
              (even? n) (recur (* b b) (/ n 2) a)
              :else (recur b (dec n) (* a b))))]
    (fib-iter b n (->Mat 1 0
                         0 1))))

(defn fib' [n]
  (-> (->Mat 1 1
             1 0)
      (fast-expt' n)
      :b))

;; fib-matrix> (map fib' (range 10))
;; (0 1 1 2 3 5 8 13 21 34)