]> git.rkrishnan.org Git - sicp.git/blob - src/sicp/ex1_19.clj
Solution to 4.44. A bit too verbose. Can be improved by better
[sicp.git] / 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))