SICP Exercise 1.45

exercise_one_fortyfive.scheme

(define tolerance 0.00001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
        next
	(try next))))
  (try first-guess))

(fixed-point cos 1.0)

;; find a solution to the equation
;; y = sin y + cos y
(fixed-point (lambda (y) (+ (sin y) (cos y)))
             1.0)


;; naively finding the fixed point of
;; \y -> x/y does not converge, 
(define (sqrt x)
  (fixed-point (lambda (y) (/ x y)) 1.0))

(sqrt 2); won't terminate

;; but this can be fixed by average damping

(define (average a b)
  (/ (+ a b) 2))

(define (average-damp f)
  (lambda (x) (average x (f x))))

(define (sqrt x)
  (fixed-point (average-damp
                (lambda (y) (/ x y)))
               1.0))

(sqrt 2) ; terminates

;; the same method works for finding cube
;; roots as fixed points of the
;; average-damped \y -> x/y^2

(define (cube-root x)
  (fixed-point (average-damp
                (lambda (y) (/ x (* y y))))
               1.0))

(cube-root 20)

(define (cube x)
  (* x x x))

(cube 2.7144158429928207)

;; y^4 = x or y = x / y^3
(define (fourth-root x)
  (fixed-point (average-damp
                (lambda (y) (/ x (cube y))))
               1.0))

(fourth-root 200)

;; but this can be fixed by average
;; damping the average damping
(define (fourth-root x)
  (fixed-point (average-damp
                (average-damp
                 (lambda (y) (/ x (cube y)))))
               1.0))

(fourth-root 200)

;; Do some experiments to determine how
;; many average damps are required to
;; compute nth roots as a fixed-point search
;;
;; Square roots y = x / y   , 1 AD
;; Cube roots   y = x / y^2 , 1 AD
;; Fourth roots y = x / y^3 , 2 AD
;; Fifth roots  y = x / y^4 , 2 AD

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

(define (fifth-root x)
  (fixed-point (average-damp
                (average-damp
                 (lambda (y) (/ x (fast-expt y 4)))))
               1.0))

(define (nth-root x n d)
  (fixed-point (average-damp
                (average-damp
                 (lambda (y) (/ x (fast-expt y (- n 1))))))
               1.0))

(define (repeated f n)
  (if (> n 1)
    (lambda (x)
      (f ((repeated f (- n 1)) x)))
    f))

(define (compose f g)
  (lambda (x)
    (g (f x))))

(define (repeated f n)
  (if (> n 1)
    (compose (repeated f (- n 1)) f)
    f))

(define (nth-root x n d)
  (fixed-point ((repeated average-damp d) 
                (lambda (y) (/ x (fast-expt y (- n 1)))))
               1.0))

;; Experimental Results
;; Root  Average Damps
;; 1     0
;; 2     1
;; 4     2
;; 8     3
;; 16    4

(define (nth-root x n)
  (fixed-point ((repeated average-damp (floor (/ (log n) (log 2))))
                (lambda (y) (/ x (fast-expt y (- n 1)))))
               1.0))