SICP - Solution: Exercise 1.19

# SICP - Solution: Exercise 1.19

##### October 14, 2018

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 1.2.2: $a\leftarrow a+b$ and $b\leftarrow a$. Call this transformation $T$, and observe that applying $T$ over and over again $n$ times, starting with 1 and 0, produces the pair ${\text{Fib}(n+1)}$ and ${\text{Fib}(n)}$. In other words, the Fibonacci numbers are produced by applying $T^n$, the $n^{\text{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=0}$ in a family of transformations $T_{pq}$, where $T_{pq}$ transforms the pair ${(a,b)}$ according to $a\leftarrow{bq}+{aq}+{ap}$ and $b\leftarrow{bp}+{aq}$. Show that if we apply such a transformation $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 gives us an explicit way to square these transformations, and thus we can compute $T^n$ 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

To solve this problem, it is necessary expand $T_{pq}\left(T_{pq}(a,b)\right)$ and see if we can refactor it:

$$T_{pq}(a,b)=(bq+aq+ap,;bp+aq)$$

$$T_{pq}\left(T_{pq}(a,b)\right)=(\left(bp+aq\right)q+\left(bq+aq+ap\right)q+\left(bq+aq+ap\right)p,;\left(;bp+aq\right)p+\left(bq+aq+ap\right)q)$$

$$T_{pq}\left(T_{pq}(a,b)\right)=(bpq+aq^2+bq^2+aq^2+aqp+bqp+aqp+ap^2,;bp^2+aqp+bq^2+aq^2+aqp)$$

Which can be rewritten as:

$$T_{pq}\left(T_{pq}(a,b)\right)=(b(2qp+q^2)+a(q^2+p^2)+a(2qp+q^2),;b(p^2+q^2)+a(2qp+q^2))=T_{p’q'}$$

$$p'=p^2+q^2$$

$$q'=2qp+q^2$$

(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 q p) (* q q))  ;compute q'
(/ count 2)))
(else
(fib-iter (+ (* b q)
(* a q)
(* a p))
(+ (* b p)
(* a q))
p
q
(- count 1)))))

(fib 17)


Which gives the trace:

>(fib-iter 1 0 0 1 17)
>(fib-iter 1 1 0 1 16)
>(fib-iter 1 1 1 1 8)
>(fib-iter 1 1 2 3 4)
>(fib-iter 1 1 13 21 2)
>(fib-iter 1 1 610 987 1)
>(fib-iter 2584 1597 610 987 0)
<1597