1 ;; (define tolerance 0.0000001)
2 ;; (define (fixed-point f first-guess)
3 ;;   (define (close-enough? v1 v2)
4 ;;     (< (abs (- v1 v2)) tolerance))
5 ;;   (define (try guess)
6 ;;     (let ((next (f guess)))
7 ;;       (if (close-enough? guess next)
8 ;; 	  next
9 ;; 	  (try next))))
10 ;;   (try first-guess))
11 
12 (define (average x y)
13   (/ (+ x y) 2.0))
14 ;; (define (average-damp f)
15 ;;   (lambda (x) (average x (f x))))
16 ;; (define (fixed-point-of-transform g transform guess)
17 ;;   (fixed-point (transform g) guess))
18 ;; (define (sqrt x)
19 ;;   (fixed-point-of-transform (lambda (y) (/ x y))
20 ;; 			    average-damp
21 ;; 			    1.0))
22 ;; (define (cube-root x)
23 ;;   (fixed-point-of-transform (lambda (y) (/ x (square y)))
24 ;; 			    average-damp
25 ;; 			    1.0))
26 
27 ;; (define (compose f g)
28 ;;   (lambda (x)
29 ;;     (f (g x))))
30 
31 (define (test-case actual expected)
32   (load-option 'format)
33   (newline)
34   (format #t "Actual: ~A Expected: ~A" actual expected))
35 
36 (define (square x) (* x x))
37 ;; (define (inc x) (1+ x))
38 ;; (test-case ((compose square inc) 6) 49)
39 
40 ;; (define (repeated f n)
41 ;;   (if (= n 0)
42 ;;       (lambda (x) x)
43 ;;       (compose f (repeated f (- n 1)))))
44 
45 ;; (test-case ((repeated square 2) 5) 625)
46 ;; (test-case (cube-root 5) 1.70997594668)
47 
48 
49 ;; 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. 
50 
51 ;; (define dx 0.01)
52 
53 ;; (define (smooth f)
54 ;;   (lambda (x)
55 ;;     (/ (+ (f x) 
56 ;; 	  (f (+ x dx))
57 ;; 	  (f (- x dx)))
58 ;;        3.0)))
59 ;; (define (n-fold-smooth f n)
60 ;;   ((repeated smooth n) f))
61 
62 ;; 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. 
63 
64 ;; (define (fast-expt b n)
65 ;;   (cond ((= n 0) 1)
66 ;; 	((even? n) (square (fast-expt b (/ n 2))))
67 ;; 	(else (* b (fast-expt b (- n 1))))))
68 
69 
70 ;; (define (quartic-root x)
71 ;;   (fixed-point-of-transform (lambda (y) (/ x (cube y)))
72 ;; 			    (repeated average-damp 2)
73 ;; 			    1.0))
74 ;; (define (nth-root-test x n d)
75 ;;   (fixed-point-of-transform (lambda (y) (/ x (expt y (- n 1))))
76 ;; 			    (repeated average-damp d)
77 ;; 			    1.0))
78 
79 ;; (test-case (nth-root-test 19 1 0) 19)
80 ;; (test-case (nth-root-test 19 2 1) 4.35889894)
81 ;; (test-case (nth-root-test 19 3 1) 2.66840165)
82 ;; (test-case (nth-root-test 19 4 2) 2.08779763)
83 ;; (test-case (nth-root-test 19 5 2) 1.80198313)
84 ;; (test-case (nth-root-test 19 6 2) 1.6335243)
85 ;; (test-case (nth-root-test 199 7 2) 2.13013723)
86 ;; (test-case (nth-root-test 199 8 3) 1.93801277)
87 ;; (test-case (nth-root-test 199 9 3) 1.80064508)
88 ;; (test-case (nth-root-test 199 10 3) 1.69779522)
89 ;; (test-case (nth-root-test 19999 11 3) 2.46037187)
90 ;; (test-case (nth-root-test 19999 12 3) 2.28253453)
91 ;; (test-case (nth-root-test 19999 13 3) 2.14213477)
92 ;; (test-case (nth-root-test 19999 14 3) 2.02868621)
93 ;; (test-case (nth-root-test 19999 15 3) 1.93523578)
94 ;; (test-case (nth-root-test 1999999 16 4) 2.47636331)
95 ;; (test-case (nth-root-test 1999999 17 4) 2.34773357)
96 
97 
98 ;; At first, my conclusion: average damp = sqrt(n), rounded down -- EXCEPT for 8...why is that?
99 ;; Maybe: 2^average damp = n
100 
101 ;; (define (nth-root x n)
102 ;;   (fixed-point-of-transform (lambda (y) (/ x (expt y (- n 1))))
103 ;; 			    (repeated average-damp (truncate (/ (log n) (log 2))))
104 ;; 			    1.0))
105 
106 ;; (test-case (nth-root 19 1) 19)
107 ;; (test-case (nth-root 19 2) 4.35889894)
108 ;; (test-case (nth-root 19 3) 2.66840165)
109 ;; (test-case (nth-root 19 4) 2.08779763)
110 ;; (test-case (nth-root 19 5) 1.80198313)
111 ;; (test-case (nth-root 19 6) 1.6335243)
112 ;; (test-case (nth-root 199 7) 2.13013723)
113 ;; (test-case (nth-root 199 8) 1.93801277)
114 ;; (test-case (nth-root 199 9) 1.80064508)
115 ;; (test-case (nth-root 199 10) 1.69779522)
116 ;; (test-case (nth-root 19999 11) 2.46037187)
117 ;; (test-case (nth-root 19999 12) 2.28253453)
118 ;; (test-case (nth-root 19999 13) 2.14213477)
119 ;; (test-case (nth-root 19999 14) 2.02868621)
120 ;; (test-case (nth-root 19999 15) 1.93523578)
121 ;; (test-case (nth-root 1999999 16) 2.47636331)
122 ;; (test-case (nth-root 1999999 17) 2.34773357)
123 
124 ;; 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. 
125 
126 (define (iterative-improve good-enough? improve)
127   (define (iter guess)
128     (if (good-enough? guess)
129 	guess
130 	(iter (improve guess))))
131   iter)
132 
133 (define (sqrt guess x)
134   ((iterative-improve (lambda (guess)
135 			(< (abs (- (square guess) x)) 0.001))
136 		      (lambda (guess)
137 			(average guess (/ x guess)))) guess))
138 
139 
140 (test-case (sqrt 2.2 5) 2.23606798)
141 
142 (define (fixed-point f guess)
143   (let ((tolerance 0.0000001))
144     ((iterative-improve (lambda (guess)
145 			  (< (abs (- guess (f guess))) tolerance))
146 			(lambda (guess)
147 			  (f guess))) guess)))
148 
149 (test-case (fixed-point (lambda (x)
150 			  (cos x))
151 			1)
152 	   0.73956720221)
153 
154