SICP in Clojure: Chapter 1, Exercise 20

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

(ns sicp.ch1.ex20)

(defn gcd-pseudo-normal
  [a b]
  (if-not (and (ifn? a) (ifn? b))
    (gcd-pseudo-normal #(identity a) #(identity b))
    (if (zero? (b))
      (a)
      (gcd-pseudo-normal b #(do
                              (println "Computing remainder")
                              (rem (a) (b)))))))

(defn gcd
  [a b]
  (if (zero? b)
    a
    (gcd b (do
             (println "Computing remainder")
             (rem a b)))))

(gcd-pseudo-normal (constantly 206)
                   (constantly 40)) ; => 18 remainder computations

(gcd 206 40) ; => 4 remainder computations

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

SICP in Clojure: Chapter 1, Exercise 18

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

(ns sicp.ch1.ex18
  (:require [sicp.ch1.ex17 :as sicp-ch1-ex17]))

(defn fast-multiply-iter
  ([b n]
   (fast-multiply-iter 0 b n))
  ([a b n]
   (cond (zero? n) a
         (even? n) (fast-multiply-iter a (sicp-ch1-ex17/double-it b)
                                       (sicp-ch1-ex17/halve-it n))
         :else (fast-multiply-iter (+ a b) b (dec n)))))

(fast-multiply-iter 2 8) ; => 16

(fast-multiply-iter 2 9) ; => 18

(every? #(= (sicp-ch1-ex17/fast-multiply 2 %)
            (fast-multiply-iter 2 %))
        (range 10)) ; => true

SICP in Clojure: Chapter 1, Exercise 17

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

(ns sicp.ch1.ex17)

(defn multiply
  [a b]
  (if (zero? b)
    0
    (+ a (multiply a (dec b)))))

(multiply 5 8) ; => 40

(defn double-it
  [n]
  (* 2 n))

(defn halve-it
  [n]
  (/ n 2))

(defn fast-multiply
  [a b]
  (cond (zero? b) 0
        (= b 1) a
        (even? b) (double-it (fast-multiply a (halve-it b)))
        :else (+ a (fast-multiply a (dec b)))))

(fast-multiply 5 8) ; => 40

(every? #(= (apply multiply %) (apply fast-multiply %))
        (for [i (range 10) j (range 10)] [i j])) ; => true

SICP in Clojure: Chapter 1, Exercise 16

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

(ns sicp.ch1.ex16)

(defn square
  [n]
  (* n n))

(defn fast-expt
  [b n]
  (cond (zero? n) 1
        (even? n) (square (fast-expt b (/ n 2)))
        :else (* b (fast-expt b (dec n)))))

(defn fast-expt-iter
  ([b n]
   (fast-expt-iter 1 b n))
  ([a b n]
   (cond (zero? n) a
         (even? n) (fast-expt-iter a (square b) (/ n 2))
         :else (fast-expt-iter (* a b) b (dec n)))))

(fast-expt 2 8) ; => 256

(fast-expt 2 9) ; => 512

(every? #(= (fast-expt 2 %) (fast-expt-iter 2 %))
        (range 10)) ; => true

SICP in Clojure: Chapter 1, Exercise 15

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

(ns sicp.ch1.ex15)

(defn cube
  [x]
  (* x x x))

(defn p
  [x]
  (- (* 3 x) (* 4 (cube x))))

(defn sine
  [angle]
  (if (not (> (Math/abs angle) 0.1))
    angle
    (p (sine (/ angle 3.0)))))

(sine 12.15) ; => -0.39 -- p is applied 5 times

;; if a is the angle then the space complexity (or the maximum height
;; of the tree) is O(log a) else the time complexity (or the number of
;; nodes in the tree) is also O(log a)