youngnh · April 25, 2014 13:35 · Apr 25, 2014
diff --git a/exercise_one_fortyfive.scheme b/exercise_one_fortyfive.scheme
@@ -0,0 +1,135 @@
+
+(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))
No results found