Exercise 1.19 of SICP

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 $T^n$, the $n^{th}$ power of the transformation T, starting with the pair (1,0). Now consider $T_{pq}$ to be the special case of p = 0 and q = 1 in a family of transformations $T_{pq}$, where $T_{pq}$ transforms the pair (a,b) according to a <- bq + aq + ap and b <- 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 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 $a_1$ and $b_1$:

$$ 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 $a_1$ and $b_1$ into $a_2$ and $b_2$ in order to get p' and q'

I start with $b_2$ because the expression is simpler to work with. The values I get for p' and q' must also work with $a_2$

$$ 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’ $$

$a_2$ 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