SICP Chapter 1 exercises cont.

1.6
Alyssa P. Hacker doesn’t see why if needs to be provided as a special form. “Why can’t I just define it as an ordinary procedure in terms of cond?” she asks. Alyssa’s friend Eva Lu Ator claims this can indeed be done, and she defines a new version of if:

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

Eva demonstrates the program for Alyssa:

(new-if (= 2 3) 0 5)
5

(new-if (= 1 1) 0 5)
0

Delighted, Alyssa uses new-if to rewrite the square-root program:

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

What happens when Alyssa attempts to use this to compute square roots? Explain.

Since new-if is an ordinary procedure, scheme uses applicative order to evaluate it. This means that sqrt-iter will keep calling itself before new-if is applied to guess and the result of sqrt-iter. The result is that the procedure never stops.

Comments: This one actually stumped me and I cheated and got the answer from here and still didn’t get it. The snag I hit was that I kept trying to figure out the difference between the cond and if special forms, instead of recalling the behavior of ordinary procedures. The benefit is that I am now quite familiar with how cond is evaluated and I have a more thorough understanding of applicative-order.

1.7

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

I’ll take the statements one at a time.

“The good-enough? test used in computing square roots will not be very effective for finding the square roots of very small numbers.”

I believe the question is referring to the somewhat arbitrary value used to test if a guess is good enough (in this case 0.001). With very small values, the allowed error will be too large to be useful most of the time.

“Also, in real computers, arithmetic operations are almost always performed with limited precision. This makes our test inadequate for very large numbers.”

I think this means that with very large values the precision at the scale of 0.001 is lost, so it is impossible to properly compare the guess and the correct answer because the precision error is larger than 0.001.

“An alternative strategy for implementing good-enough? is to watch how guess changes from one iteration 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.”

I’m just going to append 2 to the modified methods.

(define (sqrt-iter2 guess last-guess x)
  (if (good-enough2? guess last-guess)
      guess
      (sqrt-iter2 (improve guess x)
                 guess
                 x)))

(define (good-enough2? guess last-guess)
  (< (/ (abs (- guess last-guess)) guess) 0.001))

It seems to work for standard problems.

“Does this work better for small and large numbers?”

I’m using guile as my scheme interpreter, and it seems that for big numbers the alternative guessing method results in less precise answers (I assume it depends on the arbitrary threshold values), but does not end up running forever like the first guessing method. For very small values, the new method is far better because the precision works relatively.

Comments: First nontrivial coding problem! There are probably better answers, but I’m proud of being able to answer this one without looking anything up. Like all coding problems, it’s hard to really be confident that the answer is correct.

1.8
Newton’s method for cube roots is based on the fact that if y is an approximation to the cube root of x, then a better approximation is given by the value

newton

Use this formula to implement a cube-root procedure analogous to the square-root procedure. (In section 1.3.4 we will see how to implement Newton’s method in general as an abstraction of these square-root and cube-root procedures.)

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

(define (cube-iter guess last-guess x)
  (if (good-enough2? guess last-guess)
      guess
      (cube-iter (improve-cube guess x)
                 guess
                 x)))

Comments: Some simple copypasting and renaming. The only significant coding was rewriting Newton’s method for cube roots in Scheme.

Chapter 1.1 exercises all done! I thought I’d be able to finish them all in one day but some concepts (1.5 and 1.6) turned out to be more difficult than I thought. The act of writing out my answers on here also took a significant amount of time, but I am glad I did it.

Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s