All code available on GitHub. Drawings/diagrams available here.
One thing that has made going through this book super fun so far is REPL-driven development. My current workflow uses VSCode’s Calva plugin and it is truly powerful. For instance, I can evaluate parts of an expression easily and also instrument code and do step-through debugging. I also took some time to learn about Paredit, which has made working with all those S-expressions much easier! Anyway, on to the meat of the article:
One key takeaway from §1.2 is that we must not confuse Recursive Procedures with Recursive Processes. The following exercises are an application of this concept:
;; Exercise 1.11. A function f is defined by the rule that f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n> 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.
(defn ex111-r [n]
(cond (< n 3) n
(>= n 3) (+ (ex111-r (- n 1))
(* 2 (ex111-r (- n 2)))
(* 3 (ex111-r (- n 3))))
:else (throw (new AssertionError "invalid n"))))
(ex111-r 10)
(defn ex111-i [n]
(let [iter (fn [a b c count]
(if (zero? count) c
(recur b c (+ (* 3 a) (* 2 b) c) (dec count))))]
(iter 0 1 2 (- n 2))))
(ex111-i 10)
This one uses a trick I learnt from doing 4Clojure exercises - partition 2 1 gives overlapping pairs in a list which work well for Pascal’s triangle.
;; Exercise 1.12. Write a procedure that computes elements of Pascal's triangle by means of a recursive process.
(defn pascal [n]
(let [pp (fn [i prev]
(cond (< n 0) (throw (new AssertionError "invalid n"))
(= n 1) [1]
(= n 2) [1 1]
(= i n) prev
:else (let [pairs (partition 2 1 prev)
new-inner (map #(apply + %) pairs)]
(recur (inc i) (concat [1] new-inner [1])))))]
(pp 1 [])))
(assert (= (pascal 5) [1 4 6 4 1]))
Ah yes; invariants! Designing a loop with the right invariants can often assure you of the correctness of the loop. Exercises 1.16 and 1.18 are a great example of this idea.
;; Exercise 1.16 Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt.
(defn fast-expt [b n]
(cond (zero? n) 1
(even? n) (* (fast-expt b (/ n 2)) (fast-expt b (/ n 2)))
:else (* b (fast-expt b (- n 1)))))
(fast-expt 2 5)
(defn fast-expt-iter [b n]
;; a﹒b^n is invariant
(let [f (fn [b n a]
(cond
(= n 0) a
(even? n) (recur (* b b) (/ n 2) a)
:else (recur b (dec n) (* b a))))]
(f b n 1)))
(fast-expt-iter 2 5)
;; Exercise 1.18. Using the results of exercises 1.16 and 1.17, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.40
;; After thinking of the invariant, it comes naturally.
(defn fast-mult-iter [a b n]
;; a﹒b + n is invariant
(let [double (fn [a] (* a 2))
halve (fn [a] (/ a 2))]
(cond
(zero? b) n
(even? b) (recur (double a) (halve b) n)
:else (recur a (dec b) (+ n a)))))
(fast-mult-iter 11 3 0)
A logarithmic algorithm for computing Fibonacci numbers, super cool! My derivation of the transform is here: https://notability.com/n/~S4C78hC359sd2EDdHWkW.
;; Exercise 1.19
(defn fib-iter [a b p q count]
(cond (= count 0) b
(even? count) (recur
a
b
(+ (* q q) (* p p))
(+ (* q q) (* 2 p q))
(/ count 2))
:else (recur (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(dec count))))
(fib-iter 1 0 0 1 10)
For the following exercises, we use Clojure’s built-in time function, which prints out the runtime of the expression as a side-effect.
;; Exercise 1.21. Use the smallest-divisor procedure to find the smallest divisor of each of the following numbers: 199, 1999, 19999.
(defn smallest-divisor-slow [n]
(first (filter #(zero? (mod n %))
(range 2 (inc n)))))
(defn smallest-divisor [n]
(first (filter #(zero? (mod n %))
(concat '(2) (range 3 (inc n) 2)))))
(smallest-divisor 199) ;; 199
(smallest-divisor 1999) ;; 1999
(smallest-divisor 19999) ;; 7
;; Ex 1.23
(defn prime-slow? [n] (= n (smallest-divisor-slow n)))
(defn prime? [n] (= n (smallest-divisor n)))
(time (dotimes [n 10] (prime? 1000037))) ;; 555 ms
(time (dotimes [n 10] (prime-slow? 1000037))) ;; 1073 ms
;; 2x speedup, as expected!
Here we apply another trick to measure the runtime of the code - we use doall since Clojure’s sequences are lazy and we want to force evaluation.
;; Ex 1.21
(defn fermat-test [n]
(let [expmod (fn expmod [base exp m]
(cond (zero? exp) 1
(even? exp) (let [x (expmod base (/ exp 2) m)] (mod (* x x) m))
:else (mod (* base (expmod base (dec exp) m)) m)))
try-it (fn [a] (= (expmod a n n) a))]
(try-it (+ 1 (rand-int (dec n))))))
;; Uses the mod property
(fermat-test 19999)
(defn fast-prime? [n times]
(cond (zero? times) true
(fermat-test n) (fast-prime? n (- times 1))
:else false))
;; Ex 1.22
(defn search-for-primes [lower-bound num-primes-wanted]
(take num-primes-wanted
(filter #(fast-prime? % 8)
(filter odd? (range lower-bound (java.lang.Integer/MAX_VALUE))))))
(defn search-for-primes-slow [lower-bound num-primes-wanted]
(take num-primes-wanted
(filter prime?
(filter odd? (range lower-bound (java.lang.Integer/MAX_VALUE))))))
;; This is approximately O(sqrt(n)) growth.
(time (doall (search-for-primes-slow 1000 3))) ;;/ (1009 1013 1019) 0.6 msecs"
(time (doall (search-for-primes-slow 10000 3))) ;; (10007 10009 10037) 4 msecs
(time (doall (search-for-primes-slow 100000 3))) ;; (100003 100019 100043) 30 msecs"
(time (doall (search-for-primes-slow 1000000 3))) ;; (1000003 1000033 1000037) 224 ms
;; Ex 1.24
;; This is approximately O(log(n)) growth and demonstrates the power of logarithmic runtimes - a multiplication of the input's cardinality results in an additive runtime increase.
(trace/trace (time (doall (search-for-primes 1000 3)))) ;; (1009 1013 1019) 0.24 msecs"
(time (doall (search-for-primes 10000 3))) ;; (10007 10009 10037) 0.50 msecs
(time (doall (search-for-primes 100000 3))) ;; (100003 100019 100043) 0.57 msecs"
(time (doall (search-for-primes 1000000 3))) ;; (1000003 1000033 1000037) 0.6 msecs"
;; Exercise 1.25. Alyssa P. Hacker complains that we went to a lot of extra work in writing expmod. After all, she says, since we already know how to compute exponentials, we could have simply written:
;; (define (expmod base exp m)
;; (remainder (fast-expt base exp) m))
;; Theoretically (in terms of math), it would work. Computationally it fails since the numbers (without the intermediate mods) are too large and either overflow or take too long.
;; Exercise 1.26
;; Previously, the process was linear recursive and you halved the search space on each level (the /2). Now, every time you halve the seach space, you make 2 recursive calls at the same level. So the runtime is now O(N) instead of O(log N).s
;; Exercise 1.28
;; Proof that if there is nontrivial square root of n it is not prime
;; https://crypto.stanford.edu/pbc/notes/numbertheory/poly.html
(defn miller-rabin [n]
(let [expmod (fn expmod [base exp m]
(cond (zero? exp) 1
(even? exp) (let [x (expmod base (/ exp 2) m)
sq (mod (* x x) m)]
(if (and (not= x 1)
(not= x (dec m))
(= sq 1)) 0
sq))
:else (mod (* base (expmod base (dec exp) m)) m)))
try-it (fn [a] (= (expmod a (dec n) n) 1))]
(try-it 3)
;; (every? true? (map try-it (range 2 n)))
))