Differences

This shows you the differences between two versions of the page.

--- exercise_1.45 [2009/03/07 09:28]
inimino created
+++ exercise_1.45 [2009/03/08 23:10] (current)
204.14.159.185
@@ Line 16: / Line 16: @@
 ====== Solutions ======
+<code scheme>(define tolerance 0.00001)
+(define (average a b) (/ (+ a b) 2))
+(define (fixed-point-damp-n f n first-guess)
+  (define (close-enough? v1 v2)
+    (< (abs (- v1 v2)) tolerance))
+  (define (average-damp f)
+    (lambda (x) (average x (f x))))
+  (define (try guess guesses-left)
+    (newline)
+    (display guess)
+    (let ((next (((repeated average-damp n) f) guess)))
+      (cond ((close-enough? guess next) next)
+	    ((= guesses-left 0) false)
+	    (else (try next (- guesses-left 1))))))
+  (try first-guess 1500))
+(define (pow x n)
+  (if (= n 0)
+      (* x (pow x (- n 1)))))
+(fixed-point-damp-n (lambda(y) (/ 27 (* y y))) 1 2.0)   ; 3rd root converges
+(fixed-point-damp-n (lambda(y) (/ 81 (* y y y))) 1 2.0) ; 4th root/1 damp does NOT
+(fixed-point-damp-n (lambda(y) (/ 81 (* y y y))) 2 2.0) ; 4th root/2 damp does
+(fixed-point-damp-n (lambda(y) (/ 81 (pow y 4))) 2 2.0) ; 5th rt/2 damp does
+(fixed-point-damp-n (lambda(y) (/ 81 (pow y 5))) 2 2.0) ; 6th rt/2 damp does
+(fixed-point-damp-n (lambda(y) (/ 81 (pow y 6))) 2 2.0) ; 7th rt/2 damp does
+(fixed-point-damp-n (lambda(y) (/ 81 (pow y 7))) 2 2.0) ; 8th rt/2 damp does NOT
+(fixed-point-damp-n (lambda(y) (/ 81 (pow y 7))) 3 2.0) ; 8th rt/3 damp does
+(fixed-point-damp-n (lambda(y) (/ 81 (pow y 14))) 3 2.0) ; 15th rt/3 damp does
+(fixed-point-damp-n (lambda(y) (/ 81 (pow y 15))) 3 2.0) ; 16th rt/3 damp does NOT
+(fixed-point-damp-n (lambda(y) (/ 81 (pow y 15))) 4 2.0) ; 16th rt/4 damp does
+; conclusion of experimentation use at least (floor (base-2-log n)) damps
+(define (nth-root x n)
+  (fixed-point-damp-n
+   (lambda (y) (/ x (pow y (- n 1))))
+   (floor (/ (log n) (log 2)))
+   (/ (log x) (log n) )))
+(nth-root 81 2)
+(nth-root 1296 4)
+(nth-root 12789452 16)
+(nth-root 127894523423422 16)
+(nth-root 127894523423422 17)
+(nth-root 127894523423422 17)
+(nth-root 1296422342342342342342324 123)
+(nth-root 1296342 1234)
+(nth-root 129 129)
+</code>