Structure and Interpretation of SICP

Introduction

Okay, this is the first SICP thread, but I intend it to be serious.

I'd like to start at Section 1.1.7 Example: Square Roots by Newton’s Method.

Section 1.1.7 Example: Square Roots by Newton’s Method.

This section is about implementing Newton’s Method as a program. Newton’s Method for square root is computed by approximating the square root of x by successively averaging a guess, g with x/g.

Basic strategy:

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

where improve averages g and x/g and where good-enough? tests to see if the absolute difference of g² and x is less than 0.001 — basically, a very rough approximation. Good stuff.

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?

Okay, consider the following example:

> (sqrt 1.0000013)         ;; proper square root
1.0000006499997889
(square-root 1.0000013)  ;; our square root
1.0000013

So, for very small numbers, our good-enough? function is not good enough (teehee).

On the other end of the scale, I wasn’t so sure about it. The exercise mentions “in real computers, arithmetic operations are almost always performed with limited precision. This makes our test inadequate for very large numbers.” So this got me thinking about the implementation of decimal values. I had thought for fixed point decimals, the as the number part grows, there is less space in the implementation for the decimal part which would get truncated, but I really do not know. If someone can explain that, I would appreciate it.

Here is the basic implementation:

(define (square n) (* n n))

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

; old good-enough? procedure
; (define (good-enough? g n)
;  (< (abs (- (square g) n)) 0.001))

; new good-enough? procedure
(define (good-enough? g g.)
  (> (/ (min g g.) (max g g.)) 0.999999999))

(define (improve g n) (average g (/ n g)))

(define (square-root n)
  (define (try n g g.)
    (if (good-enough? g g.)
        g
        (try n (improve g n) g)))
  (try n 1.0 0.0))

This implementation works well for small numbers because it tests if the guess has not changed very much i.e. one is 99.9999999% the size of the other.

Did anyone come up with something better than this?

Isaac Newton - JEW

>─────▄████▀█▄
>───▄█████████████████▄
>─▄█████.▼.▼.▼.▼.▼.▼▼▼▼
>▄███████▄.▲.▲▲▲▲▲▲▲▲
>███████████████████▀▀
YOU HAVE BEEN CAUGHT BY THE GATOR OF DOOM! REPOST THIS 5 TIMES OR GET GATORED!!!