www.delorie.com/gnu/docs/calc/calc_98.html | search |
Buy the book! | |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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.
webmaster | delorie software privacy |
Copyright © 2003 by The Free Software Foundation | Updated Jun 2003 |