diff options
Diffstat (limited to 'chap1/part2.rkt')
| -rw-r--r-- | chap1/part2.rkt | 856 |
1 files changed, 856 insertions, 0 deletions
diff --git a/chap1/part2.rkt b/chap1/part2.rkt new file mode 100644 index 0000000..d749de9 --- /dev/null +++ b/chap1/part2.rkt @@ -0,0 +1,856 @@ +#lang sicp + +;; Chapter 1 +;; Building Abstractions with Procedures + +;; 1.2 +;; Procedures and the Processes They Generate + +#| 1.9 |# + +;; recursive process: +#| (define (+ a b) |# +#| (if (= a 0) |# +#| b |# +#| (inc (+ (dec a) b)))) |# + +;; iterative process: +#| (define (+ a b) |# +#| (if (= a 0) |# +#| b |# +#| (+ (dec a) (inc b)))) |# + +#| 1.10 |# + +(#%provide A) +(define (A x y) + (cond + ((= y 0) 0) + ((= x 0) (* 2 y)) + ((= y 1) 2) + (else + (A + (- x 1) + (A x (- y 1)))))) + +#| (A 1 10) |# +#| (A 0 (A 1 9)) |# +#| (A 0 (A 0 (A 1 8))) |# +#| (A 0 (A 0 (A 0 (A 1 7)))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 1 6))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 1 (A 1 5)))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3)))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1)))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 2)))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 4))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 8))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16)))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 16)))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 32))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 32))))) |# +#| (A 0 (A 0 (A 0 (A 0 64)))) |# +#| (A 0 (A 0 (A 0 (* 2 64)))) |# +#| (A 0 (A 0 (A 0 128))) |# +#| (A 0 (A 0 (* 2 128))) |# +#| (A 0 (A 0 256)) |# +#| (A 0 (* 2 256)) |# +#| (A 0 512) |# +#| (* 2 512) |# +#| 1024 |# + +#| (A 2 4) |# +#| (A 1 (A 2 3)) |# +#| (A 1 (A 1 (A 2 2))) |# +#| (A 1 (A 1 (A 1 (A 2 1)))) |# +#| (A 1 (A 1 (A 1 2))) |# +#| (A 1 (A 1 (A 0 (A 1 1)))) |# +#| (A 1 (A 1 (A 0 2))) |# +#| (A 1 (A 1 (* 2 2))) |# +#| (A 1 (A 1 4)) |# +#| (A 1 (A 0 (A 1 3))) |# +#| (A 1 (A 0 (A 0 (A 1 2)))) |# +#| (A 1 (A 0 (A 0 (A 0 (A 1 1))))) |# +#| (A 1 (A 0 (A 0 (A 0 2)))) |# +#| (A 1 (A 0 (A 0 (* 2 2)))) |# +#| (A 1 (A 0 (A 0 4))) |# +#| (A 1 (A 0 (* 2 4))) |# +#| (A 1 (A 0 8)) |# +#| (A 1 (* 2 8)) |# +#| (A 1 16) |# +#| (A 0 (A 1 15)) |# +#| (A 0 (A 0 (A 1 14))) |# +#| (A 0 (A 0 (A 0 (A 1 13)))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 1 12))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 11)))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 10))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 9)))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 8))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 7)))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 6))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 (A 1 5)))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3)))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2))))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1)))))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2))))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 2)))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 4))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 8))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16)))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 16)))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 64)))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 64)))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 128))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 128))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 256)))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 256)))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 512))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 512))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1024)))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 1024)))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 2048))))) |# +#| (A 0 (A 0 (A 0 (A 0 (* 2 2048))))) |# +#| (A 0 (A 0 (A 0 (A 0 4096)))) |# +#| (A 0 (A 0 (A 0 (* 2 4096)))) |# +#| (A 0 (A 0 (A 0 8182))) |# +#| (A 0 (A 0 (* 2 8182))) |# +#| (A 0 (A 0 16364)) |# +#| (A 0 (* 2 16364)) |# +#| (A 0 32768) |# +#| (* 2 32768) |# +#| 65536 |# + + +#| (A 3 3) |# +#| (A 2 (A 3 2)) |# +#| (A 2 (A 2 (A 3 1))) |# +#| (A 2 (A 2 2)) |# +#| (A 2 (A 1 (A 2 1))) |# +#| (A 2 (A 1 2)) |# +#| (A 2 (A 0 (A 1 1))) |# +#| (A 2 (A 0 2)) |# +#| (A 2 (* 2 2)) |# +#| (A 2 4) |# +#| (A 1 (A 2 3)) |# +#| (A 1 (A 1 (A 2 2))) |# +#| (A 1 (A 1 (A 1 (A 2 1)))) |# +#| (A 1 (A 1 (A 1 2))) |# +#| (A 1 (A 1 (A 0 (A 1 1)))) |# +#| (A 1 (A 1 (A 0 2))) |# +#| (A 1 (A 1 (* 2 2))) |# +#| (A 1 (A 1 4)) |# +#| (A 1 (A 0 (A 1 3))) |# +#| (A 1 (A 0 (A 0 (A 1 2)))) |# +#| (A 1 (A 0 (A 0 (A 0 (A 1 1))))) |# +#| (A 1 (A 0 (A 0 (A 0 2)))) |# +#| (A 1 (A 0 (A 0 (* 2 2)))) |# +#| (A 1 (A 0 (A 0 4))) |# +#| (A 1 (A 0 (* 2 4))) |# +#| (A 1 (A 0 8)) |# +#| (A 1 (* 2 8)) |# +#| (A 1 16) |# +#| (A 0 (A 1 15)) |# +#| (A 0 (A 0 (A 1 14))) |# +#| (A 0 (A 0 (A 0 (A 1 13)))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 1 12))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 11)))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 10))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 9)))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 8))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 7)))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 6))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 (A 1 5)))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3)))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2))))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1)))))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2))))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 2)))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 4))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 8))))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16)))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 16)))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32))))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 64)))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 64)))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 128))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 128))))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 256)))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 256)))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 512))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 512))))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1024)))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 (* 2 1024)))))) |# +#| (A 0 (A 0 (A 0 (A 0 (A 0 2048))))) |# +#| (A 0 (A 0 (A 0 (A 0 (* 2 2048))))) |# +#| (A 0 (A 0 (A 0 (A 0 4096)))) |# +#| (A 0 (A 0 (A 0 (* 2 4096)))) |# +#| (A 0 (A 0 (A 0 8182))) |# +#| (A 0 (A 0 (* 2 8182))) |# +#| (A 0 (A 0 16364)) |# +#| (A 0 (* 2 16364)) |# +#| (A 0 32768) |# +#| (* 2 32768) |# +#| 65536 |# + +;; f(n) = 2n +(define (f n) (A 0 n)) + +;; g(n) = 2^n +(define (g n) (A 1 n)) + +;; h(n) = 2^(2^... n times ...(2^2)...) +(define (h n) (A 2 n)) + +;; k(n) = 5n^2 +(define (k n) (* 5 n n)) + +(#%provide count-change) +(define (count-change amount) + (cc amount 5)) + +(define (cc amount kinds-of-coins) + (cond + ((= amount 0) 1) + ((or (< amount 0) (= kinds-of-coins 0)) 0) + (else + (+ + (cc amount (- kinds-of-coins 1)) + (cc + (- amount (first-denomination kinds-of-coins)) + kinds-of-coins))))) + +(define (first-denomination kinds-of-coins) + (cond + ((= kinds-of-coins 1) 1) + ((= kinds-of-coins 2) 5) + ((= kinds-of-coins 3) 10) + ((= kinds-of-coins 4) 25) + ((= kinds-of-coins 5) 50))) + +#| 1.11 |# + +(#%provide f-rec) +(define (f-rec n) + (cond + ((< n 3) n) + (else + (+ + (f-rec (- n 1)) + (* 2 (f-rec (- n 2))) + (* 3 (f-rec (- n 3))))))) + +(#%provide f-iter) +(define (f-iter n) + (f-iter- 2 1 0 n)) + +(define (f-iter- a b c i) + (if (= i 0) + c + (f-iter- + (+ a (* 2 b) (* 3 c)) + a + b + (- i 1)))) + +#| 1.12 |# + +(#%provide pascal) +(define (pascal row elem) + (cond + ((> elem row) 0) + ((= elem 0) 1) + (else + (+ + (pascal (- row 1) (- elem 1)) + (pascal (- row 1) elem))))) + +#| 1.13 |# + +;; phi = (1 + sqrt(5)) / 2 +;; psi = (1 - sqrt(5)) / 2 + +;; note that: +;; phi^2 = phi + 1, and +;; psi^2 = psi + 1 + +;; Proof by induction that Fib(n) = (phi^n - psi^n) / sqrt(5) + +;; Base cases: +;; Fib(0) = 0 = (phi^0 - psi^0) / sqrt(5) +;; Fib(1) = 1 = = (((1 + sqrt(5)) - (1 - sqrt(5))) / 2) / sqrt(5) +;; = (phi^1 - psi^1) / sqrt(5) + +;; Inductive case: + +;; Suppose +;; Fib(n-2) = (phi^(n-2) - psi^(n-2)) / sqrt(5), and +;; Fib(n-1) = (phi^(n-1) - psi^(n-1)) / sqrt(5), and + +;; Then +;; Fib(n) = Fib(n-1) + Fib(n - 2) +;; = (phi^(n-1) - psi^(n-1) + phi^(n-2) - psi^(n-2)) / sqrt(5) +;; = (phi^(n-1) + phi^(n-2) - psi(^n-1) - psi^(n-2)) / sqrt(5) +;; = ((phi + 1)phi^(n-2) - (psi + 1)psi^(n-2)) / sqrt(5) +;; = ((phi^2)phi^(n-2) - (psi^2)psi^(n-2)) / sqrt(5) +;; = (phi^n - psi^n) / sqrt(5) + +;; For all n, psi^n / sqrt(5) < 1/2. So Fib(n) is the closest integer to phi^n / sqrt(5) + + +#| 1.14 |# + +#| The process generated by (count-change 11): |# + +#| - cc 11 5 |# +#| | - cc -39 5 |# +#| | - cc 11 4 |# +#| | - cc -14 4 |# +#| | - cc 11 3 |# +#| | - cc 11 2 |# +#| | | - cc 11 1 |# +#| | | | - cc 11 0 |# +#| | | | - cc 10 1 |# +#| | | | - cc 10 0 |# +#| | | | - cc 9 1 |# +#| | | | - cc 9 0 |# +#| | | | - cc 8 1 |# +#| | | | - cc 8 0 |# +#| | | | - cc 7 1 |# +#| | | | - cc 7 0 |# +#| | | | - cc 6 1 |# +#| | | | - cc 6 0 |# +#| | | | - cc 5 1 |# +#| | | | - cc 5 0 |# +#| | | | - cc 4 1 |# +#| | | | - cc 4 0 |# +#| | | | - cc 3 1 |# +#| | | | - cc 3 0 |# +#| | | | - cc 2 1 |# +#| | | | - cc 2 0 |# +#| | | | - cc 1 1 |# +#| | | | - cc 1 0 |# +#| | | | - cc 0 1 |# +#| | | - cc 6 2 |# +#| | | - cc 6 1 |# +#| | | | - cc 6 0 |# +#| | | | - cc 5 1 |# +#| | | | - cc 5 0 |# +#| | | | - cc 4 1 |# +#| | | | - cc 4 0 |# +#| | | | - cc 3 1 |# +#| | | | - cc 3 0 |# +#| | | | - cc 2 1 |# +#| | | | - cc 2 0 |# +#| | | - cc 1 1 |# +#| | | | - cc 1 0 |# +#| | | | - cc 0 1 |# +#| | | - cc 1 2 |# +#| | | - cc 1 1 |# +#| | | | - cc 1 0 |# +#| | | | - cc 0 1 |# +#| | | - cc -4 2 |# +#| | - cc 1 3 |# +#| | - cc 1 2 |# +#| | | - cc 1 1 |# +#| | | | - cc 1 0 |# +#| | | | - cc 0 1 |# +#| | | - cc -4 2 |# +#| | - cc -9 3 |# + +#| count-change is Theta(n) in space (max depth of tree) |# +#| count-change is Theta(e^n) in time (number of nodes in tree) |# + +#| 1.15 |# + +(#%provide sine) +(define (sine ang) + (define (p x) (- (* 3 x) (* 4 (cube x)))) + (if (not (> (abs ang) 0.1)) + ang + (p (sine (/ ang 3.0))))) + +#| sine 12.15 |# +#| p (sine 4.05) |# +#| p (p (sine 1.35)) |# +#| p (p (p (sine 0.45))) |# +#| p (p (p (p (sine 0.15)))) |# +#| p (p (p (p (p (sine 0.05))))) |# +#| p (p (p (p (p 0.05)))) |# + +#| p is called 5 times |# + +#| The process generated by sine is recursive |# +#| Order of growth in space: Theta(log_3(n)) |# +#| Order of growth in time: Theta(log_3(n)) |# + +(#%provide expt-rec) +(define (expt-rec b n) + (if (= n 0) + 1 + (* b (expt-rec b (- n 1))))) + +(#%provide expt-iter) +(define (expt-iter b n) + (expt-iter- b n 1)) + +(define (expt-iter- b i prod) + (if (= i 0) + prod + (expt-iter- + b + (- i 1) + (* b prod)))) + +(define (even-? k) (= (remainder k 2) 0)) + +(#%provide fast-expt-rec) +(define (fast-expt-rec b n) + (cond + ((= n 0) 1) + ((even-? n) (square (fast-expt-rec b (/ n 2)))) + (else (* b (fast-expt-rec b (- n 1)))))) + +#| 1.16 |# + +(#%provide fast-expt-iter) +(define (fast-expt-iter b n) + (fast-expt-iter- 1 b n)) + +(define (fast-expt-iter- a b n) + (cond + ((= n 0) a) + ((even-? n) (fast-expt-iter- a (square b) (/ n 2))) + (else (fast-expt-iter- (* a b) b (- n 1))))) + +(#%provide mult) +(define (mult a b) + (if (= b 0) + 0 + (+ a (mult a (- b 1))))) + +#| 1.17 |# + +(define (double x) (+ x x)) +(define (halve x) (/ x 2)) + +(#%provide fast-times-rec) +(define (fast-times-rec a b) + (cond + ((= b 0) 0) + ((even-? b) (double (fast-times-rec a (halve b)))) + (else (+ a (fast-times-rec a (- b 1)))))) + +#| 1.18 |# + +(#%provide fast-times-iter) +(define (fast-times-iter a b) + (fast-times-iter- 0 a b)) + +(define (fast-times-iter- res a b) + (cond + ((= b 0) res) + ((even-? b) (fast-times-iter- res (double a) (halve b))) + (else (fast-times-iter- (+ res a) a (- b 1))))) + +#| 1.19 |# + +;; T +;; a <- a + b +;; b <- a + +;; Tpq +;; a <- bq + aq + ap +;; b <- bp + aq + +;; Tpq^2 +;; a <- (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p +;; b <- (bp + aq)p + (bq + aq + ap)q + +;; a <- b(2pq + qq) + a(2pq + qq) + a(pp + qq) +;; b <- b(pp + qq) + a(2qp + qq) + +;; p' = pp + qq +;; q' = 2pq + qq + +(#%provide fib) +(define (fib n) + (fib-iter 1 0 0 1 n)) + +(define (fib-iter a b p q i) + (cond + ((= i 0) b) + ((even-? i) + (fib-iter + a + b + (+ (square p) (square q)) + (+ (* 2 p q) (square q)) + (/ i 2))) + (else + (fib-iter + (+ (* b q) (* a q) (* a p)) + (+ (* b p) (* a q)) + p + q + (- i 1))))) + +(#%provide fib-slow) +(define (fib-slow n) + (cond + ((= n 0) 0) + ((= n 1) 1) + (else (+ (fib (- n 1)) (fib (- n 2)))))) + +#| 1.20 |# + +(#%provide gcd-) +(define (gcd- a b) + (if (= b 0) + a + (gcd- b (remainder a b)))) + +;; Process generated by normal order evaluation + +#| (gcd- 206 40) |# +#| (if (= 40 0) 206 (gcd- 40 (rem 206 40))) |# +#| (gcd- 40 (rem 206 40)) |# +#| (if (= (rem 206 40) 0) 40 (gcd- b (rem 40 (rem 206 40)))) ; one call |# +#| (if (= 6 0) 40 (gcd- (rem 206 40) (rem 40 (rem 206 40)))) |# +#| (gcd- (rem 206 40) (rem 40 (rem 206 40))) |# +#| (if (= (rem 40 (rem 206 40)) 0) ... (gcd- (rem 40 (rem 206 40)) (rem (rem 206 40) (rem 40 (rem 206 40))))) ; one call |# +#| (if (= (rem 40 6) 0) ... (gcd- (rem 40 (rem 206 40)) (rem (rem 206 40) (rem 40 (rem 206 40))))) ; one call |# +#| (if (= 4 0) ... (gcd- (rem 40 (rem 206 40)) (rem (rem 206 40) (rem 40 (rem 206 40))))) |# +#| (gcd- (rem 40 (rem 206 40)) (rem (rem 206 40) (rem 40 (rem 206 40)))) |# +#| (if (= (rem (rem 206 40) (rem 40 (rem 206 40))) 0) ... (gcd- (rem (rem 206 40) (rem 40 (rem 206 40))) ...)) ; one call |# +#| (if (= (rem 6 (rem 40 (rem 206 40))) 0) ... (gcd- (rem (rem 206 40) (rem 40 (rem 206 40))) ...)) ; one call |# +#| (if (= (rem 6 (rem 40 6)) 0) ... (gcd- (rem (rem 206 40) (rem 40 (rem 206 40))) ...)) ; one call |# +#| (if (= (rem 6 4) 0) ... (gcd- (rem (rem 206 40) (rem 40 (rem 206 40))) ...)) ; one call |# +#| (if (= 2 0) ... (gcd- (rem (rem 206 40) (rem 40 (rem 206 40))) ...)) |# +#| (gcd- (rem (rem 206 40) (rem 40 (rem 206 40))) (rem (rem 40 (rem 206 40)) ...)) |# +#| (if (= (rem (rem 40 (rem 206 40)) (rem (rem 206 40) (rem 40 (rem 206 40)))) 0) (rem (rem 206 40) ...) ...) ; one call |# +#| (if (= (rem (rem 40 6) (rem (rem 206 40) (rem 40 (rem 206 40)))) 0) (rem (rem 206 40) ...) ...) ; one call |# +#| (if (= (rem 4 (rem (rem 206 40) (rem 40 (rem 206 40)))) 0) (rem (rem 206 40) (rem 40 (rem 206 40))) ...) ; one call |# +#| (if (= (rem 4 (rem 6 (rem 40 (rem 206 40)))) 0) (rem (rem 206 40) (rem 40 (rem 206 40))) ...) ; one call |# +#| (if (= (rem 4 (rem 6 (rem 40 6))) 0) (rem (rem 206 40) (rem 40 (rem 206 40))) ...) ; one call |# +#| (if (= (rem 4 (rem 6 4)) 0) (rem (rem 206 40) (rem 40 (rem 206 40))) ...) ; one call |# +#| (if (= (rem 4 2) 0) (rem (rem 206 40) (rem 40 (rem 206 40))) ...) ; one call |# +#| (if (= 0 0) (rem (rem 206 40) (rem 40 (rem 206 40))) ...) |# +#| (rem (rem 206 40) (rem 40 (rem 206 40))) ; one call |# +#| (rem 6 (rem 40 (rem 206 40))) ; one call |# +#| (rem 6 (rem 40 6)) ; one call |# +#| (rem 6 4) ; one call |# +#| 2 |# + +;; 18 calls to remainder are performed + +;; Process generated by applicative order evaluation + +#| (gcd- 206 40) |# +#| (if (= 40 0) 206 (gcd- 40 (remainder 206 40))) ; one call |# +#| (gcd- 40 6) |# +#| (gcd- 40 6) |# +#| (if (= 6 0) 40 (gcd- 6 (remainder 40 6))) |# +#| (gcd- 6 (remainder 40 6)) ; one call |# +#| (gcd- 6 4) |# +#| (if (= 4 0) 6 (gcd- 4 (remainder 6 4))) |# +#| (gcd- 4 (remainder 6 4)) ; one call |# +#| (gcd- 4 2) |# +#| (if (= 2 0) 4 (gcd- 2 (remainder 4 2))) |# +#| (gcd- 2 (remainder 4 2)) ; one call |# +#| (gcd- 2 0) |# +#| (if (= 0 0) 2 (gcd- 0 (remainder 2 0))) |# +#| 2 |# + +;; 4 calls to remainder are performed + +(#%provide smallest-divisor) +(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 (next test-divisor))))) + +(define (divides? a b) + (= (remainder b a) 0)) + +(#%provide prime?) +(define (prime? n) + (= n (smallest-divisor n))) + +(define (expmod base expo m) + (cond + ((= expo 0) 1) + ((even-? expo) + (remainder (square (expmod base (/ expo 2) m)) m)) + (else + (remainder + (* base (expmod base (- expo 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))) + +#| 1.21 |# + +#| (smallest-divisor 199) |# +#| (smallest-divisor 1999) |# +#| (smallest-divisor 19999) |# + +(#%provide timed-prime-test) +(define (timed-prime-test n) + (newline) + (display n) + (start-prime-test n (runtime))) + +(define (start-prime-test n start-time) + (if (fast-prime? n 100) + (report-prime (- (runtime) start-time)))) + +(define (report-prime elapsed-time) +(display " *** ") + (display elapsed-time)) + +#| 1.22 |# + +(#%provide search-for-primes) +(define (search-for-primes a b) + (cond + ((> a b) (newline)) + (else + (timed-prime-test a) + (search-for-primes (+ a 1) b)))) + +;; Smallest primes over 1000: +;; 1009 3us +;; 1013 3 +;; 1019 3 + +;; Smallest primes over 10000: +;; 10007 9us +;; 10019 8 +;; 10037 9 + +;; Smallest primes over 100000: +;; 100003 22us +;; 100019 21 +;; 100043 20 + +;; Smallest primes over 1000000: +;; 1000003 65us +;; 1000033 65 +;; 1000037 65 + +;; 9 / 3 = 3 +;; 21 / 9 = 2.33 +;; 65 / 21 = 3.095 + +;; sqrt(10) = 3.16 + +#| 1.23 |# + +(define (next n) + (if (= n 2) 3 (+ n 2))) + +;; Smallest primes over 1000: +;; 1009 2us +;; 1013 2 +;; 1019 2 + +;; Smallest primes over 10000: +;; 10007 5us +;; 10019 4 +;; 10037 4 + +;; Smallest primes over 100000: +;; 100003 11us +;; 100019 12 +;; 100043 11 + +;; Smallest primes over 1000000: +;; 1000003 34us +;; 1000033 34 +;; 1000037 34 + +;; 3 / 2 = 1.4 +;; 9 / 4 = 2.25 +;; 21 / 11 = 1.9 +;; 65 / 34 = 1.9 + +#| 1.24 |# + +;; Using fast-prime? + +;; Smallest primes over 1000: +;; 1009 .28ms +;; 1013 .29 +;; 1019 .31 + +;; Smallest primes over 10000: +;; 10007 .37ms +;; 10019 .36 +;; 10037 .40 + +;; Smallest primes over 100000: +;; 100003 .42ms +;; 100019 .44 +;; 100043 .46 + +;; Smallest primes over 1000000: +;; 1000003 .50ms +;; 1000033 .49 +;; 1000037 .51 + +;; Scaling up by a factor of ten adds a constant amount of time + +#| 1.25 |# + +;; This version of expmod requires too much space to +;; represent the intermediate result when using very +;; large exponents + +(define (expmod-bad base expo m) + (remainder (fast-expt-iter base expo) m)) + +#| 1.26 |# + +;; This version of expmod makes two recursive calls of +;; size n / 2, making it Theta(n) in time rather than +;; Theta(log(n)) + +(define (expmod-slow base expo m) + (cond + ((= expo 0) 1) + ((even-? expo) + (remainder + (* + (remainder (expmod-slow base (/ expo 2) m) + (remainder (expmod-slow base (/ expo 2) m)))) + m)) + (else + (remainder + (* + base + (expmod-slow base (- expo 1) m)) + m)))) + +#| 1.27 |# + +(#%provide fermat-test-exhaustive) +(define (fermat-test-exhaustive n) + (define (iter i res) + (define (try-it a) (= (expmod a n n) a)) + (if (= i n) + res + (iter (+ i 1) (and res (try-it i))))) + (iter 1 true)) + +#| (fermat-test-exhaustive 561) |# +#| (fermat-test-exhaustive 1105) |# +#| (fermat-test-exhaustive 1729) |# +#| (fermat-test-exhaustive 2465) |# +#| (fermat-test-exhaustive 2821) |# +#| (fermat-test-exhaustive 6601) |# + +#| 1.28 |# + +(define (expmod-sig base expo m) + (define (square-sig x) + (define squared (remainder (square x) m)) + (if + (and + (= squared 1) + (not (= x 1)) + (not (= x expo))) + 0 + squared)) + (cond + ((= expo 0) 1) + ((even-? expo) + (square-sig (expmod base (/ expo 2) m))) + (else + (remainder + (* base (expmod base (- expo 1) m)) + m)))) + +(define (miller-rabin-test n) + (define (try-it a) + (= (expmod a (- n 1) n) 1)) + (try-it (+ 1 (random (- n 1))))) + +(#%provide mr-fast-prime?) +(define (mr-fast-prime? n times) + (cond + ((= times 0) true) + ((miller-rabin-test n) (mr-fast-prime? n (- times 1))) + (else false))) + +(#%provide sum-integers-) +(define (sum-integers- a b) + (if (> a b) + 0 + (+ a (sum-integers- (+ a 1) b)))) + +(#%provide sum-cubes-) +(define (sum-cubes- a b) + (if (> a b) + 0 + (+ (cube a) (sum-cubes- (+ a 1) b)))) + +(#%provide pi-sum-) +(define (pi-sum- a b) + (if (> a b) + 0 + (+ (/ 1.0 (* a (+ a 2))) (pi-sum- (+ a 4) b)))) + +(#%provide sum) +(define (sum term a next b) + (if (> a b) + 0 + (+ + (term a) + (sum term (next a) next b)))) + +(define (inc n) (+ n 1)) + +(#%provide sum-cubes) +(define (sum-cubes a b) (sum cube a inc b)) + +(define (id x) x) + +(#%provide sum-integers) +(define (sum-integers a b) (sum id a inc b)) + +(#%provide pi-sum) +(define (pi-sum a b) + (define (pi-term x) (/ 1.0 (* x (+ x 2)))) + (define (pi-next x) (+ x 4)) + (sum pi-term a pi-next b)) + +(#%provide integral) +(define (integral f a b dx) + (define (add-dx x) (+ x dx)) + (* (sum f (+ a (/ dx 2.0)) add-dx b) dx)) |