Wednesday, March 22, 2017

HP 15C: Fibonacci Numbers


HP 15C: Fibonacci Numbers (Updated, bug with HP 15C LE?)
 (edited 3/23/2017)

Approximation Formula
This program calculates the nth Fibonacci number.  Store n in memory register 0 before running the program.

Formula:  ( (1 + √5)^n – (1 - √5)^n ) / (2^n * √5)

Caution:  Due to internal calculator calculation, you may not get an integer answer.  You might have to round the answer manually.   From Joe Horn, with thanks and appreciation for letting me post his comment:  

"Hi, Eddie! I just keyed up your HP-15C program for Fibonacci numbers, and noticed that it gets wrong answers due to round-off errors much of the time. For example, with an input of 5, it should output 5, but it outputs 4.9999999998. Even rounding to the nearest integer doesn't fix the problem for inputs of 40 through 49. The only way to get the right answers for all inputs is with a loop (the usual method)." - Joe Horn

 Therefore, I would recommend using this program for n < 40.  You may need to round results to the nearest integer.
Step
Key
Code
001
LBL D
42, 21, 14
002
1
1
003
ENTER
36
004
5
5
005
11
006
+
40
007
RCL 0
45, 0
008
Y^X
14
009
1
1
010
ENTER
36
011
5
5
012
11
013
-
30
014
RCL 0
45, 0
015
Y^X
14
016
-
30
017
2
2
018
RCL 0
45, 0
019
Y^X
14
020
÷
10
021
5
5
022
11
023
÷
10
024
RTN
43, 32

Example:  R0 = n = 16, Output: 987

Loop Method – Joe Horn

Joe Horn provided a more accurate program which uses loops.  It is slower, however should speed should not be a problem if a HP 15C Limited Edition or emulator is used.  Full credit and thanks goes to Joe Horn for providing this program.  

Step
Key
Code
001
LBL A
42, 21, 11
002
STO 0
44, 0
003
1
1
004
ENTER
36
005
0
0
006
LBL 1
42, 21, 1
007
+
40
008
LST X
43, 36
009
X<>Y
34
010
DSE 0
42, 5, 0
011
GTO 1
22, 1
012
RTN
43, 32

A nice part is that you don’t have to pre-store n in memory 0.   This method is accurate for n ≤ 49. 

Comparing Results
Here are some results of some selected n:

n
Approximation
Loop Method
6
8
8
15
610
610
16
987
987
22
17710.9999
17711
29
514228.9979
514229
36
14930351.92
14930352
40
102334154.4
102334155
44
701408728.7
701408733
49
7778741992
7778742049


Bug?

I manually calculated the approximation formula on my HP 15C LE (Limited Edition) and HP Prime for n = 44 and n = 49.

n = 44
HP15C LE: 701408728.7
HP Prime: 701408733.002

n = 49
HP 15C LE: 7778741992
HP Prime: 7778742049.02

I think we may have found a bug on the HP 15C LE.

Thanks to Joe Horn for the comments, much appreciated.
This blog is property of Edward Shore, 2017.



HP 15C: Fibonacci Numbers (Updated, bug with HP 15C LE?)

1 comment:

  1. The only reason the "Approximation Method" is approximate is due to the calculator's representation of √5, isn't it (other bugs notwithstanding)? It is the iterative version of the recursive function and should produce exact results if done by hand (or when evaluating √5 exactly) . When I wrote my own UserRPL version for the 48GX back in '94/'95, I had to round the result, hence the "0 RND" in the UserRPL code below.

    I have the same program now on my 50G. I ran a version without rounding, however, and, using the input set from above, got the following results:
    6 -> 8
    15 -> 610.000000002
    16 -> 987.000000003
    22 -> 17711
    29 -> 514228.999999
    36 -> 14930352
    40 -> 102334155
    44 -> 701408733
    49 -> 7778742049.04

    UserRPL is:
    \<< 5 \v/ \-> n k
    \<< 1 k + 2 / n ^
    1 k - 2 / n ^
    - k / 0 RND
    \>>
    \>>

    Cheers!

    ReplyDelete

Casio fx-3650p and HP 21S: The Intersection Point of a Quadrilateral

Casio fx-3650p and HP 21S: The Intersection Point of a Quadrilateral Introduction This program calculates the coordinates of the c...