Tuesday, September 10, 2019

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

No comments: