SICP Solutions: Section 1.1.7
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))