SICP Solutions - 1.7

Q: The good-enough? test used in computing square roots will not be very effective for finding the square roots of very small numbers. Also, in real computers, arithmetic operations are almost always performed with limited precision. This makes our test inadequate for very large numbers. Explain these statements, with examples showing how the test fails for small and large numbers. An alternative strategy for implementing good-enough? is to watch how guess changes from one iteration to the next and to stop when the change is a very small fraction of the guess. Design a square-root procedure that uses this kind of end test. Does this work better for small and large numbers?


A: This is best demonstrated through examples using perfect squares:

> (sqrt 1000000000000)
1000000.0
> (sqrt 10000000000000)
; Infinite loop. 
> (sqrt 0.01)
0.100325785109606
> (sqrt 0.001)
0.0412454260749911 ; Good enough for government work.
> (sqrt 0.0001)
0.0323084483304812 ; Uh oh!
> (sqrt 0.0001)
0.0323084483304812
> (sqrt 0.00001)
0.0313564901077172
> (sqrt 0.000001)
0.0312606555254453

Very big numbers run into the limitations of your implementation of Scheme and/or how your machine handles decimals, and good-enough? doesn't work for numbers less than its threshold. Now, let's try changing good-enough? as the question suggests:

(define (good-enough? guess old-guess)
  (< (abs (- guess old-guess)) (* guess 0.001)))

; It's a good thing I already read Little Schemer,
; because this book really glosses over recursion.
(define (sqrt-iter guess old-guess x)
  (if (good-enough? guess old-guess)
    guess
    (sqrt-iter (improve guess x) guess x)))

(define (sqrt x)
  (sqrt-iter 1.0 2.0 x))
> (sqrt 1000000000000)
1000000.10346124 ; Not better, but carrying on...
> (sqrt 10000000000000)
3162277.66401048
> (sqrt 100000000000000)   
10000000.000044
> (sqrt 1000000000000000)  
31622779.2799952 ; And so on. Wowie!
; Now the small numbers
> (sqrt 0.01)
0.100000000001399
> (sqrt 0.001)
0.031622782450701
> (sqrt 0.0001)
0.0100000000254907
> (sqrt 0.00001)
0.0031622776602039
> (sqrt 0.000001)
0.00100000015330166 ; And so on.

This new way is obviously better. To get some intuition as to why, you can modify the new good-enough? to print each iteration, and play around in a REPL. This post is already pretty long, so I'll leave it as an exercise to the answer-reader.

(define (good-enough? guess old-guess)
  (display (abs (- guess old-guess)))
  (newline)
  (display (* guess 0.001))
  (newline)
  (newline)
  (< (abs (- guess old-guess)) (* guess 0.001)))