fibonacci using algebraic properties of matrix multiplication and fast power algorithm, adapted from this *great* book : "Elements of Programming" by Alexander Stepanov and Paul McJones http://www.elementsofprogramming.com/

fibonacci-algebraic.clj

(defn power [a n op]
  "Compute a to the (positive int) power n using operator op, using
  exponentiation by squaring."
  (let [ power-accumulate-positive (fn [r a n op]
                                    (let [r (if (odd? n) (op r a) r)]
                                      (if (= 1 n)
                                        r
                                        (recur r (op a a) (quot n 2) op))))]
    (if (odd? n)
      (let [n (quot n 2)]
        (if (zero? n) a (power-accumulate-positive a (op a a) n op)))
      (recur (op a a) (quot n 2) op))))

(defn fibonacci [n]
  "Compute fibonacci number of rank n, using matrix exponentiation"
  (let[fibonacci-matrix-multiply (fn [[x0 x1] [y0 y1]]
                                   [(+ (* x0 (+ y1 y0)) (* x1 y0))
                                    (+ (* x0 y0) (* x1 y1))])]
    (if (zero? n) 0N)
    (first (power [1N 0N] n fibonacci-matrix-multiply))))