SICP exercise 1.45

From Drewiki

Problem

We saw in section 1.3.3 of the text that attempting to compute square roots by naively finding a fixed point of does not converge, and that this can be fixed by average damping. The same method works for finding cube roots as fixed points of the average-damped . Unfortunately, the process does not work for fourth roots -- a single average damp is not enough to make a fixed-point search for converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of ) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute nth roots as a fixed-point search based upon repeated average damping of . Use this to implement a simple procedure for computing nth roots using fixed-point, average-damp, and the repeated procedure of exercise 1.43. Assume that any arithmetic operations you need are available as primitives.

Solution

Here are the average-damp and fixed-point procedures from text:

Here are procedures to calculate square and cube root using a single average damp:

As indicated in the text, we need two applications of average damping for fourth roots. Let's use the procedures from the solution to exercise 1.43:

Test it (results shown are from Chicken Scheme 3.1 on a MacBook Pro running Mac OS X 10.5):

Output:

2.0000000000022

Output:

3.00000000000003

Output:

7.0

Are two average damps sufficient for 5th roots? Let's try, but first we'll define an exponentiation procedure (let's use the one from the solution to exercise 1.16):

Test:

Output:

2.00000151299576

Output:

3.00000088774963

Output:

20.000000551502

Looks good. What about 6th roots?

Test:

Output:

2.00000293346621

Output:

20.0000029326938

Also looks good. In fact, it works for 7th roots, too... but not for 8th roots. If you try to find 8th roots using this method with only two applications of average-damp, your calculation will not converge. (If you do attempt this calculation, be prepared to interrupt or kill the process running the calculation!)

However, 3 average damps for 8th roots works fine.

Test:

Output:

2.00000000000397

Output:

7.0

Looking at the results, we can begin to see a pattern emerging: 1 average damp works for up to 3rd roots, 2 are required for 4th through 7th roots, and 3 are required for 8th roots. 4 is 2² and 8 is 2³, so it looks like we need floor(log₂(n)) average damps to find nth roots, where floor is defined as the function that returns the integer part of a real number.

We can test this hypothesis by defining 15th-roots, which should require only 3 average damps if our theory is correct:

Test:

Output:

2.0000040951543

Output:

7.00000459175445

That works. And if we tried to define the procedure sixteenth-root using only 3 average damp applications, we'd find that it would not converge; but it does work with 4 average damps:

Test:

Output:

2.00000000007696

Output:

8.0

In order to do this procedurally, we need to calculate floor(log₂(n)). It turns out that we can implement it by performing successive arithmetic right shifts (each is equivalent to dividing by 2) and counting the number of shifts required to reach zero starting from n, and then subtracting one. Many Scheme implementations implement the arithmetic-shift primitive; in the combination shown below, arithmetic-shift's 2nd argument -1 tells the procedure to shift right by one bit:

Tests:

Output:

0

Output:

1

Output:

1

Output:

2

Output:

2

Output:

3

Those are all correct values. Now we can implement the procedure requested by the exercise, namely, one that finds nth roots by fixed point searches and average damping:

Finally, a few tests:

Output:

2.00000000000397

Output:

8.999997309254

Output:

8.00000009324061