]> git.rkrishnan.org Git - sicp.git/blob - src/sicp/ex1_28.clj
rewrite `quote->cons' using `match'.
[sicp.git] / src / sicp / ex1_28.clj
1 (ns sicp.ex1_28
2   (:use [sicp utils]
3         [clojure.contrib trace test-is]))
4
5
6 ;;; exercise 1.28
7 (defn expmod2 [base exp m]
8   (cond (= exp 0) 1
9         (even? exp) (square-test (expmod2 base (/ exp 2) m) m)
10         :else (rem (* base (expmod2 base (dec exp) m))
11                    m)))
12
13 (defn square-test [x m]
14   (if (and (not (or (= x 1) (= x (- m 1))))
15            (= (rem (square x) m) 1))
16     0
17     (rem (square x) m)))
18
19 (defn miller-rabin-test [n]
20   (try-it (+ 2 (rand-int (- n 2)))
21           n))
22
23 (defn try-it [a n]
24   (= (expmod2 a (- n 1) n) 1))
25
26 (comment
27   "If the random number generated (a) is 1, then this returns false
28    positives. So generate random numbers between 2 and n-1. (is this
29    assumption correct?) "
30 )