Exercise 1.19 asks us to complete a procedure for computing Fibonacci numbers in a logarithmic number of steps. The following code is given:

`(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)))))

We're reminded of the transformation of the state variables a and b in the original fib-iter procedure from section 1.2.2: a ← a + b and b ← a. If these state changes are labeled transformation T, then applying T repeatedly for n iterations starting with a = 1 and b = 0 produces the pair a = Fib(n + 1) and b = Fib(n). So the Fibonacci numbers are produced by the nth power of the transformation T, or T

^{n}, starting with the pair (1, 0).

We are then asked to consider the family of transformations T

_{pq}which transforms the pair (a, b) according to the following rules:

a ← bq + aq + ap

b ← bp + aq

b ← bp + aq

We can verify by quick substitution that the original transformation T is just a special case of T

_{pq}, where p = 0 and q = 1.

a ← b(1) + a(1) + a(0)

a ← b + a

b ← b(0) + a(1)

b ← a

a ← b + a

b ← b(0) + a(1)

b ← a

We are asked to show that if we apply 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 will give us an explicit way to square these transformations, which we can use to compute T

^{n}using successive squaring, just like the fast-expt procedure from exercise 1.16.

We can apply T

_{pq}twice by defining new variables and using substitution. Let's define a

_{1}and b

_{1}as the results of applying transformation T

_{pq}once

a

b

_{1}= bq + aq + apb

_{1}= bp + aqThe next step is to define a

_{2}and b

_{2}and apply the tranformation a second time, this time using a

_{1}and b

_{1}in place of a and b.

a

b

_{2}= b_{1}q + a_{1}q + a_{1}pb

_{2}= b_{1}p + a_{1}qNow that we have a system of equations defined, we can use substitution on our way to simplifying.

a

b

_{2}= (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)pb

_{2}= (bp + aq)p + (bq + aq + ap)qThe second equation is shorter, so it should be easier to manipulate. Remember, we're trying to find p' and q', so we need to rewrite the equation to fit the form

b

_{2}= bp' + aq'where p' and q' can be computed in terms of q and p.

b

= (bpp + apq) + (bqq + aqq + apq)

= bpp + apq + bqq + aqq + apq

= (bpp + bqq) + (2apq + aqq)

= b(pp + qq) + a(2qp + qq)

_{2}= (bp + aq)p + (bq + aq + ap)q= (bpp + apq) + (bqq + aqq + apq)

= bpp + apq + bqq + aqq + apq

= (bpp + bqq) + (2apq + aqq)

= b(pp + qq) + a(2qp + qq)

From this we can see that p' and q' can be computed using the following equations:

p' = p

q' = 2pq + q

^{2}+ q^{2}q' = 2pq + q

^{2}Manipulating the equation for a

_{2}in the same way, we can verify those results. This time we're trying to fit the form

a

_{2}= bq' + aq' + ap'The groupings required for this manipulation are made even easier by the fact that we now already know the formulas for p' and q'.

a

= (bpq + aqq) + (bqq + aqq + apq) + (bpq + apq + app)

= bpq + aqq + bqq + aqq + apq + bpq + apq + app

= (bpq + bpq + bqq) + (apq + apq + aqq) + (app + aqq)

= b(pq + pq + qq) + a(pq + pq + qq) + a(pp + qq)

= b(2pq + qq) + a(2pq + qq) + a(pp + qq)

_{2}= (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p= (bpq + aqq) + (bqq + aqq + apq) + (bpq + apq + app)

= bpq + aqq + bqq + aqq + apq + bpq + apq + app

= (bpq + bpq + bqq) + (apq + apq + aqq) + (app + aqq)

= b(pq + pq + qq) + a(pq + pq + qq) + a(pp + qq)

= b(2pq + qq) + a(2pq + qq) + a(pp + qq)

Now that we've verified the formulas for p' and q' in terms of p and q, we can use them to complete the procedure we were given.

`(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

(+ (* p p) (* q q)) ; compute p'

(+ (* 2 p q) (* q q)) ; compute q'

(/ count 2)))

(else (fib-iter (+ (* b q) (* a q) (* a p))

(+ (* b p) (* a q))

p

q

(- count 1)))))

You can test several known values in an interpreter to verify that this actually works.

`> (fib 0)`

0

> (fib 1)

1

> (fib 2)

1

> (fib 3)

2

> (fib 5)

5

> (fib 10)

55

> (fib 20)

6765

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

## 5 comments:

I suppose it's missing the point to use the closed form of the Fibonacci numbers...?

Eric,

Yes, definitely. The first code sample I showed in the article is what's given in the book, and all we have to do is fill in the blanks.

I am planning a separate article on the closed form (Binet's formula) though, since it doesn't seem to be mentioned explicitly in the book. (The authors did lead us very close to it in exercise 1.13, though.)

You might love this http://www.catonmat.net/blog/using-fibonacci-numbers-to-convert-from-miles-to-kilometers/

Your post is of course quite old, but anyhow ;-).

My copy of SICP is apparently too old and does not include this excercise. So I don't know whether the authors mention the following fact.

The logarithmic algorithm (which is a special case of a more general algorithm to compute Lucas sequences) is optimal in the sense that the number of bit operations required is proportional to the size of the result.

The same can be achieved for Binet's formula, but it is a bit tricky working out the required precision for each step (so that you have enough precision to get the correct result but not too much and ruin the bit complexity).

That is way too much unnecessary math. All you have to see is that applying your transformation T^n that is defined by p and q to those parameters will effectively square it. This is hinted by the authors (successive squaring) and I think it's overall better solution then your brute-force one.

Post a Comment