## Blob

1 ;; The first three lines of this file were inserted by DrScheme. They record metadata2 ;; 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 function7 ;g : N[>=0 and <= (- VL 1)] -> number8 ;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 -> N12 ;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 (define (find-root-linear a-table i)15 (cond16 [(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 (cond20 [(<= (abs a-table-i)21 (abs (a-table root-of-rest))) i]22 [else root-of-rest]))]))24 (define (t x)25 (+ (+ (* 3 (sin x)) (* 5 x))26 (* -1 x (sqrt x))27 3))29 ;find-root-discrete : (N -> number) N N -> N30 ;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 monotonic37 (define (find-root-discrete2 a-table left right)38 (cond39 [(= (- right left) 1)40 (cond41 [(<= (abs (a-table left))42 (abs (a-table right))) left]43 [else right])]44 [else (local ((define midpoint45 (round (+ left46 (/ (- 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 (cond50 [(<= (abs (a-table left-side-root))51 (abs (a-table right-side-root))) left-side-root]52 [else right-side-root]))]))56 ;find-root-discrete : (N -> number) N N -> N57 ;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.62 (define (find-root-discrete a-table left right)63 (local ((define midpoint64 (round (+ left65 (/ (- right left) 2)))))66 (cond67 [(= (- right left) 1)68 (cond69 [(<= (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)])))76 (time (find-root-linear t 30000))77 (time (find-root-discrete2 t 0 100000))78 (time (find-root-discrete t 0 100000))80 find-root-linear requires 1024 applications whereas find-root-discrete requires 10 applications