Exercise

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?

Student Response

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

;code from previous sections
(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 (sqrt x)
  (sqrt-iter 1.0 x))

(define (show-diff x)
  (- x (square (sqrt x))))

;write a new version of good-enough? that uses the change in guess as a stopping condition
(define (good-enough?-new guess x)
  (< (abs (- guess (improve guess x))) 0.001))

;add the new version of good-enough? to the sqrt procedure
(define (sqrt x)
  (sqrt-iter-new 1.0 x))

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

As the number x gets smaller, the difference between (sqrt x) and (square (sqrt x)) gets larger.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

(show-diff 1)
0.0
(show-diff 1/4)
-0.00015246226204634894
(show-diff 1/5)
-0.0003628117913832274
(show-diff 1/6)
-0.0006492855829077215
(show-diff 1/7)
-0.0009887313857490088
(show-diff 1/8)
-3.6634705268268064e-6
(show-diff 1/9)
-6.78189099308224e-6
(show-diff 1/10)
-1.1255662039411085e-5
(show-diff 1/11)
-1.7222287031562478e-5
(show-diff 1/12)
-2.4759160811294034e-5
(show-diff 1/13)
-3.389224490113474e-5
(show-diff 1/14)
-4.4606249993667246e-5
(show-diff 1/15)
-5.685448920601799e-5
(show-diff 1/16)
-7.056755783747815e-5
(show-diff 1/17)
-8.566056114387571e-5

As x gets larger, we run out of precision.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

(show-diff (square 5555))
0.0
(show-diff (square 55555))
0.0
(show-diff (square 555555))
0.0
(show-diff (square 5555555))
0.0
(show-diff (square 55555555))
0.0

With the good-enough?-new stopping condition, the sqrt procedure works better for small numbers, but does not seem to impact the performance for large numbers.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

(show-diff (/ 1 4))
-0.00015246226204634894
(show-diff (/ 1 5))
-0.0003628117913832274
(show-diff (/ 1 6))
-0.0006492855829077215
(show-diff (/ 1 7))
-1.6990229269875368e-6
(show-diff (/ 1 8))
-3.6634705268268064e-6
(show-diff (/ 1 9))
-6.78189099308224e-6
(show-diff (/ 1 10))
-1.1255662039411085e-5
(show-diff (/ 1 11))
-1.7222287031562478e-5
(show-diff (/ 1 12))
-2.4759160811294034e-5
(show-diff (/ 1 13))
-3.389224490113474e-5
(show-diff (/ 1 14))
-4.4606249993667246e-5

Evaluation

Critique my response and let me know about anything that I am overlooking.

Let me analyze your solution to Exercise 1.7:

Your implementation and testing approach is good, but there are some important aspects to consider:

  1. Small Numbers Testing
  • You’ve demonstrated well how the original good-enough? test fails for small numbers through show-diff
  • The pattern shows increasing errors as numbers get smaller
  • However, you could explain why this happens: The fixed tolerance of 0.001 becomes relatively large compared to very small numbers
  1. Large Numbers Testing
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

```scheme
(show-diff (square 5555))
0.0
(show-diff (square 55555))
0.0
(show-diff (square 555555))
0.0
(show-diff (square 5555555))
0.0
(show-diff (square 55555555))
0.0
```
  • Your large number tests show the precision issue
  • However, you could be more explicit about why we get all zeros:
    • For very large numbers, the limited precision of floating-point arithmetic means small relative differences appear as zero
    • The absolute tolerance of 0.001 becomes too small relative to large numbers
  1. New Implementation Analysis
1
2

(define (good-enough?-new guess x)
  (< (abs (- guess (improve guess x))) 0.001))
  • Your new good-enough? implementation uses relative change between guesses
  • This is better because it adapts to the scale of the numbers
  • However, you could explain:
    • Why this works better for small numbers (the tolerance is relative to the guess)
    • The mathematical reasoning behind using the change in guess as a stopping condition
  1. Missing Comparative Analysis
  • You could strengthen your response by showing direct comparisons between the old and new methods for specific test cases
  • You mention it works better for small numbers but “does not seem to impact the performance for large numbers” - this deserves more explanation
  1. Edge Cases
  • You haven’t tested some important edge cases:
    • What happens with 0?
    • What happens with negative numbers?
    • What about very small numbers like 1e-10?

Here’s a suggested addition to make your analysis more complete:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

; Additional test cases to consider
(sqrt 0)
(sqrt -1)
(sqrt 1e-10)
(sqrt 1e10)

; Compare old vs new for very small numbers
(define (compare-methods x)
  (display "Original: ")
  (display (sqrt x))
  (display " New: ")
  (display (sqrt-new x))
  (newline))

Would you like me to elaborate on any of these points?