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 ;; Exercise 1.36. Modify fixed-point so that it prints the sequence of approximations it generates, using the newline and display primitives shown in exercise 1.22. 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.)
27 665c255d 2023-08-04 jrmu (define (fixed-point f first-guess)
28 665c255d 2023-08-04 jrmu (define (close-enough? v1 v2)
29 665c255d 2023-08-04 jrmu (< (abs (- v1 v2)) tolerance))
30 665c255d 2023-08-04 jrmu (define (try guess)
31 665c255d 2023-08-04 jrmu (display guess)
33 665c255d 2023-08-04 jrmu (let ((next (f guess)))
34 665c255d 2023-08-04 jrmu (if (close-enough? guess next)
35 665c255d 2023-08-04 jrmu (begin (display next)
37 665c255d 2023-08-04 jrmu (try next))))
39 665c255d 2023-08-04 jrmu (try first-guess))
41 665c255d 2023-08-04 jrmu (fixed-point (lambda (y) (+ (sin y) (cos y)))
44 665c255d 2023-08-04 jrmu (define (sqrt x)
45 665c255d 2023-08-04 jrmu (fixed-point (lambda (y) (average y (/ x y)))
48 665c255d 2023-08-04 jrmu (define (average x y)
49 665c255d 2023-08-04 jrmu (/ (+ x y) 2))
51 665c255d 2023-08-04 jrmu (define golden-ratio (fixed-point (lambda (x) (+ 1 (/ 1 x)))
54 665c255d 2023-08-04 jrmu (define (test-case actual expected)
55 665c255d 2023-08-04 jrmu (load-option 'format)
57 665c255d 2023-08-04 jrmu (format #t "Actual: ~A Expected: ~A" actual expected))
59 665c255d 2023-08-04 jrmu ;; (test-case golden-ratio (/ (+ 1.0 (sqrt 5.0)) 2.0))
61 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.)
65 665c255d 2023-08-04 jrmu (display "Finding solution to x^x = 1000 without average damping:")
66 665c255d 2023-08-04 jrmu (fixed-point (lambda (x) (/ (log 1000) (log x)))
68 665c255d 2023-08-04 jrmu ;; 35 iterations
71 665c255d 2023-08-04 jrmu (display "Finding solution to x^x = 1000 with average damping:")
72 665c255d 2023-08-04 jrmu (fixed-point (lambda (x) (average x (/ (log 1000) (log x))))
74 665c255d 2023-08-04 jrmu ;; 10 iterations
76 665c255d 2023-08-04 jrmu ;; Average damping helps it converge much faster!