Exercise 1.19: 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: a <- a + b and b <- 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 Tn,
the nth power of the transformation T, starting with the pair (1,0).
Now consider Tpq 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 <- bq + aq + ap and b <- 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)))))
Definition of a1 and b1:
$$ a_1 \leftarrow bq + aq + ap $$
$$ b_1 \leftarrow bp + aq $$ $$ T^2_{pq} = T_{p’q'} $$ $$ a_1 = bq + aq + ap $$ $$ b_1 = bp + aq $$ $$ a_2 = b_1q + a_1q + a_1p $$ $$ b_2 = b_1p + a_1q $$
The key here is to substitute from the definition of a1 and b1 into a2
and b2 in order to get p' and q'
I start with b2 because the expression is simpler to work with. The values I get
for p' and q' must also work with a2
$$ b_2 = b_1p + a_1q = (bp+aq)p + (bq+aq+ap)q $$
$$ b_2 = bp^2+aqp + bq^2+aq^2+aqp $$
$$ b_2 = b(p^2+ q^2)+a(2qp+q^2) $$
$$ p'=(p^2+ q^2) $$
$$ q'= (2qp+q^2) $$
$$ b_2 = bp'+aq' $$
a2 is trickier to check because of the number of terms, I’ll take a few short cuts here in showing the math
$$ a_2 = bpq + aq^2 + bq^2 + aq^2 + aqp + bqp + aqp + ap^2 $$
$$ a_2 = b(2qp+q^2) + a(2qp+q^2) + a(p^2+ q^2) $$
$$ a_2 = bq'+aq'+ap' $$
Finally: \( T^2_{pq} = T_{p’q'} \) where \( p'= p^2 + q^2 \) and \( q'= 2qp + q^2 \)
(define (square x) (* x x))
(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)) ; compute p'
(+ (* 2 p q) (square q)) ; compute q'
(/ count 2)))
(else
(fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))
> (fib 10)
55
> (fib 100)
354224848179261915075