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
Retrieved from "http://wiki.drewhess.com/wiki/SICP_exercise_1.19"
Personal tools