(15C) Fibonacci Numbers

[Thomas Klemm]

Another idea is to calculate:

\(
\left[
\begin{matrix}
0 & 1\\
1 & 1
\end{matrix}
\right]^n
\)

Here's a Python program that uses exponentiation by squaring:

Code:

from sympy import Matrix

def fib(n):
    A = Matrix([[1, 0], [0, 1]])
    B = Matrix([[0, 1], [1, 1]])
    while n:
        if n % 2:
            A *= B
        B *= B
        n //= 2
    return A

For \(F_{49}\) we can run fib(49) to get:

\(
\left[
\begin{matrix}
4807526976 & 7778742049\\
7778742049 & 12586269025
\end{matrix}
\right]
\)

Apparently we have to pick \(7778742049\).

This program for the HP-15C uses matrix operations:

Code:

   001 {    42 21 11 } f LBL A
   002 {           2 } 2
   003 {          36 } ENTER
   004 {    42 23 11 } f DIM A
   005 {    42 23 12 } f DIM B
   006 {    42 26 13 } f RESULT C
   007 {    42 16  1 } f MATRIX 1
   008 {       43 35 } g CLx
   009 {    44 12  u } STO B
   010 {           1 } 1
   011 {    44 12  u } STO B
   012 {    44 12  u } STO B
   013 {    44 12  u } STO B
   014 {       43 32 } g RTN
   015 {    44 11  u } STO A
   016 {          34 } x↔y
   017 {    44 11  u } STO A
   018 {    44 11  u } STO A
   019 {          34 } x↔y
   020 {    44 11  u } STO A
   021 {       43 32 } g RTN
   022 {       43 33 } g R⬆
   023 {    42 21  0 } f LBL 0
   024 {       43 20 } g x=0
   025 {       22  2 } GTO 2
   026 {           2 } 2
   027 {          10 } ÷
   028 {          36 } ENTER
   029 {       43 44 } g INT
   030 {    43 30  5 } g TEST x=y
   031 {       22  1 } GTO 1
   032 {    45 16 11 } RCL MATRIX A
   033 {    45 16 12 } RCL MATRIX B
   034 {          20 } ×
   035 {    44 16 11 } STO MATRIX A
   036 {          33 } R⬇
   037 {    42 21  1 } f LBL 1
   038 {    45 16 12 } RCL MATRIX B
   039 {          36 } ENTER
   040 {          20 } ×
   041 {    44 16 12 } STO MATRIX B
   042 {          33 } R⬇
   043 {       22  0 } GTO 0
   044 {    42 21  2 } f LBL 2
   045 {    45 11  u } RCL A
   046 {    45 11  u } RCL A
   047 {       43 32 } g RTN

Example

It takes about 21 seconds to calculate \(F_{49}\).

49 A
7,778,742,049.