SICP-2nd-Edition-Exercise-1.7
From Boozled
Contents |
Exercise 1.7 from SICP
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 question is using the Babylonian Method to compute square roots.
- Failed to parse (Cannot write to or create math temp directory): x_0 \approx \sqrt{S}
- Failed to parse (Cannot write to or create math temp directory): x_{n+1} = \frac{1}{2} \left(x_n + \frac{S}{x_n}\right)
- Failed to parse (Cannot write to or create math temp directory): \sqrt S = \lim_{n \to \infty} x_n
Some notation to be aware of:
- Failed to parse (Cannot write to or create math temp directory): \epsilon = \mbox{acceptable error}
Attempt
Small Numbers
I am not actually too sure what the authors wanted here. I don't expect they wanted us to try and calculate a root where Failed to parse (Cannot write to or create math temp directory): \epsilon
is larger than our root. I have assumed they want us to compute ever lower numbers until we hit a problem then explain it.
If we make the number we are seeking the root for very small we must also make the Failed to parse (Cannot write to or create math temp directory): \epsilon
small enough to be able to deal with it. For instance if we use
there we must also change the definition of our good-enough? procedure accordingly. For instance the following procedure will compute a bad result if Failed to parse (Cannot write to or create math temp directory): \epsilon
is not sufficiently smaller than the number we are seeking root to.
""; This extra step is here for debugging!
So we need a procedure to make sure that Failed to parse (Cannot write to or create math temp directory): \epsilon
is sufficiently small enough that we can compute the result to see if there is a problem as we decrease the root sought.
""
If I use a standard calculator to give me the answer to sqrt(0.00000000001 I get 3.16227766e-06. The function above gives me 3.170623279538559e-06. Our relative error can be calculated as follows.
- Failed to parse (Cannot write to or create math temp directory): \eta = \frac{|v_{\text{approx}}-v|}{|v|},
- Failed to parse (Cannot write to or create math temp directory): 0.00263807 \approx \frac{|3.170623279538559\times10^-6 - 3.16227766\times10^-6|}{3.16227766\times10^-6},
We can improve on our relative error by changing the value of (epsilon) in our program.
Going back to the point that I cannot see what the authors wanted here because I seem to be able to make the function quite accurate for small values by changing our required Failed to parse (Cannot write to or create math temp directory): \epsilon . I assume they wanted us to point out that the original Failed to parse (Cannot write to or create math temp directory): \epsilon
in the book was not small enough to compute accurate roots for values approaching or less than that number. I could be wrong here.
If we decrease the number close to Failed to parse (Cannot write to or create math temp directory): \epsilon
we will most certainly get inaccurate results. For instance if Failed to parse (Cannot write to or create math temp directory): \epsilon = 0.0001 is fixed:
| Failed to parse (Cannot write to or create math temp directory): X | Relative Error |
|---|---|
| Failed to parse (Cannot write to or create math temp directory): 0.001 | Failed to parse (Cannot write to or create math temp directory): 0.03549633724272905 |
| Failed to parse (Cannot write to or create math temp directory): 0.0008 | Failed to parse (Cannot write to or create math temp directory): 0.05496301527701619 |
| Failed to parse (Cannot write to or create math temp directory): 0.0006 | Failed to parse (Cannot write to or create math temp directory): 0.0037842376707752923 |
| Failed to parse (Cannot write to or create math temp directory): 0.0004 | Failed to parse (Cannot write to or create math temp directory): 0.012015644103529066 |
| Failed to parse (Cannot write to or create math temp directory): 0.0002 | Failed to parse (Cannot write to or create math temp directory): 0.055003946635965306 |
| Failed to parse (Cannot write to or create math temp directory): 0.00015 | Failed to parse (Cannot write to or create math temp directory): 0.090908194076472 |
| Failed to parse (Cannot write to or create math temp directory): 0.00013 | Failed to parse (Cannot write to or create math temp directory): 0.11414024646177157 |
| Failed to parse (Cannot write to or create math temp directory): 0.00012 | Failed to parse (Cannot write to or create math temp directory): 0.12888245342292026 |
| Failed to parse (Cannot write to or create math temp directory): 0.00011 | Failed to parse (Cannot write to or create math temp directory): 0.12888245342292026 |
| Failed to parse (Cannot write to or create math temp directory): 0.0001 | Failed to parse (Cannot write to or create math temp directory): 0.1675473894984787 |
We can see that when our Failed to parse (Cannot write to or create math temp directory): X = \epsilon
we have a relative error of 0.17. This is not particularly great.
Large Numbers
For large numbers we can see we run into problems trying to represent floating point numbers. For instance, given:
- Failed to parse (Cannot write to or create math temp directory): \epsilon = 0.01
- Failed to parse (Cannot write to or create math temp directory): X = 70368769910000
we got the following output
- guess=8394239.560662625 x=70368769910000 epsilon= 0.01 tmp= 94487891793.46875
- guess=8388611.42179962 x=70368769910000 epsilon= 0.01 tmp= 31675947.046875
- guess=8388609.53376682 x=70368769910000 epsilon= 0.01 tmp= 3.578125
- guess=8388609.533766605 x=70368769910000 epsilon= 0.01 tmp= 0.015625
- guess=8388609.533766605 x=70368769910000 epsilon= 0.01 tmp= 0.015625
Our value for guess is now repeating so we have entered an infinite loop. For more information describing what is going on there have a look at
Alternative Method
The question asks:
- 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.
So we need to track how our guess changes and determine the ratio between iterations. This is simple enough if we resort to using global variables but I would prefer not to use this method, somehow using global variables does not seem like a Scheme/Lisp idiom I should be employing for this. The following code is my attempt at this.
"""this-guess="" last-guess="" tmp="
The method above highlights something that may be of interest. If Failed to parse (Cannot write to or create math temp directory): \epsilon = 0.01
then for Failed to parse (Cannot write to or create math temp directory): X = 70368769910000 we get a relative error of Failed to parse (Cannot write to or create math temp directory): err \approx 0.0006711514
. This is accurate but when we are using numbers as large as this if we were using this in a chain of calculations it can have a large impact. For instance, drscheme gives me (display (sqrt 70368769910000 )) = 8388609.533766607. Ysing this we can see what this equates in real terms Failed to parse (Cannot write to or create math temp directory): (8388611.42179962 - 8388609.533766607)^2 \approx 3.56 . If we had hundreds of calculations happening then this error could have quite an impact.
This new method works with numbers that are both much larger and much smaller than the previous attempts and seems to work well. At least this code completes for all the numbers I have tried with it.
Scheme
The following code may need some tidying up but it contains all the procedure I've used to complete this Exercise in their raw form. Some of the earlier procedures have been commented out etc. If you are cutting and pasting this code then you need to ask if you are actually doing the Exercise or not.
Thought: Perhaps I should only provide code snippets to discourage cut&paste.
;(define (sqrt-iter guess x); (if (good-enough? guess x); guess; (sqrt-iter (improve guess x) x); ))""; (display "this-guess=") (display this-guess) (display " last-guess=") (display last-guess) (display " tmp=") (display tmp) (newline)
;(define (good-enough? guess x); (< (abs (- (square guess) x)) epsilon)); The following function has side effects ie the display statements!;(define (good-enough? guess x); (define tmp ""); (set! tmp (abs (- (square guess) x))); (display "guess=") (display guess) (display " x=") (display x) (display " epsilon= ") (display epsilon) (display " tmp= ") (display tmp) (newline); (< tmp epsilon));(define sought 70368744180000);(/ sought 10))"Rel Error: "
Parent Course
6.001_Structure_and_Interpretation_of_Computer_Programs