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 22 and 8
is 23, so it looks like we need floor(log2(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(log2(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

