Exercise 1.7

Question

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 interation 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?

Answer

We will first need the function that implement the square-root algorithm:

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

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

(define (square x)
        (* x x)
)

(define (good-enough? guess x)
        (< (abs (- (square guess) x)) 0.001)
)

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

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

Let's try first to check the result for a few small numbers:

; The value for this square root is 0.2529...
(sqrt 0.064)
; 0.25311115862564304

; The error above is somehow tolerable, but
; what happens if we go with even smaller
; numbers? The result is expected to be
; 0.08 exactly.
(sqrt 0.0064)
; 0.08095136013810225

; Still not bad, so we'll go further.
; The real result for the square root
; below should be 0.02529...
(sqrt 0.00064)
; 0.037790493135637745

; We stop here, as this is a bit off the range.

The above happens because the precision we've chosen for the good-enough? procedure is only 0.001, so it doesn't go far enough to find a more precise value.

Let's see how the square-root of large numbers performs.

; The below never finishes to run in my machine.
(sqrt 1999249294194921451)

In the case of a large number like the above, the procedure remains in an infinite loop because whatever value is chosen will never provide the 0.001 threshold as floating numbers have limited precision.

Finding the proper implementation for this function is hard and there is lengthy discussion in this forum post below: