folder

11 files changed, 327 insertions, 0 deletions

diff --git a/coding-exercises/1/21.rkt b/coding-exercises/1/21.rkt
new file mode 100644
index 0000000..7cda52f
--- /dev/null
+++ b/coding-exercises/1/21.rkt
@@ -0,0 +1,20 @@
+#lang racket
+(require racket/pretty)
+(require sicp)
+
+(define (smallest-divisor n)
+  (find-divisor n 2))
+
+(define (find-divisor n test-divisor)
+  (cond ((> (square test-divisor) n) n)
+        ((divides? test-divisor n) test-divisor)
+        (else (find-divisor n (+ test-divisor 1)))))
+
+(define (square x) (* x x))
+
+(define (divides? a b)
+  (= (remainder b a) 0))
+
+;; (pretty-print (smallest-divisor 199))
+;; (pretty-print (smallest-divisor 1999))
+;; (pretty-print (smallest-divisor 19999))
diff --git a/coding-exercises/1/22.rkt b/coding-exercises/1/22.rkt
new file mode 100644
index 0000000..feec18b
--- /dev/null
+++ b/coding-exercises/1/22.rkt
@@ -0,0 +1,48 @@
+#lang racket
+(require racket/pretty)
+(require sicp)
+
+(define (smallest-divisor n)
+  (find-divisor n 2))
+
+(define (find-divisor n test-divisor)
+  (cond ((> (square test-divisor) n) n)
+        ((divides? test-divisor n) test-divisor)
+        (else (find-divisor n (+ test-divisor 1)))))
+
+(define (square x) (* x x))
+
+(define (divides? a b)
+  (= (remainder b a) 0))
+
+(define (prime? n)
+  (= n (smallest-divisor n)))
+
+(define (report-prime n t duration)
+  (print n)
+  (println " *** prime")
+  (println duration)
+  t)
+
+(define (start-prime-test n start-time)
+  (if (prime? n)
+    (report-prime n true (- (current-inexact-milliseconds) start-time))
+    false))
+
+(define (time-prime-test n)
+  (start-prime-test n (current-inexact-milliseconds)))
+
+(define (search-for-primes found n)
+  (cond
+    ((> found 2) "found three primes")
+    ((time-prime-test n) (search-for-primes (+ found 1) (+ n 2)))
+    (else (search-for-primes found (+ n 2)))))
+
+(println " *** search for primes")
+(search-for-primes 0 1001)
+(println " *** search for primes")
+(search-for-primes 0 10001)
+(println " *** search for primes")
+(search-for-primes 0 100001)
+(println " *** search for primes")
+(search-for-primes 0 1000001)
diff --git a/coding-exercises/1/23.rkt b/coding-exercises/1/23.rkt
new file mode 100644
index 0000000..f44c87c
--- /dev/null
+++ b/coding-exercises/1/23.rkt
@@ -0,0 +1,52 @@
+#lang racket
+(require racket/pretty)
+(require sicp)
+
+(define (next n)
+  (if (= n 2) 3 (+ n 2)))
+
+(define (find-divisor n test-divisor)
+  (cond ((> (square test-divisor) n) n)
+        ((divides? test-divisor n) test-divisor)
+        (else (find-divisor n (next test-divisor)))))
+
+
+(define (smallest-divisor n)
+  (find-divisor n 2))
+
+(define (square x) (* x x))
+
+(define (divides? a b)
+  (= (remainder b a) 0))
+
+(define (prime? n)
+  (= n (smallest-divisor n)))
+
+(define (report-prime n t duration)
+  (print n)
+  (println " *** prime")
+  (println duration)
+  t)
+
+(define (start-prime-test n start-time)
+  (if (prime? n)
+    (report-prime n true (- (current-inexact-milliseconds) start-time))
+    false))
+
+(define (time-prime-test n)
+  (start-prime-test n (current-inexact-milliseconds)))
+
+(define (search-for-primes found n)
+  (cond
+    ((> found 2) "found three primes")
+    ((time-prime-test n) (search-for-primes (+ found 1) (+ n 2)))
+    (else (search-for-primes found (+ n 2)))))
+
+(println " *** search for primes")
+(search-for-primes 0 1001)
+(println " *** search for primes")
+(search-for-primes 0 10001)
+(println " *** search for primes")
+(search-for-primes 0 100001)
+(println " *** search for primes")
+(search-for-primes 0 1000001)
diff --git a/coding-exercises/1/24.rkt b/coding-exercises/1/24.rkt
new file mode 100644
index 0000000..9dae66c
--- /dev/null
+++ b/coding-exercises/1/24.rkt
@@ -0,0 +1,70 @@
+#lang racket
+(require racket/pretty)
+(require sicp)
+
+(define (next n)
+  (if (= n 2) 3 (+ n 2)))
+
+(define (square x) (* x x))
+
+(define (divides? a b)
+  (= (remainder b a) 0))
+
+(define (find-divisor n test-divisor)
+  (cond ((> (square test-divisor) n) n)
+        ((divides? test-divisor n) test-divisor)
+        (else (find-divisor n (next test-divisor)))))
+
+(define (smallest-divisor n)
+  (find-divisor n 2))
+
+(define (prime? n)
+  (= n (smallest-divisor n)))
+
+(define (expmod base e m)
+  (cond 
+    ((= e 0) 1)
+    ((even? e)
+     (remainder (square (expmod base (/ e 2) m)) m))
+    (else
+      (remainder (* base (expmod base (- e 1) m)) m))))
+
+(define (fermat-test n)
+  (define (try-it a)
+    (= (expmod a n n) a))
+  (try-it (+ 1 (random (- n 1)))))
+
+(define (fast-prime? n times)
+  (cond 
+    ((= times 0) true)
+    ((fermat-test n) (fast-prime? n (- times 1)))
+    (else false)))
+
+(define (report-prime n t duration)
+  (print n)
+  (println " *** prime")
+  (println duration)
+  t)
+
+(define (start-prime-test n start-time)
+  (if (fast-prime? n 3)
+    (report-prime n true (- (current-inexact-milliseconds) start-time))
+    false))
+
+(define (time-prime-test n)
+  (start-prime-test n (current-inexact-milliseconds)))
+
+(define (search-for-primes found n)
+  (cond
+    ((> found 2) "found three primes")
+    ((time-prime-test n) (search-for-primes (+ found 1) (+ n 2)))
+    (else (search-for-primes found (+ n 2)))))
+
+(println " *** search for primes")
+(search-for-primes 0 1001)
+(println " *** search for primes")
+(search-for-primes 0 10001)
+(println " *** search for primes")
+(search-for-primes 0 100001)
+(println " *** search for primes")
+(search-for-primes 0 1000001)
diff --git a/coding-exercises/1/27.rkt b/coding-exercises/1/27.rkt
new file mode 100644
index 0000000..8762d6c
--- /dev/null
+++ b/coding-exercises/1/27.rkt
@@ -0,0 +1,24 @@
+#lang racket
+(require sicp)
+
+(define (square x)
+  (* x x))
+
+(define (expmod base e m)
+  (cond 
+    ((= e 0) 1)
+    ((even? e)
+     (remainder (square (expmod base (/ e 2) m)) m))
+    (else
+      (remainder (* base (expmod base (- e 1) m)) m))))
+
+(define (fermat? a n)
+  (= (expmod a n n) a))
+
+(define (all-fermat n)
+  (define (f a n)
+      (cond
+        ((= a 0) true)
+        ((fermat? (- a 1) n) (f (- a 1) n))
+        (else false)))
+  (f n n))
diff --git a/coding-exercises/1/28.rkt b/coding-exercises/1/28.rkt
new file mode 100644
index 0000000..39a10d9
--- /dev/null
+++ b/coding-exercises/1/28.rkt
@@ -0,0 +1,33 @@
+#lang racket
+(require sicp)
+
+(define (square x)
+  (* x x))
+
+(define (signal b e m x)
+  (cond
+    ((= e (- m 1)) x) ;; end result
+    ((= b (- m 1)) x) ;; base squared wil result in trivial root
+    ((= x 1) 0) ;; non-trivial root
+    (else x))) ;; no root found
+
+(define (expmod base e m)
+  (cond 
+    ((= e 0) 1)
+    ((even? e)
+     (signal base e m (remainder (square (expmod base (/ e 2) m)) m)))
+    (else
+      (remainder (* base (expmod base (- e 1) m)) m))))
+
+(define (mr a n)
+  (= (expmod a (- n 1) n) 1))
+
+(define (all-mr n)
+  (define (f a n)
+      (cond
+        ((<= a 2) true)
+        ((mr (- a 1) n) (f (- a 1) n))
+        (else false)))
+  (f n n))
+
+(all-mr 1)
diff --git a/coding-exercises/1/29.rkt b/coding-exercises/1/29.rkt
new file mode 100644
index 0000000..b0d3ab8
--- /dev/null
+++ b/coding-exercises/1/29.rkt
@@ -0,0 +1,34 @@
+#lang racket
+(require sicp)
+
+(define (id x) x)
+
+(define (sum term a next b)
+  (if (> a b)
+    0
+    (+ (term a)
+       (sum term (next a) next b))))
+
+(define (simpson f lower upper n)
+  (define (h)
+    (/ (- upper lower) n))
+  (define (term a)
+    (cond
+      ((= a 0) (f a))
+      ((= a upper) (f a))
+      ((even? a) (* 2 (f a)))
+      (else (* 4 (f a)))))
+
+  (* (/ (h) 3.0)
+     (sum term lower inc upper)))
+
+(define (cube x) (* x x x))
+(define (integral f a b dx)
+  (define (add-dx x) (+ x dx))
+  (* (sum f (+ a (/ dx 2.0)) add-dx b) dx))
+
+(integral cube 0 1 100)
+(println "")
+(simpson cube 0 1 100)
+(println "")
+(simpson cube 0 1 1000)
diff --git a/coding-exercises/1/30.rkt b/coding-exercises/1/30.rkt
new file mode 100644
index 0000000..c9bf57d
--- /dev/null
+++ b/coding-exercises/1/30.rkt
@@ -0,0 +1,4 @@
+#lang racket
+(require sicp)
+
+
diff --git a/coding-exercises/1/chapter115.rkt b/coding-exercises/1/chapter115.rkt
new file mode 100644
index 0000000..0a026c6
--- /dev/null
+++ b/coding-exercises/1/chapter115.rkt
@@ -0,0 +1,14 @@
+#lang sicp
+(define counter (box 0))
+
+(define (cube x) (* x x x))
+(define (p x) 
+  (set-box! counter (+ (unbox counter) 1))
+  (- (* 3 x) (* 4 (cube x))))
+(define (sine angle)
+  (if (not (> (abs angle) 0.1))
+    angle
+    (p (sine (/ angle 3)))))
+(sine 1250.0)
+(println "\n")
+(println (unbox counter))
diff --git a/coding-exercises/1/chapter116.rkt b/coding-exercises/1/chapter116.rkt
new file mode 100644
index 0000000..e4f1e7d
--- /dev/null
+++ b/coding-exercises/1/chapter116.rkt
@@ -0,0 +1,16 @@
+(define (square x) (* x x))
+
+(define (fast-expt b n)
+  (cond ((= n 0) 1)
+        ((even? n) (square (fast-expt b (/ n 2))))
+        (else (* b (fast-expt b (- n 1))))))
+
+(define (fie a b n)
+  (cond ((= n 0) a)
+        ((even? n) (fie a (square b) (/ n 2)))
+        (else  (fie (* a b) b (- n 1)))))
+
+(define (fast-expt b n)
+  (fie 1 b n))
+
+(fast-expt 5 5)
diff --git a/coding-exercises/1/chapter117.rkt b/coding-exercises/1/chapter117.rkt
new file mode 100644
index 0000000..4a78d54
--- /dev/null
+++ b/coding-exercises/1/chapter117.rkt
@@ -0,0 +1,12 @@
+(define (halve a) (/ a 2))
+(define (double a) (* a 2))
+
+(define (miter s a b)
+  (cond ((= b 0) s)
+        ((even? b) (miter s (double a) (halve b)))
+        (else (miter (+ s a) (double a) (halve (- b 1))))))
+
+(define (m a b)
+  (miter 0 a b))
+
+(m 3 5)