1 12687dd9 2023-08-04 jrmu ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 12687dd9 2023-08-04 jrmu ;; about the language level of this file in a form that our tools can easily process.
3 12687dd9 2023-08-04 jrmu #reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname |27.3|) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))
4 12687dd9 2023-08-04 jrmu (define TOLERANCE 0.000000001)
6 12687dd9 2023-08-04 jrmu ;; poly : number -> number
7 12687dd9 2023-08-04 jrmu (define (poly x)
8 12687dd9 2023-08-04 jrmu (* (- x 2) (- x 4)))
10 12687dd9 2023-08-04 jrmu ;midpoint : number number -> number
11 12687dd9 2023-08-04 jrmu ;Returns the average of the two numbers.
12 12687dd9 2023-08-04 jrmu (define (midpoint n1 n2)
13 12687dd9 2023-08-04 jrmu (/ (+ n1 n2) 2))
15 12687dd9 2023-08-04 jrmu ;find-root : (number -> number) number number -> number
16 12687dd9 2023-08-04 jrmu ;Given f, left and right, approximate a root by using a binary search. find-root returns the left interval once the interval size is less than tolerance. find-root uses generative recursion to find the root--it splits the interval in half and finds the root for one half of the interval.
17 12687dd9 2023-08-04 jrmu ;Assume that (<= (f left) 0 (f right)) or (<= (f right) 0 (f left)).
18 12687dd9 2023-08-04 jrmu ;Termination argument: Each interval is half the size of the previous interval. Hence, the nth recursive call has an interval of initial * (1/2)^n, where initial is the size of the initial interval. As n-> infinity, the interval approaches zero, which implies that this function must terminate for any value of tolerance greater than zero.
20 12687dd9 2023-08-04 jrmu (define (find-root f left right)
21 12687dd9 2023-08-04 jrmu (local ((define mid (/ (+ left right) 2))
22 12687dd9 2023-08-04 jrmu (define f-mid (f mid)))
24 12687dd9 2023-08-04 jrmu [(<= (- right left) TOLERANCE) left]
25 12687dd9 2023-08-04 jrmu [(or (<= (f left) 0 f-mid)
26 12687dd9 2023-08-04 jrmu (>= (f left) 0 f-mid)) (find-root f left mid)]
27 12687dd9 2023-08-04 jrmu [else (find-root f mid right)])))
31 12687dd9 2023-08-04 jrmu (define (find-root f left right)
32 12687dd9 2023-08-04 jrmu (local ((define mid (/ (+ left right) 2)))
34 12687dd9 2023-08-04 jrmu [(<= (- right left) TOLERANCE) left]
35 12687dd9 2023-08-04 jrmu [(or (<= (f left) 0 (f mid))
36 12687dd9 2023-08-04 jrmu (>= (f left) 0 (f mid))) (find-root f left mid)]
37 12687dd9 2023-08-04 jrmu [(or (<= (f right) 0 (f mid))
38 12687dd9 2023-08-04 jrmu (>= (f right) 0 (f mid))) (find-root f mid right)]
39 12687dd9 2023-08-04 jrmu [else (error 'find-root "not guaranteed root")])))
43 12687dd9 2023-08-04 jrmu ;find-root-aux : (number -> number) number number number number -> number
44 12687dd9 2023-08-04 jrmu ;Same as find-root except it takes in two more arguments, f-left and f-right, in order to avoid calculating (f mid) twice.
46 12687dd9 2023-08-04 jrmu (define (find-root-aux f left right f-left f-right)
47 12687dd9 2023-08-04 jrmu (local ((define mid (/ (+ left right) 2))
48 12687dd9 2023-08-04 jrmu (define f-mid (f mid)))
50 12687dd9 2023-08-04 jrmu [(<= (- right left) TOLERANCE) left]
51 12687dd9 2023-08-04 jrmu [(or (<= f-left 0 f-mid)
52 12687dd9 2023-08-04 jrmu (>= f-left 0 f-mid)) (find-root-aux f left mid f-left f-mid)]
53 12687dd9 2023-08-04 jrmu [else (find-root-aux f mid right f-mid f-right)])))
55 12687dd9 2023-08-04 jrmu ;find-root-aux : (number -> number) number number -> number
56 12687dd9 2023-08-04 jrmu ;Same as find-root except it avoid calculating (f mid) twice to speed up calculations.
58 12687dd9 2023-08-04 jrmu (define (find-root2 f left right)
59 12687dd9 2023-08-04 jrmu (find-root-aux f left right (f left) (f right)))
61 12687dd9 2023-08-04 jrmu (define (poly2 x)
62 12687dd9 2023-08-04 jrmu (+ (- (log (+ (* (expt x 3) (exp x))
64 12687dd9 2023-08-04 jrmu (exp (* x (log x))))))) (abs x))
65 12687dd9 2023-08-04 jrmu (- (+ (expt 2 x)
66 12687dd9 2023-08-04 jrmu (expt 2 (sin x)))
67 12687dd9 2023-08-04 jrmu (/ (expt x x) (+ x 3)))))
