1 ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 ;; about the language level of this file in a form that our tools can easily process.
3 #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 ;A table is a function that consumes only natural numbers between 0 (inclusive) and VL (exclusive) and returns a number.
5 ;
6 ;Formally, a table is a function
7 ;g : N[>=0 and <= (- VL 1)] -> number
8 ;
9 ;The root of a table is the value x such that (g x) is the closest to 0.
10 ;
11 ;find-root-linear : (N -> number) N -> N
12 ;Given a-table (table) and index i, find the root of a table.  find-root-linear finds the root using structural induction (linear search).
13 
14 (define (find-root-linear a-table i)
15   (cond
16     [(zero? i) i]
17     [else (local ((define a-table-i (a-table i))
18                   (define root-of-rest (find-root-linear a-table (sub1 i))))
19             (cond
20               [(<= (abs a-table-i)
21                    (abs (a-table root-of-rest))) i]
22               [else root-of-rest]))]))
23 
24 (define (t x)
25   (+ (+ (* 3 (sin x)) (* 5 x))
26      (* -1 x (sqrt x))
27      3))
28 
29 ;find-root-discrete : (N -> number) N N -> N
30 ;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 ;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 ;midpoint : Given left and right, determine the midpoint rounded to the nearest integer.
33 ;No assumption about a-table being monotonic
34 
35 
36 
37 (define (find-root-discrete2 a-table left right)
38   (cond
39     [(= (- right left) 1) 
40      (cond
41        [(<= (abs (a-table left))
42             (abs (a-table right))) left]
43        [else right])]
44     [else (local ((define midpoint
45                     (round (+ left
46                               (/ (- right left) 2))))
47                   (define left-side-root (find-root-discrete2 a-table left midpoint))
48                   (define right-side-root (find-root-discrete2 a-table midpoint right)))
49             (cond              
50               [(<= (abs (a-table left-side-root))
51                    (abs (a-table right-side-root))) left-side-root]
52               [else right-side-root]))]))
53 
54 
55 
56 ;find-root-discrete : (N -> number) N N -> N
57 ;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 ;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 ;midpoint : Given left and right, determine the midpoint rounded to the nearest integer.
60 ;ASSUMPTION : a-table is monotonic increasing or monotonic decreasing.
61 
62 (define (find-root-discrete a-table left right)
63   (local ((define midpoint
64             (round (+ left
65                       (/ (- right left) 2)))))
66     (cond
67       [(= (- right left) 1) 
68        (cond
69          [(<= (abs (a-table left))
70               (abs (a-table right))) left]
71          [else right])]
72       [(or (<= (a-table left) 0 (a-table midpoint))
73            (<= (a-table midpoint) 0 (a-table left))) (find-root-discrete a-table left midpoint)]
74       [else (find-root-discrete a-table midpoint right)])))
75 
76 (time (find-root-linear t 30000))
77 (time (find-root-discrete2 t 0 100000))
78 (time (find-root-discrete t 0 100000))
79 
80 find-root-linear requires 1024 applications whereas find-root-discrete requires 10 applications