sicp-ex-1.8


The solution presented here is based on the solution for sicp-ex-1.7 and, similarly, uses the alternative strategy for the good-enough? predicate.

  
 ;; ex 1.8. Based on the solution of ex 1.7. 
  
 (define (square x) (* x x)) 
  
 (define (cube-root-iter guess prev-guess x) 
   (if (good-enough? guess prev-guess) 
       guess 
       (cube-root-iter (improve guess x) guess x))) 
  
 (define (improve guess x) 
   (average3 (/ x (square guess)) guess guess)) 
  
 (define (average3 x y z) 
   (/ (+ x y z) 3)) 
  
 ;; Stop when the difference is less than 1/1000th of the guess 
 (define (good-enough? guess prev-guess) 
   (< (abs (- guess prev-guess)) (abs (* guess 0.001)))) 
  
 (define (cube-root x) 
   (cube-root-iter 1.0 0.0 x)) 
  
 ;; Testing 
 (cube-root 1) 
 (cube-root -8) 
 (cube-root 27) 
 (cube-root -1000) 
 (cube-root 1e-30) 
 (cube-root 1e60) 
 ;; this fails for -2 due to zero division :( 
  
 ;; Fix: take absolute cuberoot and return with sign 
  
 ;;(define (cube-root x) 
 ;;  ((if (< x 0) - +)(cube-root-iter (improve 1.0 (abs x)) 1 (abs x)))) 
  
 (define (cube x) 
   (* x x x)) 
 (define (improve guess x) 
   (/ (+ (/ x (square guess)) (* 2 guess)) 3)) 
 (define (good-enough? guess x) 
   (< (abs (- (cube guess) x)) 0.001)) 
 (define (cube-root-iter guess x) 
   (if (good-enough? guess x) 
       guess 
       (cube-root-iter (improve guess x) 
                       x))) 
 (define (cube-root x) 
   (cube-root-iter 1.0 x)) 
 (define (cube-root x) 
   (cube-root-iter 1.0 x)) 
  
 (define (cube-root-iter guess x) 
   (if (good-enough? guess x) 
       guess 
       (cube-root-iter (improve guess x) 
                       x))) 
  
 (define (good-enough? guess x) 
   (< (relative-error guess (improve guess x)) error-threshold)) 
  
 (define (relative-error estimate reference) 
   (/ (abs (- estimate reference)) reference)) 
  
 (define (improve guess x) 
   (average3 (/ x (square guess)) guess guess)) 
  
 (define (average3 x y z) 
   (/ (+ x y z) 3)) 
  
 (define error-threshold 0.01) 

This solution makes use of the fact that (in LISP) procedures are also data.

 (define (square x) (* x x)) 
 (define (cube x) (* x x x)) 
  
 (define (good-enough? guess x improve) 
   (< (abs (- (improve guess x) guess)) 
      (abs (* guess 0.001)))) 
  
 (define (root-iter guess x improve) 
   (if (good-enough? guess x improve) 
       guess 
       (root-iter (improve guess x) x improve))) 
  
 (define (sqrt-improve guess x) 
   (/ (+ guess (/ x guess)) 2)) 
  
 (define (cbrt-improve guess x) 
   (/ (+ (/ x (square guess)) 
         (* 2 guess)) 
      3)) 
  
 (define (sqrt x) 
   (root-iter 1.0 x sqrt-improve)) 
  
 (define (cbrt x) 
   (root-iter 1.0 x cbrt-improve)) 

Use the improved good-enough?:

 (define (cube-roots-iter guess prev-guess input) 
   (if (good-enough? guess prev-guess) 
       guess 
       (cube-roots-iter (improve guess input) guess input))) 
  
 (define (good-enough? guess prev-guess input) 
   (> 0.001 (/ (abs (- guess prev-guess)) 
               input))) ;; this should be (abs input) to handle negative inputs. Example: (cube-roots -1) should be -1. Before change, output was 0.33. After fix, output is corrected to -1.000000001794607. 
  
 (define (improve guess input) 
   (/ (+ (/ input (square guess)) 
      (* 2 guess)) 
    3)) 
  
 (define (square x) 
   (* x x)) 
  
 ;;to make sure the first input of guess and prev-guess does not pass the predicate accidentally, use improve here once: 
 ;;to make sure float number is implemented, use 1.0 instead of 1: 
 (define (cube-roots x) 
   (cube-roots-iter (improve 1.0 x) 1 x)) 

<< Previous exercise (1.7) | sicp-solutions | Next exercise (1.9) >>