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 ;A table is a function that consumes only natural numbers between 0 (inclusive) and VL (exclusive) and returns a number.
6 12687dd9 2023-08-04 jrmu ;Formally, a table is a function
7 12687dd9 2023-08-04 jrmu ;g : N[>=0 and <= (- VL 1)] -> number
9 12687dd9 2023-08-04 jrmu ;The root of a table is the value x such that (g x) is the closest to 0.
11 12687dd9 2023-08-04 jrmu ;find-root-linear : (N -> number) N -> N
12 12687dd9 2023-08-04 jrmu ;Given a-table (table) and index i, find the root of a table. find-root-linear finds the root using structural induction (linear search).
14 12687dd9 2023-08-04 jrmu (define (find-root-linear a-table i)
16 12687dd9 2023-08-04 jrmu [(zero? i) i]
17 12687dd9 2023-08-04 jrmu [else (local ((define a-table-i (a-table i))
18 12687dd9 2023-08-04 jrmu (define root-of-rest (find-root-linear a-table (sub1 i))))
20 12687dd9 2023-08-04 jrmu [(<= (abs a-table-i)
21 12687dd9 2023-08-04 jrmu (abs (a-table root-of-rest))) i]
22 12687dd9 2023-08-04 jrmu [else root-of-rest]))]))
24 12687dd9 2023-08-04 jrmu (define (t x)
25 12687dd9 2023-08-04 jrmu (+ (+ (* 3 (sin x)) (* 5 x))
26 12687dd9 2023-08-04 jrmu (* -1 x (sqrt x))
29 12687dd9 2023-08-04 jrmu ;find-root-discrete : (N -> number) N N -> N
30 12687dd9 2023-08-04 jrmu ;Given a-table, left, and right, find a root of the table using binary search generative recursion. If there are multiple roots, only the root closest to zero is returned.
31 12687dd9 2023-08-04 jrmu ;Termination Argument: The interval of find-root-discrete decreases by half each time until the interval size is only 1. Once this occurs, find-root-discrete either returns the left or the right index as the root. Hence, find-root-discrete must terminate.
32 12687dd9 2023-08-04 jrmu ;midpoint : Given left and right, determine the midpoint rounded to the nearest integer.
33 12687dd9 2023-08-04 jrmu ;No assumption about a-table being monotonic
37 12687dd9 2023-08-04 jrmu (define (find-root-discrete2 a-table left right)
39 12687dd9 2023-08-04 jrmu [(= (- right left) 1)
41 12687dd9 2023-08-04 jrmu [(<= (abs (a-table left))
42 12687dd9 2023-08-04 jrmu (abs (a-table right))) left]
43 12687dd9 2023-08-04 jrmu [else right])]
44 12687dd9 2023-08-04 jrmu [else (local ((define midpoint
45 12687dd9 2023-08-04 jrmu (round (+ left
46 12687dd9 2023-08-04 jrmu (/ (- right left) 2))))
47 12687dd9 2023-08-04 jrmu (define left-side-root (find-root-discrete2 a-table left midpoint))
48 12687dd9 2023-08-04 jrmu (define right-side-root (find-root-discrete2 a-table midpoint right)))
50 12687dd9 2023-08-04 jrmu [(<= (abs (a-table left-side-root))
51 12687dd9 2023-08-04 jrmu (abs (a-table right-side-root))) left-side-root]
52 12687dd9 2023-08-04 jrmu [else right-side-root]))]))
56 12687dd9 2023-08-04 jrmu ;find-root-discrete : (N -> number) N N -> N
57 12687dd9 2023-08-04 jrmu ;Given a-table, left, and right, find a root of the table using binary search generative recursion. If there are multiple roots, only the root closest to zero is returned.
58 12687dd9 2023-08-04 jrmu ;Termination Argument: The interval of find-root-discrete decreases by half each time until the interval size is only 1. Once this occurs, find-root-discrete either returns the left or the right index as the root. Hence, find-root-discrete must terminate.
59 12687dd9 2023-08-04 jrmu ;midpoint : Given left and right, determine the midpoint rounded to the nearest integer.
60 12687dd9 2023-08-04 jrmu ;ASSUMPTION : a-table is monotonic increasing or monotonic decreasing.
62 12687dd9 2023-08-04 jrmu (define (find-root-discrete a-table left right)
63 12687dd9 2023-08-04 jrmu (local ((define midpoint
64 12687dd9 2023-08-04 jrmu (round (+ left
65 12687dd9 2023-08-04 jrmu (/ (- right left) 2)))))
67 12687dd9 2023-08-04 jrmu [(= (- right left) 1)
69 12687dd9 2023-08-04 jrmu [(<= (abs (a-table left))
70 12687dd9 2023-08-04 jrmu (abs (a-table right))) left]
71 12687dd9 2023-08-04 jrmu [else right])]
72 12687dd9 2023-08-04 jrmu [(or (<= (a-table left) 0 (a-table midpoint))
73 12687dd9 2023-08-04 jrmu (<= (a-table midpoint) 0 (a-table left))) (find-root-discrete a-table left midpoint)]
74 12687dd9 2023-08-04 jrmu [else (find-root-discrete a-table midpoint right)])))
76 12687dd9 2023-08-04 jrmu (time (find-root-linear t 30000))
77 12687dd9 2023-08-04 jrmu (time (find-root-discrete2 t 0 100000))
78 12687dd9 2023-08-04 jrmu (time (find-root-discrete t 0 100000))
80 12687dd9 2023-08-04 jrmu find-root-linear requires 1024 applications whereas find-root-discrete requires 10 applications
