## Thursday, October 15, 2009

### SICP Exercises 1.6 - 1.8

Exercises from section 1.1.7 Example: Square Roots by Newton's Method of SICP.

Exercise 1.6 gives the following alternative definition to the if special form:
(define (new-if predicate then-clause else-clause)   (cond (predicate then-clause)         (else else-clause)))
The new-if procedure seems to work with simple conditional statements on the command line, but if you then define the sqrt-iter procedure in terms of new-if, you notice something peculiar. The sqrt-iter procedure defined in terms of new-if never finishes executing.

To explain why, we need to recall that if is a special form. From section 1.1.6 of the text,
To evaluate an if expression, the interpreter starts by evaluating the "predicate" part of the expression. If the "predicate" evaluates to a true value, the interpreter then evaluates the "consequent" and returns its value. Otherwise it evaluates the "alternative" and returns its value.

In the if special form, after the predicate is evaluated, only one of the consequent or alternative will be evaluated. Never both. The new-if procedure that we've defined doesn't have this property. Our interpreter will use regular old applicative-order evaluation when it encounters the new-if procedure. Since the else-clause passed to new-if in the sqrt-iter procedure is always evaluated, sqrt-iter never stops making recursive calls to itself.

Exercise 1.7 points out a flaw in the implementation of the sqrt procedure when you try to find the square root of very small or very large numbers.

The problem is easy to spot for very small numbers. Try evaluating the following:
(sqrt 0.001)
and you should get a wrong answer. Instead of 0.0316227766 as you might expect, our sqrt procedure gives an answer of 0.0412454261. The problem is that as we refine our guess, we stop as soon as the square of our guess is within 0.001 of x. Squaring 0.0412454261we get 0.00170118517, which we can see is within our tolerance of 0.001.

For very large numbers the problem is a bit more difficult to pin down. If we try to evaluate the square root of a large enough number, we find that the interpreter never returns a value. For example, evaluating the following expression
(sqrt 9999999999998)
will never return. (I'm using PLT Scheme with the "Module" language selected for the exercises in this section. You may have different results.)

What might cause that? The answer is due to the nature of floating-point numbers. As values get larger and larger, their floating-point representation becomes less precise. As we keep recursively refining our guess in the square root procedure, if the value of the guess is large enough we're unable to represent it to within our tolerance of 0.001. This causes an endless sequence of recursive calls, since the interpreter will never reach a point where the guess is good enough.

The solution to this problem, as suggested in the question itself, is to redefine our good-enough? procedure so that it stops when our guess changes by a very small amount.

(define (square x)   (* x x))(define (average x y)   (/ (+ x y)      2))(define (good-enough? guess previous-guess)   (< (abs (- guess previous-guess))         0.001))(define (improve guess x)   (average guess            (/ x guess)))(define (sqrt-iter guess previous-guess x)   (if (good-enough? guess previous-guess)       guess       (sqrt-iter (improve guess x)                  guess                  x)))(define (sqrt x)   (sqrt-iter 1.0 0 x))
Note that the good-enough-procedure no longer takes x as an input parameter, but instead decides whether or not a guess is good enough based on the change from the previous guess. This change also called for a change to the sqrt-iter procedure, which must now keep track of the previous guess. Finally, note that when I first call the sqrt-iter procedure in sqrt, I pass in values of 1.0 and 0 for the initial guess and the previous guess. This ensures that the difference will be greater than our tolerance for at least one recursive call of sqrt-iter.

Exercise 1.8 gives us the following formula for improving a guess when using Newton's method for computing a cube root.

This is analogous to averaging our guess with x/guess in order to refine our guess in the square root procedure. In order to compute the cube root, we can replace the square root improve procedure with the following definition.
(define (improve guess)   (/ (+ (/ x            (square guess))         (* 2 guess))      3))
Putting it all together (starting from the improved version of sqrt that we wrote in the previous exercise) we get:
(define (square x)   (* x x))(define (good-enough? guess previous-guess)   (< (abs (- guess previous-guess))         0.001))(define (improve guess x)   (/ (+ (/ x            (square guess))         (* 2 guess))      3))(define (cbrt-iter guess previous-guess x)   (if (good-enough? guess previous-guess)       guess       (cbrt-iter (improve guess x)             guess             x)))(define (cbrt x)   (cbrt-iter 1.0 0 x))
We can test it out with the values that gave us problems before, with the following results:
> (sqrt 0.001)0.03162278245070105> (sqrt 99999999999998)9999999.9999999

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

Aruni RC said...

Really helpful. Do keep up the great work Bill.
Btw do check out Eli Bendersky's SICP section for parallel solutions (if needed).

Bill the Lizard said...

Aruni,
Thanks for the tip. So far I've been trying to avoid "spoilers" because I want to solve all the exercises myself, but I've heard that some of them get really hard in later chapters. It will be nice to have another resource to fall back on, just in case.

dole.doug said...

Bill, I'm just curious. How much time did you put for each SICP session. Did you do it daily?
I'm trying o learn from others the art of time management.
Many thx and good luck!

Bill the Lizard said...

dole.doug,

I do try to do at least one SICP activity per day. I define "activity" as 1) watching a video, 2) doing an exercise, 3) reading a few pages from the book, or 4) transcribing any of the first 3 to my blog. Since each video is about an hour long, that's how much time I set aside each day for SICP.

