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
(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
No comments:
Post a Comment