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 ;Once the interval size reaches TOLERANCE, simply approximate the area under the curve as the corresponding rectangle or trapezoid.
6 12687dd9 2023-08-04 jrmu ;TOLERANCE1 is for integrate-dc
7 12687dd9 2023-08-04 jrmu (define TOLERANCE1 0.0001)
9 12687dd9 2023-08-04 jrmu ;TOLERANCE2 is for integrate-adaptive
10 12687dd9 2023-08-04 jrmu (define TOLERANCE2 0.0000001)
12 12687dd9 2023-08-04 jrmu ;integrate-dc : (number -> number) number number -> number
13 12687dd9 2023-08-04 jrmu ;(integrate-divide and conquer)
14 12687dd9 2023-08-04 jrmu ;Given f, left, and right, use the divide-and-conquer generative recursion strategy to find the area under the curve. Given an interval, if the interval is small enough (compared to TOLERANCE1), we simply find the area of the interval (using a rectangle or trapezoid). Otherwise, we divide the interval into two pieces and sum the area under the curves of the resulting two integrals.
15 12687dd9 2023-08-04 jrmu ;ASSUMPTION : (> right left)
16 12687dd9 2023-08-04 jrmu ;Termination argument: Since each recursion involves an interval with half the width of the original interval, integrate-dc will eventually be applied to an interval less than the TOLERANCE1 and so terminate.
18 12687dd9 2023-08-04 jrmu (define (integrate-dc f left right)
19 12687dd9 2023-08-04 jrmu (local ((define midpoint (+ left
20 12687dd9 2023-08-04 jrmu (/ (- right left) 2))))
22 12687dd9 2023-08-04 jrmu [(not (> right left))
23 12687dd9 2023-08-04 jrmu (error 'integrate-dc "right endpoint must be greater than left endpoint")]
24 12687dd9 2023-08-04 jrmu [(<= (- right left) TOLERANCE1) (area-of-trapezoid f left right)]
25 12687dd9 2023-08-04 jrmu [else (+ (integrate-dc f left midpoint)
26 12687dd9 2023-08-04 jrmu (integrate-dc f midpoint right))])))
28 12687dd9 2023-08-04 jrmu ;area-of-rectangle : number number number -> number
29 12687dd9 2023-08-04 jrmu ;Given the left and right endpoints as well as the height, compute the area of the rectangle.
31 12687dd9 2023-08-04 jrmu (define (area-of-rectangle left right height)
32 12687dd9 2023-08-04 jrmu (* (- right left) height))
34 12687dd9 2023-08-04 jrmu ;area-of-trapezoid : (number -> number) number number -> number
35 12687dd9 2023-08-04 jrmu ;Given the function f, the left and right endpoints, compute the area of the trapezoid.
36 12687dd9 2023-08-04 jrmu (define (area-of-trapezoid f left right)
37 12687dd9 2023-08-04 jrmu (* (/ (+ (f left) (f right)) 2)
38 12687dd9 2023-08-04 jrmu (- right left)))
40 12687dd9 2023-08-04 jrmu ;integrate-adaptive :
41 12687dd9 2023-08-04 jrmu ;Given f, left, and right, integrate-adaptive uses the same strategy as integrate-dc except that it prematurely ends recursions if it notices that the difference between the trapezoid approximation of an interval versus the trapezoid approximation of the interval split in two is about the same.
43 12687dd9 2023-08-04 jrmu (define (integrate-adaptive f left right)
44 12687dd9 2023-08-04 jrmu (local ((define midpoint (+ left
45 12687dd9 2023-08-04 jrmu (/ (- right left) 2)))
46 12687dd9 2023-08-04 jrmu (define current-approx (area-of-trapezoid f left right)))
48 12687dd9 2023-08-04 jrmu [(not (> right left))
49 12687dd9 2023-08-04 jrmu (error 'integrate-adaptive "right endpoint must be greater than left endpoint")]
50 12687dd9 2023-08-04 jrmu [(< (- current-approx
51 12687dd9 2023-08-04 jrmu (+ (area-of-trapezoid f left midpoint)
52 12687dd9 2023-08-04 jrmu (area-of-trapezoid f midpoint right)))
53 12687dd9 2023-08-04 jrmu (* TOLERANCE2 (- right left)))
54 12687dd9 2023-08-04 jrmu current-approx]
55 12687dd9 2023-08-04 jrmu [(<= (- right left) TOLERANCE2) current-approx]
56 12687dd9 2023-08-04 jrmu [else (+ (integrate-adaptive f left midpoint)
57 12687dd9 2023-08-04 jrmu (integrate-adaptive f midpoint right))])))
59 12687dd9 2023-08-04 jrmu (time (integrate-adaptive (lambda (x) (sqr x)) -4 9))
60 12687dd9 2023-08-04 jrmu (time (integrate-dc (lambda (x) (sqr x)) -4 9))