In order to really understand and to get good notes, so far I've had to watch each lecture more than once. Those MIT students in the videos must have been much smarter than I am, since they didn't have the benefit of a recorded lecture that they could rewind and replay as often as they liked. :)

Thanks for following along. I'll have the next set of lecture notes up soon.

THK said...

I've begun the SICP learning these days and your posts help me a lot. Thank you!
(I stuck in Exercise 1.6 and your explanation helped me through it.)

Bill the Lizard said...

THK,
Glad I could help! If you have any questions about any of the exercises feel free to drop me a comment. Or you can ask on Stack Overflow and I'll probably see it, plus you get the benefit of a lot of other Scheme programmers who are really helpful and knowledgeable. Thanks for reading.

mfreeman451 said...

I don't think those are MIT students. I believe these videos are from the 1986 lectures commissioned by HP and given to HP employees. I'd like to know more about how this impacted these HP employees careers and lives.

Chris McClelland said...

Hi Bill,
I think your good-enough? implementation is not to spec. The book suggests "watch how guess changes from one iteration to the next and...stop when when the change is a very small fraction of the guess". I think that translates to something like:
(define (good-enough? guess previous-guess)
(< (abs (- guess previous-guess))
(/ guess 1000)))

Lewis said...

Hi Bill,

Your solution to 1.7 includes the definition of square x, but the new good-enough? definition no longer requires the comparison of square guess and x. Is there some other reason you included the definition of square x?

Bill the Lizard said...

Lewis,

No, there's no reason to include the definition of square in exercise 1.7. I solved 1.7 and 1.8 together, so that definition got into both solutions.

fernando berlanga said...
This comment has been removed by the author.
fernando berlanga said...

In my case I merged 1.7 and 1.8 as well with a more general solution to find the nth-root of a real number. Notice that
the root to be taken must a natural number, since it's bound to the implementation of the power function that deals with natural numbers as an exponent. n can be a floating point if an implementation of pow with floating points is given as well.
See nth-root algorithm: Derivation of Newton's Method.

(defun power (x n)
(if (zerop n)
1
(* x (power x (1- n)))))

(defun nth-root (x n)
(defun deltax-val (guess)
(* (/ 1.0 n)
(- (/ x (power guess (1- n)))
guess)))
(defun nth-root-helper (guess deltax)
(if (good-enough? deltax)
guess
(let ((dx (deltax-val guess)))
(nth-root-helper (+ guess dx) dx))))
(defun good-enough? (deltax)
(if (> (abs deltax) 0.001)
nil
t))
(nth-root-helper 1.0 1.0)) ; initial guess