3
\$\begingroup\$

Here is exercise 1.7 from SICP:

Exercise 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 believe "a very small fraction of the guess" means guess*a-very-small-number. I think it is working correctly. I haven't found any values that could fail the good-enough? test. Is there something wrong here I haven't discovered? Please review my code. How can I improve it?

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

(define (sqrt-iter guess x)
  (if (good-enough? guess (improve 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 next-guess)
  (< (abs (- guess next-guess)) (* guess 0.000000000000000000000000000001)))

(define (square x)
  (* x x))
\$\endgroup\$
  • 1
    \$\begingroup\$ Right now you're asking for equality to something like 30 decimal digits. That's a lot more than you typically need. If you loosen that requirement, you'll typically use fewer iterations, so you'll get your results faster. \$\endgroup\$ – Jerry Coffin Jul 13 '17 at 18:48
3
\$\begingroup\$

sqrt-iter

  1. You compute (improve guess x) twice - this is a waste.
  2. You return guess instead of the improved guess, i.e., you return a worse approximation than you could.

E.g.:

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

good-enough?

  1. 0.000000000000000000000000000001 is unreadable. 1d-30 is better.
  2. 1d-30 is far too high precision. With such an epsilon, you might as well use = instead of good-enough? - the "oscillation between two adjacent floats" problem will be the same. Read up on machine epsilon.
  3. This number should actually be an argument to sqrt.
  4. Adding a line break would make the function more readable.
\$\endgroup\$
  • \$\begingroup\$ "you return a worse approximation than you could." - how mutch worse could this be? Is it possible I didn't notice it because of the very high precision I used? \$\endgroup\$ – morbidCode Jul 15 '17 at 3:25
  • \$\begingroup\$ at most 1d-30 ;-) \$\endgroup\$ – sds Jul 16 '17 at 2:23
1
\$\begingroup\$

With IEEE floating point numbers, the multiplication (* guess 1d-30) may underflow, leading to a 0.0 result. The test would have to be more sophisticated in a real program. Check out these links Comparison of floating point numbers , Correctly Rounded Decimal to Floating-Point Conversion

The precision should also depend on the kind of floating points. If you use ieee754 32-bit, then you have only 24-bit, less than 8 decimal significant digits. With 64-bit you have 53 bits, or a little less than 16 significant digits. Is the most significant decimal digits precision that can be converted to binary and back to decimal without loss of significance 6 or 7.225?

I don't have a production-level code for this exercise but I'd also like to see one.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.