From 576ac44fc908c2f9f3b754c783560c1f05f29c69 Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Sun, 22 Apr 2018 22:28:33 +0700 Subject: Finish Chapter 1 of SICP --- sicp/chapter1.rkt | 394 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ sicp/chapter2.rkt | 52 +++++++ sicp/scratch.rkt | 305 ------------------------------------------ 3 files changed, 446 insertions(+), 305 deletions(-) create mode 100644 sicp/chapter1.rkt create mode 100644 sicp/chapter2.rkt delete mode 100644 sicp/scratch.rkt (limited to 'sicp') diff --git a/sicp/chapter1.rkt b/sicp/chapter1.rkt new file mode 100644 index 0000000..76716f7 --- /dev/null +++ b/sicp/chapter1.rkt @@ -0,0 +1,394 @@ +#lang sicp +(define (square x) (* x x)) +(define (sum-of-square x y) (+ (square x) (square y))) +(define (abs x) + (if (> x 0) x + (- x))) +(define (>= x y) (not (< x y))) + +(define (ex-1-3 a b c) + (cond ((and (< a b) (< a c)) (sum-of-square b c)) + ((and (< b a) (< b c)) (sum-of-square a c)) + (else (sum-of-square a b)))) + +(define (good-enough? guess x) + (< (abs (* (- guess x) 1000)) x)) +(define (average x y) (/ (+ x y) 2)) +(define (sqrt x) + (define (sqrt-improve guess x) (average guess (/ x guess))) + (define (sqrt-iter guess x) + (if (good-enough? (square guess) x) + guess + (sqrt-iter (sqrt-improve guess x) x))) + (sqrt-iter 1.0 x)) + +(define (cube x) (* x x x)) +(define (cbrt x) ; Exercise 1.8 + (define (cbrt-iter guess x) + (if (good-enough? (cube guess) x) + guess + (cbrt-iter (/ (+ (/ x (square guess)) (* 2 guess)) 3) x))) + (cbrt-iter 1.0 x)) + +(define (dec x) (- x 1)) +(define (inc x) (+ x 1)) +(define (factorial n) + (if (= n 1) 1 (* n (factorial (dec n))))) + +; Exercise 1.10 +(define (A x y) + (cond ((= y 0) 0) + ((= x 0) (* 2 y)) + ((= y 1) 2) + (else (A (dec x) (A x (dec y)))))) +(define (f n) (A 0 n)) ; return 2n +(define (g n) (A 1 n)) ; return n logical-and 2^n +(define (h n) (A 2 n)) ; return n logical-and (2 up-arrow up-arrow 2) + +(define (fibonacci n) + (define (fibonacci-iter a b m) + (if (= m n) b (fibonacci-iter b (+ a b) (inc m)))) + (if (= n 0) 0 (fibonacci-iter 0 1 1))) + +(define (count-change amount) + (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))) + (define (cc amount kinds-of-coins) + (cond ((= amount 0) 1) ; this means the coin change is valid + ((or (< amount 0) (= kinds-of-coins 0)) 0) + (else (+ (cc amount (dec kinds-of-coins)) + (cc (- amount (first-denomination kinds-of-coins)) + kinds-of-coins))))) + (cc amount 5)) + +; Exercise 1.11 +(define (f-recursive n) + (if (< n 3) + n + (+ (f-recursive (dec n)) (* (f-recursive (- n 2)) 2) + (* (f-recursive (- n 3)) 3)))) +(define (f-iterative n) + (define (f-iter a b c count) + (if (= count 0) c (f-iter b c (+ c (* b 2) (* a 3)) (dec count)))) + (if (< n 3) n (f-iter 1 2 4 (- n 3)))) + +; Exercise 1.12 +(define (combination-pascal n r) + (if (or (= n 1) (= r 1)) + 1 + (+ (combination-pascal (dec n) (dec r)) (combination-pascal (dec n) r)))) +(define (combination n r) ; well, factorial is recursive :-) + (/ (factorial n) (factorial r) (factorial (- n r)))) + +(define (even? n) (= (remainder n 2) 0)) +(define (expt-recursive b n) + (cond ((= n 0) 1) + ((even? n) (square (expt-recursive b (/ n 2)))) + (else (* (expt-recursive b (dec n)) b)))) +; Exercise 1.16 +(define (expt-iterative b n) + (define (expt-iter b n a) + (cond ((= n 0) a) + ((even? n) (expt-iter (square b) (/ n 2) a)) + (else (expt-iter b (dec n) (* a b))))) + (expt-iter b n 1)) + +; Exercise 1.17 +(define (double n) (+ n n)) +(define (halve n) (/ n 2)) +(define (mul-recursive a b) + (cond ((= b 0) 0) + ((< b 0) (mul-recursive (- a) (- b))) + ; halve only works on even intergers, thus even? must also be included + ((even? b) (double (mul-recursive a (halve b)))) + (else (+ (mul-recursive a (dec b)) a)))) +; Exercise 1.18 +(define (mul-iterative a b) + (define (mul-iter a b c) + (cond ((= b 0) c) + ((even? b) (mul-iter (double a) (halve b) c)) + (else (mul-iter a (dec b) (+ c a))))) + (if (< b 0) (mul-iter (- a) (- b) 0) (mul-iter a b 0))) + +(define (fib n) + (define (fib-iter a b p q count) + ; Tpq(a, b) = (bq + aq + ap, bp + aq) + ; Tpq(Tpq(a, b)) = (..., (bp + aq)p + (bq + aq + ap)q) + ; = (..., b(pp + qq) + a(2pq + qq)) + ; => p' = pp + qq, q' = 2pq + qq + (cond ((= count 0) b) + ((even? count) + (fib-iter a + b + (sum-of-square p q) + (+ (* 2 p q) (square q)) + (/ count 2))) + (else (fib-iter (+ (* b q) (* a q) (* a p)) + (+ (* b p) (* a q)) + p + q + (dec count))))) + (fib-iter 1 0 0 1 n)) + +; Exercise 1.23 +(define (smallest-divisor n) + (define (find-divisor test-divisor) + (cond ((> (square test-divisor) n) n) + ((= (remainder n test-divisor) 0) test-divisor) + (else (find-divisor (+ test-divisor 2))))) + (if (even? n) 2 (find-divisor 3))) +(define (prime? n) (and (> n 1) (= (smallest-divisor n) n))) + +(define (expmod x y z) + (cond ((= y 0) 1) + ((even? y) (remainder (square (expmod x (/ y 2) z)) z)) + (else (remainder (* (expmod x (dec y) z) x) z)))) +(define (fermat-prime-trial n a) (= (expmod a n n) a)) +(define (fermat-prime? n times) + (define (fermat-test n) + (fermat-prime-trial (inc (random (dec n))))) + (cond ((= times 0) true) + ((fermat-test n) (fermat-prime? n (dec times))) + (else false))) + +; Exercise 1.22 +(define (timed-prime-test n) + (define (report-prime elapsed-time) + (display " *** ") + (display elapsed-time)) + (define (start-prime-test n start-time) + (if (prime? n) (report-prime (- (runtime) start-time)) false)) + (newline) + (display n) + (start-prime-test n (runtime))) +(define (search-for-primes start n) + (cond ((< n 0)) ; wow this is valid + ((even? start) (search-for-primes (inc start) n)) + ((timed-prime-test start) (search-for-primes (+ start 2) (dec n))) + (else (search-for-primes (+ start 2) n)))) + +; Exercise 1.25 +(define (expmod-lousy x y z) (remainder (expt-recursive x y) z)) +(define (expmod-effeciency-test func x y z) + (define (display-elapsed start-time) + (func x y z) + (display (- (runtime) start-time)) + (newline)) + (display-elapsed (runtime))) + +; Exercise 1.27 +(define (slow-fermat-prime? n) + (define (slow-iter count) + (cond ((= count 1) true) + ((fermat-prime-trial n count) (slow-iter (dec count))) + (else false))) + (slow-iter (dec n))) + +; Exercise 1.28 +(define (miller-rabin n) + (define (nontrivial-sqrt-1-mod? m) + (let ((r (remainder (square m) n))) + (if (or (not (= r 1)) (= m 1) (= m (dec n))) r 0))) + (define (expmod-1 x y) + (cond ((= y 0) 1) + ((odd? y) (remainder (* (expmod-1 x (dec y)) x) n)) + (else (nontrivial-sqrt-1-mod? (expmod-1 x (/ y 2)))))) + (define (miller-rabin-trail a) (= (expmod-1 a (dec n)) 1)) + (define (miller-rabin-iter count) + (cond ((= count 0)) + ((miller-rabin-trail (inc (random (dec n)))) + (miller-rabin-iter (dec count))) + (else false))) + (cond ((= n 2) true) + ((or (< n 2) (even? n)) false) + (else (miller-rabin-iter (/ (dec n) 2))))) + +(define (sum term a next b) + (if (> a b) 0 (+ (term a) (sum term (next a) next b)))) +(define (identity x) x) +(define (sum-integers a b) (sum identity a inc b)) +(define (sum-cubes a b) (sum cube a inc b)) +(define (pi-sum a b) + (sum (lambda (x) (/ 1.0 x (+ x 2))) a (lambda (x) (+ x 4)) b)) +(define dx 0.00001) +(define (integral f a b dx) + (* (sum f (+ a (/ dx 2.0)) (lambda (x) (+ x dx)) b) dx)) + +; Exercise 1.29 +(define (simpson-integral f a b n) + (define h (/ (- b a) n)) ; sorry! + (define (fk k) (f (+ a (* k h)))) + (define (y k) + (cond ((= (remainder k n) 0) (fk k)) + ((even? k) (* (fk k) 2)) + (else (* (fk k) 4)))) + (define (simpson-iter k) + (if (= k 0) + (y 0) + (+ (y k) (simpson-iter (dec k))))) + (* (simpson-iter n) h 1/3)) + +; Exercise 1.30 +(define (sum-iter term a next b) + (define (iter a result) + (if (> a b) + result + (iter (next a) (+ (term a) result)))) + (iter a 0)) + +; Exercise 1.31 +(define (product-recursive term a next b) + (if (> a b) + 1 + (* (term a) (product-recursive term (next a) next b)))) +(define (pi-fourth precision) + (define (john-wallis-term n) + (* (if (even? n) (/ n (inc n)) (/ (inc n) n)) 1.0)) + (product-recursive john-wallis-term 2 inc (+ (* (abs precision) 2) 2))) +(define (product-iterative term a next b) + (define (iter a result) + (if (> a b) + result + (iter (next a) (* (term a) result)))) + (iter a 1)) + +; Exercise 1.32 +(define (accumulate combiner null-value term a next b) + (if (> a b) + null-value + (combiner (term a) + (accumulate combiner null-value term (next a) next b)))) +(define (sum-recursive term a next b) (accumulate + 0 term a next b)) +(define (accumulate-iter combiner null-value term a next b) + (define (iter a result) + (if (> a b) + result + (iter (next a) (combiner (term a) result)))) + (iter a null-value)) + +; Exercise 1.33 +(define (filtered-accumulate filter combiner null-value term a next b) + (if (> a b) + null-value + (combiner (if (filter a) (term a) null-value) + (filtered-accumulate filter + combiner + null-value + term + (next a) + next + b)))) +(define (sum-square-primes a b) + (filtered-accumulate prime? + 0 square a inc b)) +(define (product-relative-primes n) + (filtered-accumulate (lambda (i) (= (gcd i n) 1)) * 1 identity 1 inc (dec n))) + +(define (search f neg-point pos-point) + (let ((midpoint (average neg-point pos-point))) + (if (good-enough? neg-point pos-point) + midpoint + (let ((test-value (f midpoint))) + (cond ((positive? test-value) (search f neg-point midpoint)) + ((negative? test-value) (search f midpoint pos-point)) + (else midpoint)))))) + +(define (half-interval-method f a b) + (let ((a-value (f a)) + (b-value (f b))) + (cond ((and (negative? a-value) (positive? b-value)) + (search f a b)) + ((and (negative? b-value) (positive? a-value)) + (search f b a)) + (else (error "Values are not of opposite sign" a b))))) + +(define (fixed-point f first-guess) + (define (try guess) + (let ((next (f guess))) + (if (good-enough? guess next) next (try next)))) + (try first-guess)) + +(define (sqrt-fixed x) + (fixed-point (lambda (y) (average y (/ x y))) 1.0)) + +; Exercise 1.35 +(define golden-ratio (fixed-point (lambda (x) (inc (/ x))) 1.0)) + +; Exercise 1.37 +(define (cont-frac-recursive n d k) + (define (cont-frac n d k root) + (if (= k 0) + root + (cont-frac n d (dec k) (/ (n k) (+ (d k) root))))) + (if (> k 0) + (cont-frac n d (dec k) (/ (n k) (d k))) + (error "You weirdo!"))) +(define (cont-frac-iterative n d k) + (define (cont-frac n d k c) + (if (< c k) + (/ (n c) (+ (d c) (cont-frac n d k (inc c)))) + (/ (n k) (d k)))) ; UB if k is not a positive integer + (cont-frac n d k 1)) + +; Exercise 1.38 +(define (e-2 precision) + (cont-frac-iterative + (lambda (i) 1.0) + (lambda (i) (if (= (remainder i 3) 2) (* (inc i) 2/3) 1.0)) + precision)) + +; Exercise 1.39 +(define (tan-cf x k) + (cont-frac-iterative + (lambda (i) (if (= i 1) x (square x))) + (lambda (i) ((if (even? i) - +) (dec (* i 2)))) + k)) + +(define (average-damp f) (lambda (x) (average x (f x)))) +(define (newton-method g guess) + (define (deriv g) + (lambda (x) (/ (- (g (+ x dx)) (g x)) dx))) + (let ((f (lambda (x) (- x (/ (g x) ((deriv g) x)))))) + (fixed-point f guess))) + +(define (fixed-point-of-transform g transform guess) + (fixed-point (transform g) guess)) + +; Exercise 1.40 +(define (cubic a b c) + (lambda (x) (+ (cube x) (* (square x) a) (* x b) c))) + +; Exercise 1.41 +(define (duplicate f) (lambda (x) (f (f x)))) + +; Exercise 1.42 +(define (compose f g) (lambda (x) (f (g x)))) + +; Exercise 1.43 +(define (repeated f times) + (cond ((< times 1) identity) + ((= times 1) f) + (else (compose f (repeated f (dec times)))))) + +; Exercise 1.44 +(define (smooth f) + (lambda (x) (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3))) +(define (repeated-smooth f times) (repeated smooth times)) + +; Exercise 1.45 +(define (root n x) + (fixed-point-of-transform + (lambda (y) (/ x (expt y (dec n)))) + (repeated average-damp (log n 2)) + 1.0)) + +; Exercise 1.46 +(define (iter-improve good-enough improve) + (lambda (x) + (let ((xim (improve x))) + (if (good-enough x xim) + xim + ((iter-improve good-enough improve) xim))))) diff --git a/sicp/chapter2.rkt b/sicp/chapter2.rkt new file mode 100644 index 0000000..2915203 --- /dev/null +++ b/sicp/chapter2.rkt @@ -0,0 +1,52 @@ +#lang sicp +; Exercise 2.1 +(define (make-rat n d) + (if (< d 0) + (make-rat (- n) (- d)) + (let ((g (gcd n d))) + (cons (/ n g) (/ d g))))) +(define numer car) +(define denom cdr) +(define (print-rat x) + (display (numer x)) + (display "/") + (display (denom x)) + (newline)) +(define (add-rat x y) + (let ((dx (denom x)) + (dy (denom y))) + (make-rat (+ (* (numer x) dy) + (* (numer y) dx)) + (* dx dy)))) +(define (sub-rat x y) + (add-rat x (make-rat (- (numer y)) (denom y)))) +(define (mul-rat x y) + (make-rat (* (numer x) (numer y)) + (* (denom x) (denom y)))) +(define (div-rat x y) + (make-rat (* (numer x) (denom y)) + (* (denom x) (numer y)))) +(define (equal-rat? x y) + (= (* (numer x) (denom y)) + (* (numer y) (denom x)))) + +; Exercise 2.2 +(define make-point cons) +(define x-point car) +(define y-point cdr) +(define make-segment cons) +(define start-segment car) +(define end-segment cdr) +(define (average x y) (/ (+ x y) 2)) +(define (midpoint-segment d) + (let ((A (start-segment d)) + (B (end-segment d))) + (make-point (average (x-point A) (x-point B)) + (average (y-point A) (y-point B))))) +(define (print-point P) + (display "(") + (display (x-point P)) + (display ", ") + (display (y-point P)) + (display ")") + (newline)) diff --git a/sicp/scratch.rkt b/sicp/scratch.rkt deleted file mode 100644 index 298d42d..0000000 --- a/sicp/scratch.rkt +++ /dev/null @@ -1,305 +0,0 @@ -#lang sicp -(define (square x) (* x x)) -(define (sum-of-square x y) (+ (square x) (square y))) -(define (abs x) - (if (> x 0) x - (- x))) -(define (>= x y) (not (< x y))) - -(define (ex-1-3 a b c) - (cond ((and (< a b) (< a c)) (sum-of-square b c)) - ((and (< b a) (< b c)) (sum-of-square a c)) - (else (sum-of-square a b)))) - -(define (good-enough? guess x) - (< (abs (* (- guess x) 1000)) x)) -(define (average x y) (/ (+ x y) 2)) -(define (sqrt x) - (define (sqrt-improve guess x) (average guess (/ x guess))) - (define (sqrt-iter guess x) - (if (good-enough? (square guess) x) - guess - (sqrt-iter (sqrt-improve guess x) x))) - (sqrt-iter 1.0 x)) - -(define (cube x) (* x x x)) -(define (cbrt x) ; Exercise 1.8 - (define (cbrt-iter guess x) - (if (good-enough? (cube guess) x) - guess - (cbrt-iter (/ (+ (/ x (square guess)) (* 2 guess)) 3) x))) - (cbrt-iter 1.0 x)) - -(define (dec x) (- x 1)) -(define (inc x) (+ x 1)) -(define (factorial n) - (if (= n 1) 1 (* n (factorial (dec n))))) - -; Exercise 1.10 -(define (A x y) - (cond ((= y 0) 0) - ((= x 0) (* 2 y)) - ((= y 1) 2) - (else (A (dec x) (A x (dec y)))))) -(define (f n) (A 0 n)) ; return 2n -(define (g n) (A 1 n)) ; return n logical-and 2^n -(define (h n) (A 2 n)) ; return n logical-and (2 up-arrow up-arrow 2) - -(define (fibonacci n) - (define (fibonacci-iter a b m) - (if (= m n) b (fibonacci-iter b (+ a b) (inc m)))) - (if (= n 0) 0 (fibonacci-iter 0 1 1))) - -(define (count-change amount) - (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))) - (define (cc amount kinds-of-coins) - (cond ((= amount 0) 1) ; this means the coin change is valid - ((or (< amount 0) (= kinds-of-coins 0)) 0) - (else (+ (cc amount (dec kinds-of-coins)) - (cc (- amount (first-denomination kinds-of-coins)) - kinds-of-coins))))) - (cc amount 5)) - -; Exercise 1.11 -(define (f-recursive n) - (if (< n 3) - n - (+ (f-recursive (dec n)) (* (f-recursive (- n 2)) 2) - (* (f-recursive (- n 3)) 3)))) -(define (f-iterative n) - (define (f-iter a b c count) - (if (= count 0) c (f-iter b c (+ c (* b 2) (* a 3)) (dec count)))) - (if (< n 3) n (f-iter 1 2 4 (- n 3)))) - -; Exercise 1.12 -(define (combination-pascal n r) - (if (or (= n 1) (= r 1)) - 1 - (+ (combination-pascal (dec n) (dec r)) (combination-pascal (dec n) r)))) -(define (combination n r) ; well, factorial is recursive :-) - (/ (factorial n) (factorial r) (factorial (- n r)))) - -(define (even? n) (= (remainder n 2) 0)) -(define (expt-recursive b n) - (cond ((= n 0) 1) - ((even? n) (square (expt-recursive b (/ n 2)))) - (else (* (expt-recursive b (dec n)) b)))) -; Exercise 1.16 -(define (expt-iterative b n) - (define (expt-iter b n a) - (cond ((= n 0) a) - ((even? n) (expt-iter (square b) (/ n 2) a)) - (else (expt-iter b (dec n) (* a b))))) - (expt-iter b n 1)) - -; Exercise 1.17 -(define (double n) (+ n n)) -(define (halve n) (/ n 2)) -(define (mul-recursive a b) - (cond ((= b 0) 0) - ((< b 0) (mul-recursive (- a) (- b))) - ; halve only works on even intergers, thus even? must also be included - ((even? b) (double (mul-recursive a (halve b)))) - (else (+ (mul-recursive a (dec b)) a)))) -; Exercise 1.18 -(define (mul-iterative a b) - (define (mul-iter a b c) - (cond ((= b 0) c) - ((even? b) (mul-iter (double a) (halve b) c)) - (else (mul-iter a (dec b) (+ c a))))) - (if (< b 0) (mul-iter (- a) (- b) 0) (mul-iter a b 0))) - -(define (fib n) - (define (fib-iter a b p q count) - ; Tpq(a, b) = (bq + aq + ap, bp + aq) - ; Tpq(Tpq(a, b)) = (..., (bp + aq)p + (bq + aq + ap)q) - ; = (..., b(pp + qq) + a(2pq + qq)) - ; => p' = pp + qq, q' = 2pq + qq - (cond ((= count 0) b) - ((even? count) - (fib-iter a - b - (sum-of-square p q) - (+ (* 2 p q) (square q)) - (/ count 2))) - (else (fib-iter (+ (* b q) (* a q) (* a p)) - (+ (* b p) (* a q)) - p - q - (dec count))))) - (fib-iter 1 0 0 1 n)) - -; Exercise 1.23 -(define (smallest-divisor n) - (define (find-divisor test-divisor) - (cond ((> (square test-divisor) n) n) - ((= (remainder n test-divisor) 0) test-divisor) - (else (find-divisor (+ test-divisor 2))))) - (if (even? n) 2 (find-divisor 3))) -(define (prime? n) (and (> n 1) (= (smallest-divisor n) n))) - -(define (expmod x y z) - (cond ((= y 0) 1) - ((even? y) (remainder (square (expmod x (/ y 2) z)) z)) - (else (remainder (* (expmod x (dec y) z) x) z)))) -(define (fermat-prime-trial n a) (= (expmod a n n) a)) -(define (fermat-prime? n times) - (define (fermat-test n) - (fermat-prime-trial (inc (random (dec n))))) - (cond ((= times 0) true) - ((fermat-test n) (fermat-prime? n (dec times))) - (else false))) - -; Exercise 1.22 -(define (timed-prime-test n) - (define (report-prime elapsed-time) - (display " *** ") - (display elapsed-time)) - (define (start-prime-test n start-time) - (if (prime? n) (report-prime (- (runtime) start-time)) false)) - (newline) - (display n) - (start-prime-test n (runtime))) -(define (search-for-primes start n) - (cond ((< n 0)) ; wow this is valid - ((even? start) (search-for-primes (inc start) n)) - ((timed-prime-test start) (search-for-primes (+ start 2) (dec n))) - (else (search-for-primes (+ start 2) n)))) - -; Exercise 1.25 -(define (expmod-lousy x y z) (remainder (expt-recursive x y) z)) -(define (expmod-effeciency-test func x y z) - (define (display-elapsed start-time) - (func x y z) - (display (- (runtime) start-time)) - (newline)) - (display-elapsed (runtime))) - -; Exercise 1.27 -(define (slow-fermat-prime? n) - (define (slow-iter count) - (cond ((= count 1) true) - ((fermat-prime-trial n count) (slow-iter (dec count))) - (else false))) - (slow-iter (dec n))) - -; Exercise 1.28 -(define (miller-rabin n) - (define (nontrivial-sqrt-1-mod? m) - (let ((r (remainder (square m) n))) - (if (or (not (= r 1)) (= m 1) (= m (dec n))) r 0))) - (define (expmod-1 x y) - (cond ((= y 0) 1) - ((odd? y) (remainder (* (expmod-1 x (dec y)) x) n)) - (else (nontrivial-sqrt-1-mod? (expmod-1 x (/ y 2)))))) - (define (miller-rabin-trail a) (= (expmod-1 a (dec n)) 1)) - (define (miller-rabin-iter count) - (cond ((= count 0)) - ((miller-rabin-trail (inc (random (dec n)))) - (miller-rabin-iter (dec count))) - (else false))) - (cond ((= n 2) true) - ((or (< n 2) (even? n)) false) - (else (miller-rabin-iter (/ (dec n) 2))))) - -(define (sum term a next b) - (if (> a b) 0 (+ (term a) (sum term (next a) next b)))) -(define (identity x) x) -(define (sum-integers a b) (sum identity a inc b)) -(define (sum-cubes a b) (sum cube a inc b)) -(define (pi-sum a b) - (sum (lambda (x) (/ 1.0 x (+ x 2))) a (lambda (x) (+ x 4)) b)) -(define (integral f a b dx) - (* (sum f (+ a (/ dx 2.0)) (lambda (x) (+ x dx)) b) dx)) - -; Exercise 1.29 -(define (simpson-integral f a b n) - (define h (/ (- b a) n)) ; sorry! - (define (fk k) (f (+ a (* k h)))) - (define (y k) - (cond ((= (remainder k n) 0) (fk k)) - ((even? k) (* (fk k) 2)) - (else (* (fk k) 4)))) - (define (simpson-iter k) - (if (= k 0) - (y 0) - (+ (y k) (simpson-iter (dec k))))) - (* (simpson-iter n) h 1/3)) - -; Exercise 1.30 -(define (sum-iter term a next b) - (define (iter a result) - (if (> a b) - result - (iter (next a) (+ (term a) result)))) - (iter a 0)) - -; Exercise 1.31 -(define (product-recursive term a next b) - (if (> a b) - 1 - (* (term a) (product-recursive term (next a) next b)))) -(define (pi-fourth precision) - (define (john-wallis-term n) - (* (if (even? n) (/ n (inc n)) (/ (inc n) n)) 1.0)) - (product-recursive john-wallis-term 2 inc (+ (* (abs precision) 2) 2))) -(define (product-iterative term a next b) - (define (iter a result) - (if (> a b) - result - (iter (next a) (* (term a) result)))) - (iter a 1)) - -; Exercise 1.32 -(define (accumulate combiner null-value term a next b) - (if (> a b) - null-value - (combiner (term a) - (accumulate combiner null-value term (next a) next b)))) -(define (sum-recursive term a next b) (accumulate + 0 term a next b)) -(define (accumulate-iter combiner null-value term a next b) - (define (iter a result) - (if (> a b) - result - (iter (next a) (combiner (term a) result)))) - (iter a null-value)) - -; Exercise 1.33 -(define (filtered-accumulate filter combiner null-value term a next b) - (if (> a b) - null-value - (combiner (if (filter a) (term a) null-value) - (filtered-accumulate filter - combiner - null-value - term - (next a) - next - b)))) -(define (sum-square-primes a b) - (filtered-accumulate prime? + 0 square a inc b)) -(define (product-relative-primes n) - (filtered-accumulate (lambda (i) (= (gcd i n) 1)) * 1 identity 1 inc (dec n))) - -(define (search f neg-point pos-point) - (let ((midpoint (average neg-point pos-point))) - (if (good-enough? neg-point pos-point) - midpoint - (let ((test-value (f midpoint))) - (cond ((positive? test-value) (search f neg-point midpoint)) - ((negative? test-value) (search f midpoint pos-point)) - (else midpoint)))))) - -(define (half-interval-method f a b) - (let ((a-value (f a)) - (b-value (f b))) - (cond ((and (negative? a-value) (positive? b-value)) - (search f a b)) - ((and (negative? b-value) (positive? a-value)) - (search f b a)) - (else (error "Values are not of opposite sign" a b))))) -- cgit 1.4.1