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

From Drewiki
Jump to: navigation, search

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
Personal tools