1 minute read

Section 1.1.7

Exercise 1.6

If if is not a special form, and is a procedure based on cond instead, it would lose its short-circuiting property, as, due to applicative-order evaluation, all of the arguments would need be evaluated just as the new-if procedure would be called.

In our case, the program would fall into an infinite loop, always trying to evaluate the next sqrt-iter, even if good-enough? would return true.

Exercise 1.7

For very small numbers, 0.001 will be of the same order of magnitude with the solution. This means that the tolerance will not be adequate to reach a good-enough solution. For example, calculating the square root of 0.0001 itself (which is 0.01), our algorithm will yield:

> (sqrt 0.0001)
0.0323084483304812
> (square 0.032)
0.001024

For very large numbers, the algorithm might never terminate because the machine precision will not be able to represent small differences between large numbers. This means that good-enough? will never return #t. The tipping point is between \( 10^{12} \) (which returns) and \( 10^{13} \) (which runs infinitely).

What happens is that after a few iterations, the guess will be 3,162,277.6601683795. When running good-enough?, the procedure will try to square it, yielding 10,000,000,000,000.002, which isn’t good enough according to the 0.001 desired error. When trying to improve this, the procedure will need the average of the guess and of the x/y = 3,162,277.660168379. However, this reaches the limit of the numbers that can be represented, and the average is again 3,162,277.6601683795 which means guess will remain unchanged and the program will enter an infinite loop.

To improve, we can use the following listing which uses the suggested solution of making sure that the guess actually improves between runs, again using the value 0.001 as a threshold - if the ratio between or old guess and the new one hasn’t changed at least by that number, then we consider our calculations finished.

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

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

(define (guess-improved? guess old-guess)
  (> (abs (- 1 (/ guess old-guess))) 0.001))

(define (sqrt-iter guess old-guess x)
  (if (guess-improved? guess old-guess)
    (sqrt-iter (improve guess x)
               guess
               x)
    guess))

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

(sqrt 0.0001)

Exercise 1.8

We just need to use a different improve procedure:

  (define (improve guess x)
    (/ (+ (/ x (square guess))
       (* 2 guess))
     3))

Updated: