## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 1.45

## Problem

We saw in section 1.3.3 of the text that attempting to compute square roots by naively finding a fixed
point of <math>y \mapsto x/y</math> 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 <math>y \mapsto x/y^2</math>. Unfortunately, the process
does not work for fourth roots -- a single average damp is not enough to make a fixed-point search for <math>y \mapsto x/y^3</math> converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of <math>y \mapsto x/y^3</math>) the fixed-point search does converge. Do some experiments to determine how many
average damps are required to compute *n*th roots as a fixed-point search based upon repeated average
damping of <math>y \mapsto x/y^{n-1}</math>. Use this to implement a simple procedure for computing *n*th 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:

(define (average x y) (/ (+ x y) 2)) (define (average-damp f) (lambda (x) (average x (f x)))) (define tolerance 0.00001) (define (fixed-point f first-guess) (define (close-enough? v1 v2) (< (abs (- v1 v2)) tolerance)) (define (try guess) (let ((next (f guess))) (if (close-enough? guess next) next (try next)))) (try first-guess)) (define (fixed-point-of-transform g transform guess) (fixed-point (transform g) guess))

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

(define (sqrt x) (fixed-point-of-transform (lambda (y) (/ x y)) average-damp 1.0)) (define (square x) (* x x)) (define (cube-root x) (fixed-point-of-transform (lambda (y) (/ x (square y))) average-damp 1.0))

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:

(define (compose f g) (lambda (x) (f (g x)))) (define (inc x) (+ x 1)) (define (repeated f n) (define (repeated-iter i result) (if (= i n) result (repeated-iter (inc i) (compose f result)))) (repeated-iter 1 f)) (define (cube x) (* x x x)) (define (fourth-root x) (fixed-point-of-transform (lambda (y) (/ x (cube y))) (repeated average-damp 2) 1.0))

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

(fourth-root 16)

*Output:*

`
`

2.0000000000022

(fourth-root (* 3 3 3 3))

*Output:*

`
`

3.00000000000003

(fourth-root (* 7 7 7 7))

*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):

(define (fast-expt b n) (fast-expt-iter b n 1)) (define (fast-expt-iter b n a) (cond ((= n 0) a) ((even? n) (fast-expt-iter (square b) (/ n 2) a)) (else (fast-expt-iter b (- n 1) (* a b))))) (define (fifth-root x) (fixed-point-of-transform (lambda (y) (/ x (fast-expt y 4))) (repeated average-damp 2) 1.0))

Test:

(fifth-root (* 2 2 2 2 2))

*Output:*

`
`

2.00000151299576

(fifth-root (* 3 3 3 3 3))

*Output:*

`
`

3.00000088774963

(fifth-root (* 20 20 20 20 20))

*Output:*

`
`

20.000000551502

Looks good. What about 6th roots?

(define (sixth-root x) (fixed-point-of-transform (lambda (y) (/ x (fast-expt y 5))) (repeated average-damp 2) 1.0))

Test:

(sixth-root (* 2 2 2 2 2 2))

*Output:*

`
`

2.00000293346621

(sixth-root (* 20 20 20 20 20 20))

*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.

(define (eighth-root x) (fixed-point-of-transform (lambda (y) (/ x (fast-expt y 7))) (repeated average-damp 3) 1.0))

Test:

(eighth-root (fast-expt 2 8))

*Output:*

`
`

2.00000000000397

(eighth-root (fast-expt 7 8))

*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 <math>2^2</math> and 8
is <math>2^3</math>, so it looks like we need <math>floor(\log_2(n))</math> average damps to
find *n*th 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:

(define (fifteenth-root x) (fixed-point-of-transform (lambda (y) (/ x (fast-expt y 14))) (repeated average-damp 3) 1.0))

Test:

(fifteenth-root (fast-expt 2 15))

*Output:*

`
`

2.0000040951543

(fifteenth-root (fast-expt 7 15))

*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:

(define (sixteenth-root x) (fixed-point-of-transform (lambda (y) (/ x (fast-expt y 15))) (repeated average-damp 4) 1.0))

Test:

(sixteenth-root (fast-expt 2 16))

*Output:*

`
`

2.00000000007696

(sixteenth-root (fast-expt 8 16))

*Output:*

`
`

8.0

In order to do this procedurally, we need to calculate <math>floor(\log_2(n))</math>. 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:

(define (floor-log2 n) (define (iter m count) (if (= m 0) (- count 1) (iter (arithmetic-shift m -1) (inc count)))) (iter n 0))

Tests:

(floor-log2 1)

*Output:*

`
`

0

(floor-log2 2)

*Output:*

`
`

1

(floor-log2 3)

*Output:*

`
`

1

(floor-log2 4)

*Output:*

`
`

2

(floor-log2 7)

*Output:*

`
`

2

(floor-log2 8)

*Output:*

`
`

3

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

(define (nth-root x n) (let ((number-of-damps (floor-log2 n))) (fixed-point-of-transform (lambda (y) (/ x (fast-expt y (- n 1)))) (repeated average-damp number-of-damps) 1.0)))

Finally, a few tests:

(nth-root (fast-expt 2 8) 8)

*Output:*

`
`

2.00000000000397

(nth-root (fast-expt 9 13) 13)

*Output:*

`
`

8.999997309254

(nth-root (fast-expt 8 17) 17)

*Output:*

`
`

8.00000009324061