(50g) Nth Fibonacci Number
|
02-26-2015, 07:39 PM
(This post was last modified: 02-26-2015 07:41 PM by Han.)
Post: #6
|
|||
|
|||
RE: (50g) Nth Fibonacci Number
(02-26-2015 01:42 PM)rprosperi Wrote:(02-22-2015 09:06 PM)Joe Horn Wrote: Here's my favorite exact Nth Fibonacci Number program for the 50g: Very nice! The way it works is that matrix multiplication is essentially a dot product of row i (of the left matrix) with column j (of the right matrix) to form the i,j entry in the resulting matrix. \[ \left[ \begin{array}{cc} a & b \\ c & d \end{array} \right] \cdot \left[ \begin{array}{cc} r & s \\ t & u \end{array} \right] = \left[ \begin{array}{cc} ar+bt & as+bu \\ cr+dt & cs+du \end{array} \right] \] So now let \[ A = \left[ \begin{array}{cc} F_2 & F_1 \\ F_1 & F_0 \end{array} \right] \] where \( F_0 = 0\) and \(F_1 = 1 \). Notice \( F_2 = F_1 + F_0 = 1 \). \[ A^2 = A \cdot \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] = \left[ \begin{array}{cc} F_2 & F_1 \\ F_1 & F_0 \end{array} \right] \cdot \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] = \left[ \begin{array}{cc} F_1+F_2 & F_2+0 \\ F_1+F_0 & F_1+0 \end{array} \right] = \left[ \begin{array}{cc} F_3 & F_2 \\ F_2 & F_1 \end{array} \right]\] \[ A^3 = A^2 \cdot A = \left[ \begin{array}{cc} F_3 & F_2 \\ F_2 & F_1 \end{array} \right] \cdot \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right] = \left[ \begin{array}{cc} F_4 & F_3 \\ F_3 & F_2 \end{array} \right] \] (It also works if you prefer to do \( A^n = A \cdot A^{n-1} \) since \( A \) and its powers are symmetric.) Very neat indeed. Graph 3D | QPI | SolveSys |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)