From b18a28271ccd7ec4467f219204c31a53976c368d Mon Sep 17 00:00:00 2001
From: Ramakrishnan Muthukrishnan <vu3rdd@gmail.com>
Date: Sun, 11 Apr 2010 01:42:38 +0530
Subject: [PATCH] Added solution to 1.19.

---
 chapter1/ch1_2.clj | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/chapter1/ch1_2.clj b/chapter1/ch1_2.clj
index 0cf3c55..13b99d1 100644
--- a/chapter1/ch1_2.clj
+++ b/chapter1/ch1_2.clj
@@ -536,3 +536,22 @@ TRACE t2916: |    => 6
 TRACE t2915: => 6
 6
 )
+
+;; exercise 1.19: fast fibonacci
+;; see the pdf of the notebook scan for the derivation of p' and q'
+(defn ffib [n]
+  (ffib-iter 1 0 0 1 n))
+
+(defn ffib-iter [a b p q count]
+  (cond (= count 0) b
+	(even? count)
+	(ffib-iter a
+		   b
+		   (+ (* p p) (* q q))
+		   (+ (* 2 p q) (* q q))
+		   (/ count 2))
+	:else (ffib-iter (+ (* b q) (* a q) (* a p))
+			 (+ (* b p) (* a q))
+			 p
+			 q
+			 (- count 1))))
-- 
2.45.2