SICP-2nd-Edition-Exercise-1.19

From Boozled

Jump to: navigation, search

Contents

Exercise 1.19 From SICP

Details from SICP are here

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 \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 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 \left(1,0\right). Now consider T to be the special case of p = 0 and q = 1 in a family of transformations Tp,q, where Tp,q transforms the pair \left(a,b\right) according to:

a \leftarrow bq + aq + ap

and

b \leftarrow bp + aq

Show that if we apply such a transformation Tp,q 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:See Footnote 41 

  1. (define (fib n)
  2.   (fib-iter 1 0 0 1 n))
  3. (define (fib-iter a b p q count)
  4.   (cond ((= count 0) b)
  5.         ((even? count)
  6.          (fib-iter a
  7.                    b
  8.                    <??>      ; compute p'
  9.                    <??>      ; compute q'
  10.                    (/ count 2)))
  11.         (else (fib-iter (+ (* b q) (* a q) (* a p))
  12.                         (+ (* b p) (* a q))
  13.                         p
  14.                         q
  15.                         (- count 1)))))

Attempt

The trick I used to get this one was to assume we had been asked for Fib(n) where n is a power of 2 . Also note that it's b that's returned. I used a spreadsheet to see what was happening with this one.

The following table shows what happens if we had been asked for Fib(16).

(a,b) (q,p) bq + aq + ap bp + aq
(1,0) (0,1) 1 1
(1,0) (1,1) 3 2
(1,0) (3,2) 21 13
(1,0) (21,13) 987 610

Scheme

  1. (define (fib n)
  2.   (fib-iter 1 0 0 1 n))
  3. (define (fib-iter a b p q count)
  4.   (cond ((= count 0) b)
  5.         ((even? count)
  6.          (display "a=")(display a) (display " b=") (display b) (display " p=") (display p) (display " q=") (display q) (newline)
  7.          (fib-iter a 
  8.                    b 
  9.                    (+ (* p p) (* q q))
  10.                    (+ (* q q) (* p q) (* q p))
  11.                    (/ count 2)))
  12.         (else (fib-iter (+ (* b q) (* a q) (* a p))
  13.                         (+ (* b p) (* a q))
  14.                         p
  15.                         q
  16.                         (- count 1)))))
  17. (display (fib 21)) ; Fib(21)=10946

Parent Course

6.001_Structure_and_Interpretation_of_Computer_Programs

Further Reading

Retrieved from "http://www.boozled.org/wiki/index.php/SICP-2nd-Edition-Exercise-1.19"
Personal tools