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