Structure and Interpretation of Computer Programs - Section 1.3.3 Procedures as General Methods

root-of-an-equation.scm

; Calculate the root of an equation using numerical computation
; (scheme is hard to write :(
; 2022-01-23
; Yihang Wang <wangyihanger@gmail.com>

(define (same-sign? a b) (or (and (>= a 0) (>= b 0)) (and (<= a 0) (<= b 0))))
(define (average a b) (/ (+ a b) 2))
(define (abs x) (cond
    ((< x 0) (- x))
    ((= x 0) 0)
    ((> x 0) x)
))
(define (find-root f a b t)
    (define (good-enough? a b t) (< (abs (- b a)) t))
    (define (improve-l f a b) (if (same-sign? (f a) (f (average a b))) (average a b) a))
    (define (improve-r f a b) (if (same-sign? (f b) (f (average a b))) (average a b) b))
    (define (has-root? f a b) (not (same-sign? (f a) (f b))))
    (define (find-root-iter f a b t)
        (if (has-root? f a b)
            (if (good-enough? a b t)
                (average a b)
                (find-root-iter f (improve-l f a b) (improve-r f a b) t)
            )
            (error "no root between [a, b]")
        )
    )
    (find-root-iter f a b t)
)

; f(x) = 2x^2 + 4x - 100
(define (f x)
    (+  
        (* 2 x x)
        (* 4 x)
        (- 100)
    )
)

; f(x) = x^2 - 2
; the root of equation f(x) = 0 is sqrt(2)
(define (sqrt2 x)
    (- (* x x) 2)
)

; sqrt2(1) = -1 < 0 and sqrt2(2) = 2 > 0
; expected output: ";Value: 1.41455078125"
(exact->inexact (find-root sqrt2 1 2 0.001))

; f(1) < 0 and f(10) > 0
; expected output: ";Value: 6.141326904296875"
(exact->inexact (find-root f 1 10 0.001))

; f(10) > 0 and f(11) > 0
; expected output: ";no root between [a, b]"
(exact->inexact (find-root f 10 11 0.001))

; calc pi, cause sin(pi) = 0, the root of the equation is pi. 
; sin(1) > 0 and sin(5) < 0
; expected output: ";Value: 3.1415926536137704"
(exact->inexact (find-root sin 1 5 0.0000000001))