Peter Sheats’ Blog

So I never really expected this course to be so much about math – but I am beginning to see the importance of math more and more. It makes me wish that I had focussed more on math in school. Anyway, here’s my solution after some great help from our SICP study group.

Here’s what we are given:

a = bq + aq + ap
b = bp + aq

And we are told to apply the transformation Tpq to (a, b) using the definitions above. So we actually have:

(bq + aq + ap, bp + aq) and if we were going to apply the transformation again we would need to substitute for a and b in that pair by using algebra.

So the first part of that pair would be:

a = (bp + aq)q + (bq+aq + ap)q + (bq +aq + ap)p – by replacing every a and b with the definitions above
a = bpq + aq² + bq² + aq² + apq + bpq + aqp + ap² — factor in the q’s and p’s
a = 2bpq + 2aq² + 2aqp + bq² + ap² – group similar terms
a = b(2pq + q²) + a(2pq + q²) + a(p² + q²) — factor out a’s and b’s

b = (bp + aq)p + (bq + aq + ap)q — replacing
b = bp² + apq + bq² + aq² + apq — multiply out
b = 2apq + aq² + bp² + bq² — group similar terms
b = a(2pq + q²) + b(p² + q²) — factor out a and b

So we are looking to do the following transformations:
a = bq’ + aq’ + ap’
b = bp’ + aq’

So by our calculations above we can see that
p’ = p² + q²
q’ = 2pq + q²

So then substituting those values into our procedure:

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

(define (square x)
  (* x x))