Skip to content

Instantly share code, notes, and snippets.

@youngnh
Created April 25, 2014 13:35
Show Gist options
  • Save youngnh/11289792 to your computer and use it in GitHub Desktop.
Save youngnh/11289792 to your computer and use it in GitHub Desktop.
SICP Exercise 1.45
(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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment