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

## Problem

There is a clever algorithm for computing the Fibonacci numbers in a logarithmic number of steps. Recall the transformation of the state variables *a* and *b* in the `fib-iter` process of section 1.2.2 of the text:

Call this transformation *T*, and observe that applying *T* over and over again *n* times, starting with 1 and 0, produces the pair Fib(*n*+1) and Fib(*n*). In other words, the Fibonacci numbers are produced by applying , the *n* th power of the transformation *T*, starting with the pair (1,0).

Now consider *T* to be the special case of *p* = 0 and *q* = 1 in a family of transformations *T*_{pq}, where *T*_{pq} transforms the pair (*a*, *b*) according to

and

.

Show that if we apply such a transformation *T*_{pq} twice, the effect is the same as using a single transformation *T*_{p'q'} of the same form, and compute *p*' and *q*' in terms of *p* and *q*. This gives us an explicit way to square these transformations, and thus we can compute *T*^{n} using successive squaring, as in the `fast-expt` procedure.

Put this all together to complete the following procedure, which runs in a logarithmic number of steps:

(define (fib n) (fib-iter 1 0 0 1 n)) (define (fib-iter a b p q count) (cond ((= count 0) b) ((even? count) (fib-iter a b <??> ; compute p' <??> ; compute q' (/ count 2))) (else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1)))))

## Solution

Apply the transformation *T*_{pq} twice:

,

then

and

Therefore,

Now we can fill in the missing pieces of `fib-iter`:

(define (square n) (* n n)) (define (fib n) (fib-iter 1 0 0 1 n)) (define (fib-iter a b p q count) (cond ((= count 0) b) ((even? count) (fib-iter a b (+ (square q) (square p)) (+ (* 2 p q) (square q)) (/ count 2))) (else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1)))))

Here's the previous definition of the iterative Fibonacci procedure; we'll use it to test the new version.

(define (fib-slow n) (fib-slow-iter 1 0 n)) (define (fib-slow-iter a b count) (if (= count 0) b (fib-slow-iter (+ a b) a (- count 1))))

Tests:

(fib-slow 0)

*Output:*

`
`

0

(fib 0)

*Output:*

`
`

0

(fib-slow 1)

*Output:*

`
`

1

(fib 1)

*Output:*

`
`

1

(fib-slow 2)

*Output:*

`
`

1

(fib 2)

*Output:*

`
`

1

(fib-slow 3)

*Output:*

`
`

2

(fib 3)

*Output:*

`
`

2

(fib-slow 4)

*Output:*

`
`

3

(fib 4)

*Output:*

`
`

3

(fib-slow 5)

*Output:*

`
`

5

(fib 5)

*Output:*

`
`

5

(fib-slow 6)

*Output:*

`
`

8

(fib 6)

*Output:*

`
`

8

(fib-slow 7)

*Output:*

`
`

13

(fib 7)

*Output:*

`
`

13

(fib-slow 8)

*Output:*

`
`

21

(fib 8)

*Output:*

`
`

21

(fib-slow 9)

*Output:*

`
`

34

(fib 9)

*Output:*

`
`

34

(fib-slow 10)

*Output:*

`
`

55

(fib 10)

*Output:*

`
`

55

(fib-slow 16)

*Output:*

`
`

987

(fib 16)

*Output:*

`
`

987