# SICP Exercises 1.5 through 1.7

In this installment, we’ll look at exercises 1.5 through 1.7. Note that these exercises are taken from the first edition.

## Exercise 1.5

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 tests 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 test. Does this work better for small and large numbers?

First, here are the original definitions of `GOOD-ENOUGH?` and friends from the text:

```(define (square x)
(* x x))

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

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

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

(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))

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

Let’s test the operation of `NEW-SQRT`. In the results below, `NEW-SQRT` is off by a factor of ten when taking the root of .00001 – a small number.

```(sqrt .00001)
0.00316228 ;Three one thousandths.
```
```(new-sqrt .00001)
0.0313565 ;Three one hundredths. Wat?
```

Why are we so far off? Let’s trace `GOOD-ENOUGH?`, since it’s used to decide when our result is, er, good enough.

```> ,trace good-enough?
> (new-sqrt .00001)
[Enter (good-enough? 1. 1.e-05)
Leave good-enough? #f]
[Enter (good-enough? 0.500005 1.e-05)
Leave good-enough? #f]
[Enter (good-enough? 0.250012 1.e-05)
Leave good-enough? #f]
[Enter (good-enough? 0.125026 1.e-05)
Leave good-enough? #f]
[Enter (good-enough? 0.0625531 1.e-05)
Leave good-enough? #f]
[Enter (good-enough? 0.0313565 1.e-05)
Leave good-enough? #t]
0.0313565
```

In the last call to `GOOD-ENOUGH?`, we’re still off by a factor of ten! This is because inside `GOOD-ENOUGH?`, we’re checking our results against an absolute value (also known as a “magic number”), which is dumb. As suggested by the text, let’s implement a better `GOOD-ENOUGH?` that watches how `GUESS` changes from one iteration to the next and returns true when the value of `GUESS` stops changing by much. This means we’ll have to update `SQRT-ITER`, too.

```(define (good-enough? last-guess this-guess x)
(if (< (abs (- this-guess last-guess)) .0001) ;Watch how GUESS changes.
#t
#f))

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

(define (new-sqrt x)
(sqrt-iter 0 1.0 x))
```

Now we’ll test our new `GOOD-ENOUGH?`:

```> (sqrt .0001)
0.01
> (new-sqrt .0001)
0.01
> (sqrt .1)
0.316228
> (new-sqrt .1)
0.316228
> (sqrt .0000001)
0.000316228
> (new-sqrt .0000001)
0.000319804 ;Pretty darn close!
```

As we can see from the tests, this version of `GOOD-ENOUGH?` starts to lose accuracy when we work with millionths. I’m happy with that accuracy for this application. :-)

## Exercise 1.6

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

(x/y**2 + 2y) / 3

Use this formula to implement a cube-root procedure analogous to the square root procedure.

After doing the last problem, this is pretty much a “color by numbers” implementation:

```(define (cube-iter last-guess this-guess x)
(if (good-enough? last-guess this-guess x)
this-guess
(cube-iter this-guess (cube-improve this-guess x) x)))

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

(define (cube x)
(cube-iter 0 1.0 x))
```

Testing it is also straightforward:

• Take the cube root `Y` of a number, `X`
• Use `EXPT` to cube `Y`
• See if the number you get back is `X`

The tests look good. Note that `GOOD-ENOUGH?` is still being traced (just for fun).

```> (cube 16)
[Enter (good-enough? 0 1. 16)
Leave good-enough? #f]
[Enter (good-enough? 1. 6. 16)
Leave good-enough? #f]
[Enter (good-enough? 6. 4.14815 16)
Leave good-enough? #f]
[Enter (good-enough? 4.14815 3.07538 16)
Leave good-enough? #f]
[Enter (good-enough? 3.07538 2.61415 16)
Leave good-enough? #f]
[Enter (good-enough? 2.61415 2.5232 16)
Leave good-enough? #f]
[Enter (good-enough? 2.5232 2.51985 16)
Leave good-enough? #f]
[Enter (good-enough? 2.51985 2.51984 16)
Leave good-enough? #t]
2.51984
> ##
2.51984
> (expt ## 3)
16.
> (expt 16 3)
4096
> (cube ##)
[Enter (good-enough? 0 1. 4096)
Leave good-enough? #f]
[Enter (good-enough? 1. 1366. 4096)
Leave good-enough? #f]
[Enter (good-enough? 1366. 910.667 4096)
Leave good-enough? #f]
[Enter (good-enough? 910.667 607.113 4096)
Leave good-enough? #f]
[Enter (good-enough? 607.113 404.746 4096)
Leave good-enough? #f]
[Enter (good-enough? 404.746 269.839 4096)
Leave good-enough? #f]
[Enter (good-enough? 269.839 179.911 4096)
Leave good-enough? #f]
[Enter (good-enough? 179.911 119.983 4096)
Leave good-enough? #f]
[Enter (good-enough? 119.983 80.0836 4096)
Leave good-enough? #f]
[Enter (good-enough? 80.0836 53.6019 4096)
Leave good-enough? #f]
[Enter (good-enough? 53.6019 36.2098 4096)
Leave good-enough? #f]
[Enter (good-enough? 36.2098 25.1812 4096)
Leave good-enough? #f]
[Enter (good-enough? 25.1812 18.9407 4096)
Leave good-enough? #f]
[Enter (good-enough? 18.9407 16.4329 4096)
Leave good-enough? #f]
[Enter (good-enough? 16.4329 16.0113 4096)
Leave good-enough? #f]
[Enter (good-enough? 16.0113 16. 4096)
Leave good-enough? #f]
[Enter (good-enough? 16. 16. 4096)
Leave good-enough? #t]
16.
```

## Exercise 1.7

Each of the following two procedures defines a method for adding two positive integers in terms of the more primitive operators `1+`, which increments its argument by 1, and `-1+`, which decrements its argument by 1.

```(define (incr n) (+ n 1))               ;Modern 1+
(define (decr n) (- n 1))               ;Modern -1+

;; The FOO and BAR designators are just used to differentiate these
;; procedures from our built-in addition procedure (and from each
;; other).
(define (foo+ a b)
(if (= a 0)
b
(incr (foo+ (decr a) b))))

(define (bar+ a b)
(if (= a 0)
b
(bar+ (decr a)
(incr b))))
```

Using the substitution model, illustrate the process generated by each procedure in evaluating `(+ 4 5)`. Are these processes iterative or recursive?

Let’s start by tracing `FOO+`. This wasn’t strictly necessary, but I like tracing things.

```> (foo+ 3 4)
[Enter (foo+ 3 4)
[Enter (foo+ 2 4)
[Enter (foo+ 1 4)
[Enter (foo+ 0 4)
Leave foo+ 4]
Leave foo+ 5]
Leave foo+ 6]
Leave foo+ 7]
7
```

As you can see, we keep deferring operations until we reach our base case. This is shown in the way we enter the recursive `FOO+` procedure call four times, and each time we decrement the variable `A`, but `B` remains the same. Then, when we hit our base case (when `A` is equal to 0), we make the addition calls we’ve been storing up all this time. You can tell this is happening because every time we `Leave’ the call to `FOO+`, we’re still adding to the value.

Here’s another, possibly better way to visualize it:

```(foo+ 3 4)
(incr (foo+ (decr 3) 4))
(incr (incr (foo+ (decr 2) 4)))
(incr (incr (incr (foo+ (decr 1) 4))))
(incr (incr (incr 4)))
```

Therefore this procedure uses O(n) time in `B` and O(n) space in `A` (assuming it’s called as `(FOO+ A B)`.)

Now let’s look at `BAR+`. Here’s the text of the procedure again:

```(define (bar+ a b)
(if (= a 0)
b
(bar+ (decr a)
(incr b))))
```

`BAR+` looks like it will generate an iterative process. Its self-call appears to be in tail position. Let’s see how it looks in the REPL:

```> (bar+ 3 4)
[Enter (bar+ 3 4)
[Enter (bar+ 2 5)
[Enter (bar+ 1 6)
[Enter (bar+ 0 7)
Leave bar+ 7]
Leave bar+ 7]
Leave bar+ 7]
Leave bar+ 7]
7
```

In this case, we can be pretty sure we’re generating an iterative process (with no deferred computations being built up) because when we `Leave’ the call to `BAR+` we’re not doing anything additional to the result, it’s just being passed back up to the top-level unchanged.

Here’s a trace written out by hand:

```(BAR+ 4 3)
(BAR+ 3 4)
(BAR+ 2 5)
(BAR+ 1 6)
(BAR+ 0 7)
```

As you can see, we don’t defer operations that take up additional space. Therefore we’re O(1) in space, and O(n) in time for this implementation.

(Image courtesy SallySetsForth under Creative Commons license.)