Skip to content

Instantly share code, notes, and snippets.

@bmabey
Forked from jimweirich/gist:189261
Created September 23, 2009 02:32
Show Gist options
  • Save bmabey/191650 to your computer and use it in GitHub Desktop.
Save bmabey/191650 to your computer and use it in GitHub Desktop.
SICP Exercise 1.7
;; 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?
; The problem with the good-enough? procedure for small numbers is that there radicant is much smaller than
; the 0.001 hardcoded threshold. The logic prevents the improvement of the guess past this threshold.
; For example, the square-root of 0.005 is ~0.007110678 but the computed value with the 0.001 threshold
; is 0.031781009679092864 since the logic prevents any further improvements.
;
; The problem with large numbers is you enter an endless loop as the program is unable to improve the guess
; any further. An example of this is (sqrt 123456789012345678901234567890). At some point the value of the guess
; becomes 4.4351364182882e16 and the improve guess continues to return the same value unable to improve it. As
; the question alluded to math on computers is done with limited precision. This fact is evident as the floating
; point value guess is not changed with subsequent applications of improve on it and the original number.
;
; Below is my implementation of the proposed solution. Instead of having a good-enough? function I introduced a
; within-delta? function that sqrt-iter used to compare old and current guesses. To enable this state to be carried
; by all the recursive calls I added it as an argument to the sqrt-iter. With this solution small and large numbers
; are computed correctly.
(define (square x)
(* x x))
(define (average numbers)
(/ (apply + numbers) (length numbers)))
(define (within-delta? x y delta)
(<= (abs (- x y)) delta))
(define (sqrt x)
(define (improve guess x)
(average (list guess (/ x guess))))
(define (sqrt-iter old-guess guess x)
(if (within-delta? old-guess guess 0.000001)
guess
(sqrt-iter guess (improve guess x)
x)))
(sqrt-iter 0.0 1.0 x))
(sqrt 9)
(sqrt (+ 100 37))
(sqrt (+ (sqrt 2) (sqrt 3)))
(square (sqrt 1000))
(sqrt 0.005)
(sqrt 123456789012345678901234567890)
(defn square [x]
(* x x))
(defn abs [x]
(if (< x 0) (- x) x))
(defn average [numbers]
(/ (apply + numbers) (count numbers)))
(defn within-delta? [x y delta]
(<= (abs (- x y)) delta))
(defn sqrt [x]
(let [improve (fn [guess x]
(average (list guess (/ x guess))))
sqrt-iter (fn [old-guess guess x]
(if (within-delta? old-guess guess 0.000001)
guess
(recur guess (improve guess x) x)
))]
(sqrt-iter 0.0 1.0 x)))
(sqrt 9)
(sqrt (+ 100 37))
(sqrt (+ (sqrt 2) (sqrt 3)))
(square (sqrt 1000))
(sqrt 0.005)
(sqrt 123456789012345678901234567890)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment