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 ;Once the interval size reaches TOLERANCE, simply approximate the area under the curve as the corresponding rectangle or trapezoid.
5 
6 ;TOLERANCE1 is for integrate-dc
7 (define TOLERANCE1 0.0001)
8 
9 ;TOLERANCE2 is for integrate-adaptive
10 (define TOLERANCE2 0.0000001)
11 
12 ;integrate-dc  : (number -> number) number number -> number
13 ;(integrate-divide and conquer)
14 ;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 ;ASSUMPTION : (> right left)
16 ;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.
17 
18 (define (integrate-dc f left right)
19   (local ((define midpoint (+ left
20                               (/ (- right left) 2))))
21     (cond
22       [(not (> right left))
23        (error 'integrate-dc "right endpoint must be greater than left endpoint")]
24       [(<= (- right left) TOLERANCE1) (area-of-trapezoid f left right)]
25       [else (+ (integrate-dc f left midpoint)
26                (integrate-dc f midpoint right))])))
27 
28 ;area-of-rectangle : number number number -> number
29 ;Given the left and right endpoints as well as the height, compute the area of the rectangle.
30 
31 (define (area-of-rectangle left right height)
32   (* (- right left) height))
33 
34 ;area-of-trapezoid : (number -> number) number number -> number
35 ;Given the function f, the left and right endpoints, compute the area of the trapezoid.
36 (define (area-of-trapezoid f left right)
37   (* (/ (+ (f left) (f right)) 2)
38      (- right left)))
39 
40 ;integrate-adaptive : 
41 ;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.
42 
43 (define (integrate-adaptive f left right)
44   (local ((define midpoint (+ left
45                               (/ (- right left) 2)))
46           (define current-approx (area-of-trapezoid f left right)))
47     (cond
48       [(not (> right left))
49        (error 'integrate-adaptive "right endpoint must be greater than left endpoint")]
50       [(< (- current-approx 
51              (+ (area-of-trapezoid f left midpoint)
52                 (area-of-trapezoid f midpoint right)))
53           (* TOLERANCE2 (- right left)))
54        current-approx]
55       [(<= (- right left) TOLERANCE2) current-approx]
56       [else (+ (integrate-adaptive f left midpoint)
57                (integrate-adaptive f midpoint right))])))
58 
59 (time (integrate-adaptive (lambda (x) (sqr x)) -4 9))
60 (time (integrate-dc (lambda (x) (sqr x)) -4 9))