SICP in Clojure: Chapter 1, Exercise 25

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

(ns sicp.ch1.ex25
  (:require [sicp.ch1.ex22 :as sicp-ch1-ex22]
            [sicp.ch1.ex24 :as sicp-ch1-ex24]))

(defn square ; supports arbitrary precision
  [n]
  (*' n n))

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

(defn expmod
  [base exp m]
  (rem (fast-expt base exp) m))

(defn fermat-test
  [n]
  (letfn [(try-it [a]
            (= (expmod a n n) a))]
    (try-it (inc (rand-int (dec n))))))

(defn fast-prime?
  [n times]
  (cond (zero? times)   true
        (fermat-test n) (fast-prime? n (dec times))
        :else           false))

(defn start-prime-test
  [n start-time]
  (let [p (fast-prime? n 10)]
    (when p
      (sicp-ch1-ex22/report-prime n (- (sicp-ch1-ex22/runtime)
                                       start-time)))
    p))

(defn timed-prime-test
  [n]
  (start-prime-test n (sicp-ch1-ex22/runtime)))

(def primes [1009 1013 1019 10007 10009 10037 100003 100019 100043
             1000003 1000033 1000037])

(map sicp-ch1-ex24/timed-prime-test primes)

(map timed-prime-test (take 6 primes))

(def old-times [50052 44905 62564 53861 82539 51227 59000 60004 59868
                66958 66804 61172])

(def new-times [2082324 667264 671594 29729704 25477811 25314029])

(map #(double (/ %1 %2)) old-times new-times) ; 0.0018--0.09x disimprovement

SICP in Clojure: Chapter 1, Exercise 24

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

(ns sicp.ch1.ex24
  (:require [sicp.ch1.ex16 :as sicp-ch1-ex16]
            [sicp.ch1.ex22 :as sicp-ch1-ex22]))

(defn expmod
  [base exp m]
  (cond (zero? exp) 1
        (even? exp) (rem (sicp-ch1-ex16/square (expmod base
                                                       (/ exp 2)
                                                       m))
                         m)
        :else       (rem (* base (expmod base (dec exp) m))
                         m)))

(defn fermat-test
  [n]
  (letfn [(try-it [a]
            (= (expmod a n n) a))]
    (try-it (inc (rand-int (dec n))))))

(defn fast-prime?
  [n times]
  (cond (zero? times)   true
        (fermat-test n) (fast-prime? n (dec times))
        :else           false))

(defn start-prime-test
  [n start-time]
  (let [p (fast-prime? n 10)]
    (when p
      (sicp-ch1-ex22/report-prime n (- (sicp-ch1-ex22/runtime)
                                       start-time)))
    p))

(defn timed-prime-test
  [n]
  (start-prime-test n (sicp-ch1-ex22/runtime)))

(def primes [1009 1013 1019 10007 10009 10037 100003 100019 100043
             1000003 1000033 1000037])

(map sicp-ch1-ex22/timed-prime-test primes)

(map timed-prime-test primes)

(def old-times [131134 49417 48302 153392 159432 167507 523204 498113
                357480 815095 580023 253359])

(def new-times [461622 142283 171243 156552 274436 89991 78386 77681
                74216 99555 79155 85534])

(map #(double (/ %1 %2)) old-times new-times) ; 0.28--8.19x (dis)improvement

SICP in Clojure: Chapter 1, Exercise 23

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

(ns sicp.ch1.ex23
  (:require [sicp.ch1.ex16 :as sicp-ch1-ex16]
            [sicp.ch1.ex22 :as sicp-ch1-ex22]))

(defn next-divisor
  [test-divisor]
  (cond (= 2 test-divisor) 3
        :else              (+ 2 test-divisor)))

(defn find-divisor
  [n test-divisor]
  (cond (> (sicp-ch1-ex16/square
            test-divisor) n)       n
        (zero? (rem n
                    test-divisor)) test-divisor
        :else                      (find-divisor n
                                                 (next-divisor
                                                  test-divisor))))

(defn smallest-divisor
  [n]
  (find-divisor n 2))

(defn prime?
  [n]
  (= n (smallest-divisor n)))

(defn start-prime-test
  [n start-time]
  (let [p (prime? n)]
    (when p
      (sicp-ch1-ex22/report-prime n (- (sicp-ch1-ex22/runtime)
                                       start-time)))
    p))

(defn timed-prime-test
  [n]
  (start-prime-test n (sicp-ch1-ex22/runtime)))

(def primes [1009 1013 1019 10007 10009 10037 100003 100019 100043
             1000003 1000033 1000037])

(map sicp-ch1-ex22/timed-prime-test primes)

(map timed-prime-test primes)

(def old-times [14074 7304 6946 18528 18431 17979 56382 54608 54627
                167110 166381 166168])

(def new-times [9383 5812 5227 13593 14283 13093 38618 38156 38717
                119032 118839 118661])

(map #(double (/ %1 %2)) old-times new-times) ; 1.2--1.5x improvement

SICP in Clojure: Chapter 1, Exercise 22

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

(ns sicp.ch1.ex22

  (:require [sicp.ch1.ex21 :as sicp-ch1-ex21]))

(defn prime?

  [n]

  (= n (sicp-ch1-ex21/smallest-divisor n)))

(defn report-prime

  [n elapsed-time]

  (println "* " n elapsed-time))

(defn runtime

  []

  (System/nanoTime))

(defn start-prime-test

  [n start-time]

  (let [p (prime? n)]

    (when p

      (report-prime n (- (runtime) start-time)))

    p))

(defn timed-prime-test

  [n]

  (start-prime-test n (runtime)))

(defn search-for-primes

  [start cnt]

  (reduce

   (fn [acc x]

     (if (= cnt (count acc))

       (reduced acc)

       (if (timed-prime-test x)

         (conj acc x)

         acc)))

   []

   (filter #(= 1 (rem % 2))

           (iterate inc start))))

(search-for-primes 1000 3) ; ~5,000ns

(search-for-primes 10000 3) ; ~15,000ns

(search-for-primes 100000 3) ; ~50,000ns

(search-for-primes 1000000 3) ; ~160,000ns

SICP in Clojure: Chapter 1, Exercise 21

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

(ns sicp.ch1.ex21
  (:require [sicp.ch1.ex16 :as sicp-ch1-ex16]))

(defn find-divisor
  [n test-divisor]
  (cond (> (sicp-ch1-ex16/square test-divisor) n) n
        (zero? (rem n test-divisor)) test-divisor
        :else (find-divisor n (inc test-divisor))))

(defn smallest-divisor
  [n]
  (find-divisor n 2))

(smallest-divisor 199) ; => 199

(smallest-divisor 1999) ; => 1999

(smallest-divisor 19999) ; => 7