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

$a \gets a + b\,$

$b \gets a\,$

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 $T^n\,$, 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 Tpq, where Tpq transforms the pair (a, b) according to

$a \gets bq + aq + ap\,$

and

$b \gets bp + aq\,$.

Show that if we apply such a transformation Tpq twice, the effect is the same as using a single transformation Tp'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 Tn 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 Tpq twice:

$a_1 \gets bq + aq + ap\,$

$b_1 \gets bp + aq\,$,

then

\begin{align} a_2 & \gets b_1q + a_1q + a_1p \\ & = (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p \\ & = bpq + aqq + bqq + aqq + apq + bpq + apq + app \\ & = b(pq + pq + qq) + a(pq + pq + qq) + a(qq + pp) \\ & = bq' + aq' + ap', \mbox{ where } q' = 2pq + qq \mbox{ and } p' = qq + pp \\ \end{align}

and

\begin{align} b_2 & \gets b_1p + a_1q \\ & = (bp + aq)p + (bq + aq + ap)q \\ & = bpp + apq + bqq + aqq + apq \\ & = b(pp + qq) + a(pq + pq + qq) \\ & = bp' + aq', \mbox{ where } q' = 2pq + qq \mbox{ and } p' = qq + pp \end{align}

Therefore,

$q' = 2pq + qq\,$

$p' = qq + pp\,$

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