Next: Programming Answer 7, Previous: Programming Answer 5, Up: Answers to Exercises [Contents][Index]

#### 2.7.63 Programming Tutorial Exercise 6

Here is the matrix:

    [ [ 0, 1 ]   * [a, b] = [b, a + b]
      [ 1, 1 ] ]

Thus ‘`[0, 1; 1, 1]^n * [1, 1]`’ computes Fibonacci numbers ‘`n+1`’ and ‘`n+2`’. Here’s one program that does the job:

    C-x ( ' [0, 1; 1, 1] ^ ($-1) * [1, 1] RET v u DEL C-x )

This program is quite efficient because Calc knows how to raise a matrix (or other value) to the power ‘`n`’ in only ‘`log(n,2)`’ steps. For example, this program can compute the 1000th Fibonacci number (a 209-digit integer!) in about 10 steps; even though the `Z < ... Z >` solution had much simpler steps, it would have required so many steps that it would not have been practical.