From b18a28271ccd7ec4467f219204c31a53976c368d Mon Sep 17 00:00:00 2001 From: Ramakrishnan Muthukrishnan 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