Chapter 1, Building Abstractions with Procedures
Section - The Elements of Programming
Exercise 1.7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#lang sicp
(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 (square x)
(* x x))
(define (sqrt x)
(sqrt-iter 1.0 x))
For small numbers, specially whose square are themselves less than 0.001
the method good-enough
is not good enough as it will
return true as soon our guess reach close to 0.001
and clearly it wont be correct.
For example: (sqrt 0.00000001)
should return 0.0001
but the procedure returns 0.03125106561775382
.
For large numbers, generally computers does not support high precision. Thus the difference between two large numbers which are very close
will still result there difference more than 0.001
, no matter how close they get.
Thus the program will go into infinite recursive calls.
After changing the program with new good-enough
we get:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#lang sicp
(define (sqrt-iter oldguess newguess x)
(if (good-enough? oldguess newguess)
newguess
(sqrt-iter newguess (improve newguess x)
x)))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (good-enough? oldguess newguess)
(< (/ (abs (- oldguess newguess)) oldguess) 0.001))
(define (sqrt x)
(sqrt-iter 1.0 x x))
This programs works for small numbers as well as large numbers. Note that in racket I used numbers in decimal form like 100000000000000000.0
or 0.000000001
.
Using fractional or natural numbers takes program much larger time to finish because racket internally uses rational number which end up
generating very large numerators and denominators in the fractions.