1 665c255d 2023-08-04 jrmu ;; (define (search f neg-point pos-point)
2 665c255d 2023-08-04 jrmu ;; (let ((midpoint (average neg-point pos-point)))
3 665c255d 2023-08-04 jrmu ;; (if (close-enough? neg-point pos-point)
5 665c255d 2023-08-04 jrmu ;; (let ((test-value (f midpoint)))
6 665c255d 2023-08-04 jrmu ;; (cond ((positive? test-value)
7 665c255d 2023-08-04 jrmu ;; (search f neg-point midpoint))
8 665c255d 2023-08-04 jrmu ;; ((negative? test-value)
9 665c255d 2023-08-04 jrmu ;; (search f midpoint pos-point))
10 665c255d 2023-08-04 jrmu ;; (else midpoint))))))
11 665c255d 2023-08-04 jrmu ;; (define (close-enough? x y)
12 665c255d 2023-08-04 jrmu ;; (< (abs (- x y)) 0.001))
14 665c255d 2023-08-04 jrmu ;; (define (half-interval-method f a b)
15 665c255d 2023-08-04 jrmu ;; (let ((a-value (f a))
16 665c255d 2023-08-04 jrmu ;; (b-value (f b)))
17 665c255d 2023-08-04 jrmu ;; (cond ((and (negative? a-value) (positive? b-value))
18 665c255d 2023-08-04 jrmu ;; (search f a b))
19 665c255d 2023-08-04 jrmu ;; ((and (negative? b-value) (positive? a-value))
20 665c255d 2023-08-04 jrmu ;; (search f b a))
22 665c255d 2023-08-04 jrmu ;; (error "Values are not of opposite sign" a b)))))
23 665c255d 2023-08-04 jrmu ;; (define tolerance 0.00001)
25 665c255d 2023-08-04 jrmu ;; (define (fixed-point f first-guess)
26 665c255d 2023-08-04 jrmu ;; (define (close-enough? v1 v2)
27 665c255d 2023-08-04 jrmu ;; (< (abs (- v1 v2)) tolerance))
28 665c255d 2023-08-04 jrmu ;; (define (try guess)
29 665c255d 2023-08-04 jrmu ;; ;; (display guess)
30 665c255d 2023-08-04 jrmu ;; ;; (newline)
31 665c255d 2023-08-04 jrmu ;; (let ((next (f guess)))
32 665c255d 2023-08-04 jrmu ;; (if (close-enough? guess next)
33 665c255d 2023-08-04 jrmu ;; ;; (begin (display next)
36 665c255d 2023-08-04 jrmu ;; (try next))))
37 665c255d 2023-08-04 jrmu ;; ;; (newline)
38 665c255d 2023-08-04 jrmu ;; (try first-guess))
40 665c255d 2023-08-04 jrmu ;;(fixed-point (lambda (y) (+ (sin y) (cos y)))
43 665c255d 2023-08-04 jrmu ;; (define (sqrt x)
44 665c255d 2023-08-04 jrmu ;; (fixed-point (lambda (y) (average y (/ x y)))
47 665c255d 2023-08-04 jrmu ;; (define (average x y)
48 665c255d 2023-08-04 jrmu ;; (/ (+ x y) 2))
50 665c255d 2023-08-04 jrmu (define (test-case actual expected)
51 665c255d 2023-08-04 jrmu (load-option 'format)
53 665c255d 2023-08-04 jrmu (format #t "Actual: ~A Expected: ~A" actual expected))
55 665c255d 2023-08-04 jrmu ;; (test-case golden-ratio (/ (+ 1.0 (sqrt 5.0)) 2.0))
57 665c255d 2023-08-04 jrmu ;; Then find a solution to x^x = 1000 by finding a fixed point of x-->log(1000)/log(x). (Use Scheme's primitive log procedure, which computes natural logarithms.) Compare the number of steps this takes with and without average damping. (Note that you cannot start fixed-point with a guess of 1, as this would cause division by log(1) = 0.)
59 665c255d 2023-08-04 jrmu ;; (define golden-ratio (fixed-point (lambda (x) (+ 1 (/ 1 x)))
62 665c255d 2023-08-04 jrmu ;; (newline)
63 665c255d 2023-08-04 jrmu ;; (newline)
64 665c255d 2023-08-04 jrmu ;; (display "Finding solution to x^x = 1000 without average damping:")
65 665c255d 2023-08-04 jrmu ;; (fixed-point (lambda (x) (/ (log 1000) (log x)))
67 665c255d 2023-08-04 jrmu ;; 35 iterations
69 665c255d 2023-08-04 jrmu ;; (newline)
70 665c255d 2023-08-04 jrmu ;; (display "Finding solution to x^x = 1000 with average damping:")
71 665c255d 2023-08-04 jrmu ;; (fixed-point (lambda (x) (average x (/ (log 1000) (log x))))
73 665c255d 2023-08-04 jrmu ;; 10 iterations
75 665c255d 2023-08-04 jrmu ;; Average damping helps it converge much faster!
77 665c255d 2023-08-04 jrmu ;; Suppose that n and d are procedures of one argument (the term index i) that return the Ni and Di of the terms of the continued fraction. Define a procedure cont-frac such that evaluating (cont-frac n d k) computes the value of the k-term finite continued fraction. Check your procedure by approximating 1/golden-ratio using
79 665c255d 2023-08-04 jrmu ;; (define (cont-frac n d k)
80 665c255d 2023-08-04 jrmu ;; (define (cont-frac-rec i)
81 665c255d 2023-08-04 jrmu ;; (if (> i k)
83 665c255d 2023-08-04 jrmu ;; (/ (n i) (+ (d i) (cont-frac-rec (1+ i))))))
84 665c255d 2023-08-04 jrmu ;; (cont-frac-rec 1))
86 665c255d 2023-08-04 jrmu ;; (test-case (cont-frac (lambda (i) 1.0)
87 665c255d 2023-08-04 jrmu ;; (lambda (i) 1.0)
89 665c255d 2023-08-04 jrmu ;; (/ 1.0 (/ (+ 1.0 (sqrt 5)) 2.0)))
91 665c255d 2023-08-04 jrmu ;; (test-case (cont-frac (lambda (i) 1.0)
92 665c255d 2023-08-04 jrmu ;; (lambda (i) 1.0)
94 665c255d 2023-08-04 jrmu ;; (/ 1.0 (/ (+ 1.0 (sqrt 5)) 2.0)))
96 665c255d 2023-08-04 jrmu ;; (test-case (cont-frac (lambda (i) 1.0)
97 665c255d 2023-08-04 jrmu ;; (lambda (i) 1.0)
99 665c255d 2023-08-04 jrmu ;; (/ 1.0 (/ (+ 1.0 (sqrt 5)) 2.0)))
101 665c255d 2023-08-04 jrmu ;; for successive values of k. How large must you make k in order to get an approximation that is accurate to 4 decimal places?
103 665c255d 2023-08-04 jrmu ;; k has to be somewhere between 10-100
105 665c255d 2023-08-04 jrmu ;; b. If your cont-frac procedure generates a recursive process, write one that generates an iterative process. If it generates an iterative process, write one that generates a recursive process.
107 665c255d 2023-08-04 jrmu (define (cont-frac-iter n d k)
108 665c255d 2023-08-04 jrmu (define (iter i result)
109 665c255d 2023-08-04 jrmu (if (= i 0)
111 665c255d 2023-08-04 jrmu (iter (- i 1) (/ (n i) (+ (d i) result)))))
112 665c255d 2023-08-04 jrmu (iter k 0.0))
114 665c255d 2023-08-04 jrmu ;; (test-case (cont-frac-iter (lambda (i) 1.0)
115 665c255d 2023-08-04 jrmu ;; (lambda (i) 1.0)
117 665c255d 2023-08-04 jrmu ;; (/ 1.0 (/ (+ 1.0 (sqrt 5)) 2.0)))
119 665c255d 2023-08-04 jrmu (test-case (+ 2.0
120 665c255d 2023-08-04 jrmu (cont-frac-iter (lambda (i) 1)
121 665c255d 2023-08-04 jrmu (lambda (i) (if (= (remainder i 3) 2)
122 665c255d 2023-08-04 jrmu (* (/ (+ i 1) 3) 2)
125 665c255d 2023-08-04 jrmu 2.7182818284590452353602874)
