SICP Exercise 1.7

Exercise1-7.md

The good-enough? function is not so effective when we use small numbers as arguments in the function.

For example, when we want to find the square root of 0.0001 which is 0.01,

(sqrt 0.0001)

;.03230844833048122

The wrong answer is because the good-enough? function stops the refinement of the answer once it reaches to 0.001 of the actual answer. In this case, (square 0.0323084) = 0.0010438 which is within 0.001 of the actual answer of 0.0001. Thus, the function evaluates to #t. To test further, we try

(sqrt 0.000001)

;.03135649010771716

which is also the wrong answer.

As for large numbers, we also see problems because of the floating point representation in the computers. As large numbers cannot be represented with the precision of 0.001 required by the good-enough? function, the function never returns a #t.

When we try evaluating the following expression

(sqrt 1e15)

the system keeps evaluating without halting.

To fix these problems, we can redefine the good-enough? function to compare between subsequent guesses.

(define (sqrt-iter guess prev-guess x)
  (if (good-enough? guess prev-guess)
      guess
      (sqrt-iter (improve guess x) 
      		 guess
                 x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

(define (good-enough? guess prev-guess)
  (< (abs (- guess prev-guess)) 0.001))

(define (sqrt x)
  (sqrt-iter 1.0 0.0 x))

The good-enough? function above evaluates by only comparing the previous-guess with the current guess to check if there is any improvement in refinement of answer by doing any further iterations. For small numbers, it ensures that the iteration does not halt prematurely and for large numbers, it halts when it is realised that the iteration will not produce further refinement. To test, we re-run the previous tests.

(sqrt 0.0001)
; 1.0000714038711746e-2

(sqrt 1e15)

; 31622776.601683795