View source

==Exercise 1.19 From SICP==

[http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_thm_1.19 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 [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.2 section 1.2.2:] 

<math>a \leftarrow a + b</math> and <math>b \leftarrow a</math> 

Call this transformation <math>T</math>, and observe that applying <math>T</math> over and over again '''n''' times, starting with 1 and 0, produces the pair <math>Fib(n + 1)</math> and <math>Fib(n)</math>. In other words, the Fibonacci numbers are produced by applying <math>T^n</math>, the nth power of the transformation <math>T</math>, starting with the pair <math>\left(1,0\right)</math>. Now consider <math>T</math> to be the special case of <math>p = 0</math> and <math>q = 1</math> in a family of transformations <math>T_{p,q}</math>, where <math>T_{p,q}</math> transforms the pair <math>\left(a,b\right)</math> according to:

:<math>a \leftarrow bq + aq + ap</math> 
and
:<math>b \leftarrow bp + aq</math>

Show that if we apply such a transformation <math>T_{p,q}</math> twice, the effect is the same as using a single transformation <math>T_{p',q'}</math> 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 <math>T^n</math> 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:[http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#footnote_Temp_70 See Footnote 41]

<source lang="scheme" line start=1>
(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)))))
</source>

==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).

{| style="background-color:#eeeeee;" cellpadding="5" cellspacing="0" border="1"
! (a,b)
! (q,p)
! <math>bq + aq + ap</math> 
! <math>bp + aq</math>
|-
| (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==
<source lang="scheme" line start=1>
(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (display "a=")(display a) (display " b=") (display b) (display " p=") (display p) (display " q=") (display q) (newline)
         (fib-iter a 
                   b 
                   (+ (* p p) (* q q))
                   (+ (* q q) (* p q) (* q p))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))
(display (fib 21)) ; Fib(21)=10946
</source>

==Parent Course==

[[6.001_Structure_and_Interpretation_of_Computer_Programs]]

==Further Reading==