A few more exercises – one that looks at the way Scheme interprets expressions and a brief glance at special forms, and a couple of numerical ones.
Alyssa P. Hacker doesn’t see why
if needs to be provided as a special form. Can’t we just define it in terms of
cond? Alyssa defines a new version of
(define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause)))
This seems to work:
> (new-if (= 0 1) 0 5) 5 > (new-if (= 1 1) 0 5) 0
Alyssa now 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 tries to use this program to compute square roots? Explain.
The program will enter into an infinite loop. When you call
new-if the interpreter attempts to evaluate all the inputs, and then passes them into
cond. In the square root program, the third input to
sqrt-iter, which involves another call to
new-if, which calls
sqrt-iter again, and so on.
In contrast, the special form
if evaluates its first argument, and then evaluates only one of the remaining two arguments depending on whether the first argument is true or false — therefore the problem of entering into an infinite loop never arises, as eventually the first argument returns true, which means that the second argument (rather than the third) is the one that gets evaluated.
good-enough? test used to compute 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 inaccurate 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 stop when the change is a very small fraction of the guess. Design a square root procedure that uses this kind of test. Does it work better for small and large numbers?
The procedure fails for very small numbers because it is not accurate enough. For example, say we want to compute the square root of 0.000001 (which is 0.001) using this procedure. If our initial guess was 0.02 (too big by a factor of 20) then our test squares it to get 0.0004, which is certainly within 0.001 of the input — so this guess passes the test, and is reported as the true number. Here’s an example, using 1.0 as an initial guess:
> (sqrt 0.000001) 0.031260655525445276
It fails for large numbers because the computer only stores floating point numbers to a limited precision — it uses a fixed number of bits to store a number of significant digits, and the rest of the bits to store an exponent. The limit of precision is often called machine epsilon. For significantly large numbers, machine epsilon is bigger than 0.001, and thus the difference between any two different, sufficiently large numbers will be greater than 0.001, and the process will not terminate. For example, trying to computer
> (sqrt 1000000000000000)
(that’s 1 followed by 15 zeros) causes the interpreter to hang.
To get around this, we can redefine
good-enough?. We supply it with the previous guess and the new guess, and it returns true when the difference in guesses is smaller than the new guess by some fixed ratio (let’s say 0.000001, or ). Our
sqrt-iter process becomes:
(define (sqrt-iter old-guess new-guess) (if (good-enough? old-guess new-guess) guess (sqrt-iter new-guess (improve new-guess))))
good-enough? now given by:
(define (good-enough? old-guess new-guess) (< (abs (- old-guess new-guess)) (* 0.000001 new-guess)))
We can now try computing the square roots of very small and large numbers:
> (sqrt 0.000001) 0.0010000000000000117 > (sqrt 1000000000000000) 31622776.601683907
and see that everything works as we would expect it to.
Netwon’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
Use this formula to implement a cube root procedure analogous to the square root procedure.
We only need to change a few of our procedures. Our newly improved
good-enough? procedure is already fine. If we implement a procedure
(define (improve-cbrt guess x) (/ (+ (/ x (square guess)) (* 2 guess)) 3))
and the iterative cube root as essentially identical to the iterative cube root:
(define (cbrt-iter old-guess new-guess x) (if (good-enough? old-guess new-guess) guess (cbrt-iter new-guess (improve-cbrt new-guess) x)))
(define (cbrt x) (cbrt-iter 0.0 1.0 x))
then we can use our new cube root procedure as we’d expect:
> (cbrt 8) 2.0 > (cbrt 100) 4.64158883361313
Next we’ll look at a way to hide our abstractions from the end user, by defining procedures inside other procedures.