sicp-ex-1.19



<< Previous exercise (1.18) | sicp-solutions | Next exercise (1.20) >>


This exercise is fairly easy if we observe that, if we group a and b into a column vector, T is a linear transformation expressed by

1 1
1 0

and Tpq is, similarly,

p+q q
q p

Given this definition of Tpq, Tp'q' can be easily computed as the square of Tpq. p' and q' are, respectively

p' = p^2 + q^2
q' = 2pq + q^2

The same results can be computed without resorting to linear algebra. Just define a' and b' by applying the transformation once

a' = qb +qa + pa = (p + q)a + bq
b' = qa + pb

Then, let a" and b" be the results of applying the transformation to a' and b' and show how those values can be computed directly from a and b

a" = qb' +qa' + pa' = (p + q)a' + b'q = ... = (p^2 + 2pq + 2q^2)a + (2pq + q^2)b
b" = qa' + pb' = ... = (2pq + q^2)a + (p^2 + q^2)b

Now, it is plain to see that p' and q' are the same as the ones shown above.

Putting this all together, we can complete the given procedure

  
 ;; ex 1.19 
  
 (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 p) (square q)) 
                    (+ (* 2 p q) (square q)) 
                    (/ count 2))) 
         (else (fib-iter (+ (* b q) (* a q) (* a p)) 
                         (+ (* b p) (* a q)) 
                         p 
                         q 
                         (- count 1))))) 
  
 (define (square x) (* x x)) 
  
 ;; Testing 
 (fib 0) 
 (fib 1) 
 (fib 2) 
 (fib 3) 
 (fib 4) 
 (fib 5) 
 (fib 6) 
 (fib 7) 
 (fib 8) 
 (fib 9) 
 (fib 10) 
  

These are my self-notes as I worked through the problem. My goal was not just to implement the missing parts of the procedure (I didn't look at the book's implementation until after), but to create the entire procedure from scratch along with fully understanding the thought process behind it.

Jordan Chavez

#|
Consider the fibonacci numbers as the result of applying the following transformation:
T(a, b) = (a + b, a)
a <- a + b
b <- a
Starting with (a, b) = (0, 1) as first input and applied n times.

This can be thought of as a special case of the following transformation Tpq, defined below, with p = 0 and q = 1:

Tpq(a, b) = (bq + aq + ap, bp + aq)
a <- (bq + aq + ap)
b <- (bp + aq)

T01(a, b) = (b1 + a1 + a0, b0 + a1) = (a + b, a)

Now we need to calculate how to successively apply a particular Tpq twice. In other words, given Tpq and Txy, compute p' and q' such that Tp'q'(a, b) = Tpq(Txy(a, b))

Tpq(Txy(a, b))
Tpq(by + ay + ax, bx + ay)
((bx + ay)q + (by + ay + ax)q + (by + ay + ax)p, (bx + ay)p + (by + ay + ax)q)

Calculation for a <- (bq + aq + ap):
(bx + ay)q + (by + ay + ax)q + (by + ay + ax)p
bxq + ayq + byq + ayq + axq + byp + ayp + axp
b(xq + yp + yq) + a(xq + yp + yq) + a(xp + yq)

Calculation for b <- (bp + aq):
(bx + ay)p + (by + ay + ax)q
bxp + ayp + byq + ayq + axq
b(xp + yq) + a(xq + yp + yq)

Both calculations confirm:
p' = xp + yq
q' = xq + yp + yq

For the special case of x = p and y = q, we get:
p' = pp + qq
q' = 2pq + qq

Also note that T is commutative. Swap p<->x and q<->y and you get the same result:
p' = px + qy
q' = py + qx + qy

Finally, calculate pi and qi, the identity values such that Tpiqi(Txy) = Txy:
x = xpi + yqi
yq' = xqi + ypi + yqi
clearly (pi, qi) = (1, 0)
These identity values will form the first parameters of our "accumulator" T.

To compute fib(n), apply T01 n times to (1, 0), and take the *second* value, i.e. b

Now we can implement a logarithmic fibonacci procedure using this idea.

To understand this, think of the exponentiation example where we did a logarithmic+iterative implementation. We had an accumulator for the "odd" factors and we successively doubled the base while halving the exponent.
An example is a^15. Each number in the text below represents a power of a, so 1 means a^1, 2 means a^2, etc:

accumulator is on the left, rest is on the right:
0 111111111111111 (acc = 1,    base = a^1, exp = 15)
1 11111111111111  (acc = a,    base = a^1, exp = 14)
1 2222222         (acc = a,    base = a^2, exp =  7)
12 222222         (acc = a^3,  base = a^2, exp =  6)
12 444            (acc = a^3,  base = a^4, exp =  3)
124 44            (acc = a^7,  base = a^4, exp =  2)
124 8             (acc = a^7,  base = a^8, exp =  1)
1248              (acc = a^15, base = a^8, exp =  0)

We can apply the same idea.
Each time you replace Tpq with Tp'q', you get to halve the number of times you apply it (halving the exponent), since you're doubling the "power" of each application (squaring the base).
In other words T^n = (T^2) ^ (n/2)

Our "accumulator" is simply p-acc and q-acc that represent the parameters for the accumulated T function. Our "base" is p and q that change as we "double" the base function.
At the end we'll have p-acc and q-acc equivalent to applying T01 n times. We can compute the actual fibonacci number by taking our p-acc and q-acc, applying them to (1, 0), and taking the second value:

a <- (bq + aq + ap) = (0q + 1q + 1p) = p + q   <-- we don't care about this one at the end (it's fib(n+1))
b <- (bp + aq) = (0p + 1q) = q   <--- this is the final value fib(n)

|#

(define (fib n)
  (define (even? x)
    (= (remainder x 2) 0))
  (define (fib-iter p-acc q-acc p q n)
    (cond ((= n 0) q-acc)
          ((even? n) (fib-iter
                      p-acc
                      q-acc
                      (+ (* p p) (* q q))
                      (+ (* 2 p q) (* q q))
                      (/ n 2)))
          (else (fib-iter
                 (+ (* p p-acc) (* q q-acc))
                 (+ (* p q-acc) (* q p-acc) (* q q-acc))
                 p
                 q
                 (- n 1)))))
  (fib-iter 1 0 0 1 n))

(fib 0)
(fib 1)
(fib 2)
(fib 5)
(fib 6)
(fib 19)
(fib 20)

Substitute in the state changes and distribute/group things the solution reveals itself

Apply the first state change a <- bq + aq + ap and b <- bp + aq

T_pq(a, b)
= T_pq(bq + aq + ap, bp + aq)

Then apply another state change (there is now 2 b's and 3 a's)

T_{p'q'}(bq + aq + ap), bp + aq)
= T_{p'q'}(bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p, (bp + aq)p + (bq + aq + ap)q

Distribute everything and group like terms

(bpq + bqq + bqp) + (aqq + aqq + aqp + aqp + app), (bpp + bqq) + (aqp + aqq + apq)

Factor out b and a

b(2pq + qq) + a(qq + qq + qp + qp + pp), b(qq + pp) + a(2pq + qq)
b(2pq + qq) + a(2pq + qq) + a(qq + pp), b(qq + pp) + a(2pq + qq)

q' is 2pq + q^2 and p' is q^2 + p^2