; Solutions by Alberto Tacchella to (some) exercises in the book
; "Structure and Interpretation of Computer Programs"
; by Abelson, Sussmann and Sussmann (2nd edition)
;
; Code is generally R5RS-compliant, with some mit-scheme specific extensions.
; Comments are minimal. Solutions are most probably not the optimal and/or
; most clever ones.
; Some procedures include a debug facility defined using "dotted-tail notation"
; If you invoke such procedures with any additional argument(s), some output
; useful for debugging purposes will be produced.
;
; This file contains code and solutions for Section 1.1.
;(define (square x) (* x x))
(define (sum-of-squares x y)
(+ (square x) (square y)))
; ex 1.3
(define (sum-sq-greatest-three a b c)
; note that it takes fewer conditionals to determine which of the three numbers
; is the smaller one, and then call sum-of-squares on the other two
(if (< a b)
(if (< c a)
(sum-of-squares a b)
(sum-of-squares b c))
(if (< c b)
(sum-of-squares a b)
(sum-of-squares a c))))
; square root by newton's method
(define (average x y)
(/ (+ x y) 2))
(define (sqrt-newton x)
; stops when squares differ by < 0.001
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess)
(average guess (/ x guess)))
(define (iter guess)
(if (good-enough? guess)
guess
(iter (improve guess))))
(if (< x 0)
(error "Negative argument: sqrt" x)
(iter 1.0)))
; ex 1.7
(define (sqrt-newton-imp x . debug)
; stops when relative change between guesses is < 0.001
(define (good-enough? old-guess new-guess)
(< (abs (- 1 (/ old-guess new-guess))) 0.001))
(define (improve guess)
(average guess (/ x guess)))
(define (iter old-guess new-guess)
(if (good-enough? old-guess new-guess)
new-guess
(begin
(cond ((not (null? debug)) (display new-guess)(display " ")))
(iter new-guess (improve new-guess)))))
(cond ((< x 0) (error "Negative argument: sqrt" x))
; here the case x=0 must be handled separately because
; the iterative process will not converge
((= x 0) 0)
(else (iter 0.0 1.0))))
(define (sqrt-newton-imp2 x . debug)
; stops when relative change between guesses is < 0.001 / |log x|
; the log x factor counts -roughly- the number of digits of x. This is done
; to improve the approximation for large values of x
(define (good-enough? old-guess new-guess)
(< (abs (- 1 (/ old-guess new-guess))) (/ 0.001 (abs (log x)))))
(define (improve guess)
(average guess (/ x guess)))
(define (iter old-guess new-guess)
(if (good-enough? old-guess new-guess)
new-guess
(begin
(cond ((not (null? debug)) (display new-guess)(display " ")))
(iter new-guess (improve new-guess)))))
(cond ((< x 0) (error "Negative argument: sqrt" x))
((= x 0) 0)
(else (iter 0.0 1.0))))
(define test-values '(2 773 45927 2841025 267903453 0 0.0001 0.00000407))
; ex 1.8
(define (cbrt-newton x . debug)
(define (good-enough? old-guess new-guess)
(< (abs (- 1 (/ old-guess new-guess))) (/ 0.001 (abs (log (abs x))))))
(define (improve guess)
(/ (+ (/ x (square guess)) (* 2 guess)) 3))
(define (iter old-guess new-guess)
(if (good-enough? old-guess new-guess)
new-guess
(begin
(cond ((not (null? debug)) (display new-guess)(display " ")))
(iter new-guess (improve new-guess)))))
(cond ((< x 0) (iter 0.0 -1.0))
((= x 0) 0)
(else (iter 0.0 1.0))))