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