Skip to main content.
-->
May 13th, 2005

Solution to SICP Exercise 1.19

Structure and Interpretation of Computer Programs

Solution to Exercise 1.19:

Tqp is defined as:

abq + aq + ap
bbp + aq

If we apply Tpq to itself, we get T2pq:

a ← (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p
b ← (bp + aq)p + (bq + aq + ap)q

With some manipulation, this can be rewritten as:

ab(2pq + q2) + a(2pq + q2) + a(p2 + q2)
bb(p2 + q2) + a(2pq + q2)

As we are looking for a transformation of the form

abq′ + aq′ + ap
bbp′ + aq

It should be fairly obvious that

p′ = p2 + q2
q′ = 2pq + q2

Now we can modify our program:

(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
                   <strong>(sum-of-squares p q)</strong>     ; compute p'
                   <strong>(+ (* 2 p q) (square q))</strong> ; 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))

(define (sum-of-squares x y)
  (+ (square x) (square y)))

Posted by Ken Dyck in Programming

No Comments »

This entry was posted on Friday, May 13th, 2005 at 8:10 pm and is filed under Programming. You can follow any responses to this entry through the comments RSS 2.0 feed. You can leave a response, or trackback from your own site.

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>