src/sicp/ex1_19.clj

   1 (ns sicp.ex1_19
   2   (:use [sicp utils]
   3         [clojure.contrib trace test-is]))
   4
   5 ;; exercise 1.19: fast fibonacci
   6 ;; see the pdf of the notebook scan for the derivation of p' and q'
   7 (defn ffib-iter [a b p q count]
   8   (cond (= count 0) b
   9         (even? count)
  10         (ffib-iter a
  11                    b
  12                    (+ (* p p) (* q q))
  13                    (+ (* 2 p q) (* q q))
  14                    (/ count 2))
  15         :else (ffib-iter (+ (* b q) (* a q) (* a p))
  16                          (+ (* b p) (* a q))
  17                          p
  18                          q
  19                          (- count 1))))
  20
  21 (defn ffib [n]
  22   (ffib-iter 1 0 0 1 n))