SICP-2nd-Edition-Exercise-1.7

From Boozled

Contents 1 Exercise 1.7 from SICP 2 Attempt 2.1 Small Numbers 2.2 Large Numbers 2.3 Alternative Method 3 Scheme 4 Parent Course 5 Further Reading

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.

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

Wikipedia Floating Point.

Floating-Point Representation at David Russinoffs site

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.

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.

Parent Course

6.001_Structure_and_Interpretation_of_Computer_Programs

Further Reading

Computing Roots at Wikipedia

Wikipedia Floating Point.

Floating-Point Representation at David Russinoffs site