(15C) Fibonacci Numbers

[Thomas Klemm]

Computation by rounding

We can use rounding to the nearest integer:

\(
F_{n}=\left\lfloor {\frac {\varphi ^{n}}{\sqrt {5}}}\right\rceil ,\ n\geq 0.
\)

However we experience errors when \(n \gt 40\).

Splitting the Index

But since the biggest value for \(n\) is only \(49\) we can use the following formulas to reduce the index:

\(
\begin{aligned}
F_{2n-1}&={F_{n}}^{2}+{F_{n-1}}^{2}\\
F_{2n}&=(2F_{n-1}+F_{n})F_{n}\\
\end{aligned}
\)

Now even in the worst case of \(F_{49}\) we can use rounding to calculate \(F_{24}\) and \(F_{25}\).

Examples

\(
\begin{aligned}
F_{44}&=&(2F_{21}+F_{22})F_{22} &=& (2 \cdot 10,946 + 17,711) \cdot 17,711 &=& 701,408,733 \\
F_{49}&=&{F_{25}}^{2}+{F_{24}}^{2} &=& 75,025^2 + 46,386^2 &=& 7,778,742,049 \\
\end{aligned}
\)

Program for the HP-15C

Code:

   001 {    42 21 11 } f LBL A
   002 {       43 20 } g x=0
   003 {       43 32 } g RTN
   004 {           1 } 1
   005 {          30 } −
   006 {           2 } 2
   007 {          10 } ÷
   008 {          36 } ENTER
   009 {       43 44 } g INT
   010 {    43 30  5 } g TEST x=y
   011 {       22  0 } GTO 0
   012 {       32  1 } GSB 1
   013 {          34 } x↔y
   014 {           2 } 2
   015 {          20 } ×
   016 {          34 } x↔y
   017 {          40 } +
   018 {       43 36 } g LSTΧ
   019 {          20 } ×
   020 {       43 32 } g RTN
   021 {    42 21  0 } f LBL 0
   022 {       32  1 } GSB 1
   023 {       43 11 } g x²
   024 {          34 } x↔y
   025 {       43 11 } g x²
   026 {          40 } +
   027 {       43 32 } g RTN
   028 {    42 21  1 } f LBL 1
   029 {           5 } 5
   030 {          11 } √x̅
   031 {          36 } ENTER
   032 {          36 } ENTER
   033 {           1 } 1
   034 {          40 } +
   035 {           2 } 2
   036 {          10 } ÷
   037 {          36 } ENTER
   038 {       43 33 } g R⬆
   039 {          14 } yˣ
   040 {       43 33 } g R⬆
   041 {          10 } ÷
   042 {          20 } ×
   043 {       43 36 } g LSTΧ
   044 {       32  2 } GSB 2
   045 {          34 } x↔y
   046 {    42 21  2 } f LBL 2
   047 {          48 } .
   048 {           5 } 5
   049 {          40 } +
   050 {       43 44 } g INT
   051 {       43 32 } g RTN

Timing

For \(F_{49}\) it takes about 5 seconds while Joe's program takes about 30 seconds.
This was measured using the Nonpareil emulator on a MacBook.
But I assume that the timing will be similar on the real calculator.

References

• Fibonacci sequence