(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
 Han Senior Member Posts: 1,883 Joined: Dec 2013
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:

Code:
<<   [[ 1 1 ]    [ 1 0 ]] SWAP ^ 2. GET >>
BYTES: 45.0 #CD5Ah

Exact mode, of course. Short & sweet. Pretty fast for a URPL program: 512th Fibonacci number (107 digits) in 0.75 seconds. 1024th Fibonacci number (214 digits) in 1.63 seconds.

Wow, completely unexpected. So, can you explain that? I follow the code, trivial as it is, so I guess I don't know the math behind the matrix power operation.

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 »

 Messages In This Thread (50g) Nth Fibonacci Number - Eddie W. Shore - 02-21-2015, 03:31 PM RE: (50g) Nth Fibonacci Number - Gerald H - 02-22-2015, 09:48 AM RE: (50g) Nth Fibonacci Number - Joe Horn - 02-22-2015, 09:06 PM RE: (50g) Nth Fibonacci Number - Offroad - 02-23-2015, 03:07 AM RE: (50g) Nth Fibonacci Number - rprosperi - 02-26-2015, 01:42 PM RE: (50g) Nth Fibonacci Number - Han - 02-26-2015 07:39 PM RE: (50g) Nth Fibonacci Number - rprosperi - 02-26-2015, 08:23 PM RE: (50g) Nth Fibonacci Number - Joe Horn - 02-26-2015, 10:19 PM RE: (50g) Nth Fibonacci Number - Thomas Klemm - 02-26-2015, 10:45 PM RE: (50g) Nth Fibonacci Number - Han - 02-27-2015, 03:29 AM RE: (50g) Nth Fibonacci Number - rprosperi - 02-27-2015, 01:31 PM RE: (50g) Nth Fibonacci Number - Thomas Klemm - 02-26-2015, 11:04 PM RE: (50g) Nth Fibonacci Number - Thomas Klemm - 02-27-2015, 05:10 AM RE: (50g) Nth Fibonacci Number - rprosperi - 02-27-2015, 01:43 PM RE: (50g) Nth Fibonacci Number - Thomas Klemm - 02-27-2015, 05:58 AM RE: (50g) Nth Fibonacci Number - rprosperi - 02-27-2015, 01:48 PM RE: (50g) Nth Fibonacci Number - Han - 02-27-2015, 02:22 PM RE: (50g) Nth Fibonacci Number - Gerald H - 02-27-2015, 03:27 PM RE: (50g) Nth Fibonacci Number - Thomas Klemm - 03-02-2015, 02:11 AM

User(s) browsing this thread: 1 Guest(s)