1 665c255d 2023-08-04 jrmu ;; (define tolerance 0.0000001)
2 665c255d 2023-08-04 jrmu ;; (define (fixed-point f first-guess)
3 665c255d 2023-08-04 jrmu ;; (define (close-enough? v1 v2)
4 665c255d 2023-08-04 jrmu ;; (< (abs (- v1 v2)) tolerance))
5 665c255d 2023-08-04 jrmu ;; (define (try guess)
6 665c255d 2023-08-04 jrmu ;; (let ((next (f guess)))
7 665c255d 2023-08-04 jrmu ;; (if (close-enough? guess next)
9 665c255d 2023-08-04 jrmu ;; (try next))))
10 665c255d 2023-08-04 jrmu ;; (try first-guess))
12 665c255d 2023-08-04 jrmu (define (average x y)
13 665c255d 2023-08-04 jrmu (/ (+ x y) 2.0))
14 665c255d 2023-08-04 jrmu ;; (define (average-damp f)
15 665c255d 2023-08-04 jrmu ;; (lambda (x) (average x (f x))))
16 665c255d 2023-08-04 jrmu ;; (define (fixed-point-of-transform g transform guess)
17 665c255d 2023-08-04 jrmu ;; (fixed-point (transform g) guess))
18 665c255d 2023-08-04 jrmu ;; (define (sqrt x)
19 665c255d 2023-08-04 jrmu ;; (fixed-point-of-transform (lambda (y) (/ x y))
20 665c255d 2023-08-04 jrmu ;; average-damp
22 665c255d 2023-08-04 jrmu ;; (define (cube-root x)
23 665c255d 2023-08-04 jrmu ;; (fixed-point-of-transform (lambda (y) (/ x (square y)))
24 665c255d 2023-08-04 jrmu ;; average-damp
27 665c255d 2023-08-04 jrmu ;; (define (compose f g)
28 665c255d 2023-08-04 jrmu ;; (lambda (x)
29 665c255d 2023-08-04 jrmu ;; (f (g x))))
31 665c255d 2023-08-04 jrmu (define (test-case actual expected)
32 665c255d 2023-08-04 jrmu (load-option 'format)
34 665c255d 2023-08-04 jrmu (format #t "Actual: ~A Expected: ~A" actual expected))
36 665c255d 2023-08-04 jrmu (define (square x) (* x x))
37 665c255d 2023-08-04 jrmu ;; (define (inc x) (1+ x))
38 665c255d 2023-08-04 jrmu ;; (test-case ((compose square inc) 6) 49)
40 665c255d 2023-08-04 jrmu ;; (define (repeated f n)
41 665c255d 2023-08-04 jrmu ;; (if (= n 0)
42 665c255d 2023-08-04 jrmu ;; (lambda (x) x)
43 665c255d 2023-08-04 jrmu ;; (compose f (repeated f (- n 1)))))
45 665c255d 2023-08-04 jrmu ;; (test-case ((repeated square 2) 5) 625)
46 665c255d 2023-08-04 jrmu ;; (test-case (cube-root 5) 1.70997594668)
49 665c255d 2023-08-04 jrmu ;; Exercise 1.44. The idea of smoothing a function is an important concept in signal processing. If f is a function and dx is some small number, then the smoothed version of f is the function whose value at a point x is the average of f(x - dx), f(x), and f(x + dx). Write a procedure smooth that takes as input a procedure that computes f and returns a procedure that computes the smoothed f. It is sometimes valuable to repeatedly smooth a function (that is, smooth the smoothed function, and so on) to obtained the n-fold smoothed function. Show how to generate the n-fold smoothed function of any given function using smooth and repeated from exercise 1.43.
51 665c255d 2023-08-04 jrmu ;; (define dx 0.01)
53 665c255d 2023-08-04 jrmu ;; (define (smooth f)
54 665c255d 2023-08-04 jrmu ;; (lambda (x)
55 665c255d 2023-08-04 jrmu ;; (/ (+ (f x)
56 665c255d 2023-08-04 jrmu ;; (f (+ x dx))
57 665c255d 2023-08-04 jrmu ;; (f (- x dx)))
59 665c255d 2023-08-04 jrmu ;; (define (n-fold-smooth f n)
60 665c255d 2023-08-04 jrmu ;; ((repeated smooth n) f))
62 665c255d 2023-08-04 jrmu ;; Exercise 1.45. We saw in section 1.3.3 that attempting to compute square roots by naively finding a fixed point of y x/y does not converge, and that this can be fixed by average damping. The same method works for finding cube roots as fixed points of the average-damped y x/y2. Unfortunately, the process does not work for fourth roots -- a single average damp is not enough to make a fixed-point search for y x/y3 converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of y x/y3) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute nth roots as a fixed-point search based upon repeated average damping of y x/yn-1. Use this to implement a simple procedure for computing nth roots using fixed-point, average-damp, and the repeated procedure of exercise 1.43. Assume that any arithmetic operations you need are available as primitives.
64 665c255d 2023-08-04 jrmu ;; (define (fast-expt b n)
65 665c255d 2023-08-04 jrmu ;; (cond ((= n 0) 1)
66 665c255d 2023-08-04 jrmu ;; ((even? n) (square (fast-expt b (/ n 2))))
67 665c255d 2023-08-04 jrmu ;; (else (* b (fast-expt b (- n 1))))))
70 665c255d 2023-08-04 jrmu ;; (define (quartic-root x)
71 665c255d 2023-08-04 jrmu ;; (fixed-point-of-transform (lambda (y) (/ x (cube y)))
72 665c255d 2023-08-04 jrmu ;; (repeated average-damp 2)
74 665c255d 2023-08-04 jrmu ;; (define (nth-root-test x n d)
75 665c255d 2023-08-04 jrmu ;; (fixed-point-of-transform (lambda (y) (/ x (expt y (- n 1))))
76 665c255d 2023-08-04 jrmu ;; (repeated average-damp d)
79 665c255d 2023-08-04 jrmu ;; (test-case (nth-root-test 19 1 0) 19)
80 665c255d 2023-08-04 jrmu ;; (test-case (nth-root-test 19 2 1) 4.35889894)
81 665c255d 2023-08-04 jrmu ;; (test-case (nth-root-test 19 3 1) 2.66840165)
82 665c255d 2023-08-04 jrmu ;; (test-case (nth-root-test 19 4 2) 2.08779763)
83 665c255d 2023-08-04 jrmu ;; (test-case (nth-root-test 19 5 2) 1.80198313)
84 665c255d 2023-08-04 jrmu ;; (test-case (nth-root-test 19 6 2) 1.6335243)
85 665c255d 2023-08-04 jrmu ;; (test-case (nth-root-test 199 7 2) 2.13013723)
86 665c255d 2023-08-04 jrmu ;; (test-case (nth-root-test 199 8 3) 1.93801277)
87 665c255d 2023-08-04 jrmu ;; (test-case (nth-root-test 199 9 3) 1.80064508)
88 665c255d 2023-08-04 jrmu ;; (test-case (nth-root-test 199 10 3) 1.69779522)
89 665c255d 2023-08-04 jrmu ;; (test-case (nth-root-test 19999 11 3) 2.46037187)
90 665c255d 2023-08-04 jrmu ;; (test-case (nth-root-test 19999 12 3) 2.28253453)
91 665c255d 2023-08-04 jrmu ;; (test-case (nth-root-test 19999 13 3) 2.14213477)
92 665c255d 2023-08-04 jrmu ;; (test-case (nth-root-test 19999 14 3) 2.02868621)
93 665c255d 2023-08-04 jrmu ;; (test-case (nth-root-test 19999 15 3) 1.93523578)
94 665c255d 2023-08-04 jrmu ;; (test-case (nth-root-test 1999999 16 4) 2.47636331)
95 665c255d 2023-08-04 jrmu ;; (test-case (nth-root-test 1999999 17 4) 2.34773357)
98 665c255d 2023-08-04 jrmu ;; At first, my conclusion: average damp = sqrt(n), rounded down -- EXCEPT for 8...why is that?
99 665c255d 2023-08-04 jrmu ;; Maybe: 2^average damp = n
101 665c255d 2023-08-04 jrmu ;; (define (nth-root x n)
102 665c255d 2023-08-04 jrmu ;; (fixed-point-of-transform (lambda (y) (/ x (expt y (- n 1))))
103 665c255d 2023-08-04 jrmu ;; (repeated average-damp (truncate (/ (log n) (log 2))))
106 665c255d 2023-08-04 jrmu ;; (test-case (nth-root 19 1) 19)
107 665c255d 2023-08-04 jrmu ;; (test-case (nth-root 19 2) 4.35889894)
108 665c255d 2023-08-04 jrmu ;; (test-case (nth-root 19 3) 2.66840165)
109 665c255d 2023-08-04 jrmu ;; (test-case (nth-root 19 4) 2.08779763)
110 665c255d 2023-08-04 jrmu ;; (test-case (nth-root 19 5) 1.80198313)
111 665c255d 2023-08-04 jrmu ;; (test-case (nth-root 19 6) 1.6335243)
112 665c255d 2023-08-04 jrmu ;; (test-case (nth-root 199 7) 2.13013723)
113 665c255d 2023-08-04 jrmu ;; (test-case (nth-root 199 8) 1.93801277)
114 665c255d 2023-08-04 jrmu ;; (test-case (nth-root 199 9) 1.80064508)
115 665c255d 2023-08-04 jrmu ;; (test-case (nth-root 199 10) 1.69779522)
116 665c255d 2023-08-04 jrmu ;; (test-case (nth-root 19999 11) 2.46037187)
117 665c255d 2023-08-04 jrmu ;; (test-case (nth-root 19999 12) 2.28253453)
118 665c255d 2023-08-04 jrmu ;; (test-case (nth-root 19999 13) 2.14213477)
119 665c255d 2023-08-04 jrmu ;; (test-case (nth-root 19999 14) 2.02868621)
120 665c255d 2023-08-04 jrmu ;; (test-case (nth-root 19999 15) 1.93523578)
121 665c255d 2023-08-04 jrmu ;; (test-case (nth-root 1999999 16) 2.47636331)
122 665c255d 2023-08-04 jrmu ;; (test-case (nth-root 1999999 17) 2.34773357)
124 665c255d 2023-08-04 jrmu ;; Exercise 1.46. Several of the numerical methods described in this chapter are instances of an extremely general computational strategy known as iterative improvement. Iterative improvement says that, to compute something, we start with an initial guess for the answer, test if the guess is good enough, and otherwise improve the guess and continue the process using the improved guess as the new guess. Write a procedure iterative-improve that takes two procedures as arguments: a method for telling whether a guess is good enough and a method for improving a guess. Iterative-improve should return as its value a procedure that takes a guess as argument and keeps improving the guess until it is good enough. Rewrite the sqrt procedure of section 1.1.7 and the fixed-point procedure of section 1.3.3 in terms of iterative-improve.
126 665c255d 2023-08-04 jrmu (define (iterative-improve good-enough? improve)
127 665c255d 2023-08-04 jrmu (define (iter guess)
128 665c255d 2023-08-04 jrmu (if (good-enough? guess)
130 665c255d 2023-08-04 jrmu (iter (improve guess))))
133 665c255d 2023-08-04 jrmu (define (sqrt guess x)
134 665c255d 2023-08-04 jrmu ((iterative-improve (lambda (guess)
135 665c255d 2023-08-04 jrmu (< (abs (- (square guess) x)) 0.001))
136 665c255d 2023-08-04 jrmu (lambda (guess)
137 665c255d 2023-08-04 jrmu (average guess (/ x guess)))) guess))
140 665c255d 2023-08-04 jrmu (test-case (sqrt 2.2 5) 2.23606798)
142 665c255d 2023-08-04 jrmu (define (fixed-point f guess)
143 665c255d 2023-08-04 jrmu (let ((tolerance 0.0000001))
144 665c255d 2023-08-04 jrmu ((iterative-improve (lambda (guess)
145 665c255d 2023-08-04 jrmu (< (abs (- guess (f guess))) tolerance))
146 665c255d 2023-08-04 jrmu (lambda (guess)
147 665c255d 2023-08-04 jrmu (f guess))) guess)))
149 665c255d 2023-08-04 jrmu (test-case (fixed-point (lambda (x)
152 665c255d 2023-08-04 jrmu 0.73956720221)
