Saturday, August 24, 2019

SICP in Clojure: Chapter 1, Exercise 19

This is my Clojure solution to Chapter 1, Exercise 19:

(ns sicp.ch1.ex19
  (:require [sicp.ch1.ex13 :as sicp-ch1-ex13]))

(defn fast-fib-iter
  ([n]
   (fast-fib-iter 1 0 0 1 n))
  ([a b p q i]
   (cond (zero? i) b
         (even? i) (fast-fib-iter a
                                  b
                                  (+ (* p p) (* q q)) ; compute p'
                                  (+ (* q q) (* 2 p q)) ; compute q'
                                  (/ i 2))
         :else (fast-fib-iter (+ (* b q) (* a q) (* a p))
                              (+ (* b p) (* a q))
                              p
                              q
                              (dec i)))))

(fast-fib-iter 0) ; => 0

(fast-fib-iter 1) ; => 1

(fast-fib-iter 2) ; => 1

(fast-fib-iter 3) ; => 2

(fast-fib-iter 4) ; => 3

(fast-fib-iter 5) ; => 5

(every? #(= (sicp-ch1-ex13/fib %) (fast-fib-iter %))
        (range 10)) ; => true


No comments: