(41) Fibonacci Decomposition (integer)

[SlideRule]

Pages 347 & 348 from Number Theory in Science and Communication, Second Enlarged Edition, © Sprinler·Veriag Berlin Heidelberg 1984 and 1986, ISBN 978-3-662-22246-1 (eBoook)

"C. A Calculator Program for Decomposing an Integer According to the Fibonacci Number System
To call the program, press
    GTO "FNS"
and enter the integer to be decomposed, for example,
    1000.
Then press
    R/S
to start the calculation. The display will show in rapid succession the Fibonacci decomposition of 1000 and the least significant term once more with two zeroes after the decimal point (because this is important in a winning strategy for nim-like games; see Chap. 5):
    987.      13.      13.00
More specifically, in such a parlor game, when confronted with a pile of 1000 chips, take 13 away to start your winning strategy. (Rules of the game: No player can take more than twice the number of chips his predecessor just took, but each player must take at least one chip, and the first player may not take all the chips. He who takes the last chip(s) wins.)

                             Listing for "FNS"

Comment                                     Step     Code      

                                                 01        LBL "FNS"
initialize by calculating                   02        5
two constants                              03        SQRT
√5                                             04        STO 01
                                                 05        1
                                                 06        +
                                                 07        0.5
                                                 08        *
Golden Ratio                                 09        STO 02
                                                 10        LN
                                                 11        STO 03
                                                 12        RDN
subroutine for                               13        LBL 14
storing new integer
subroutine for                               14        STO 04
Fibonnacci decomposition
                                                 15        LBL 15
                                                 16        0
                                                 17        RCL 04
decomposition completed?              18        x ≤ y ?
                                                 19        GTO 13
                                                 20        RCL 01
                                                 21        *
                                                 22        LN
hyperbolic cosine                          23        COSH
from MATH 1                                24        2
                                                 25        *
                                                 26        LN
                                                 27        RCL 03
                                                 28        /
                                                 29        INT
                                                 30        RCL 02
                                                 31        x < > y
                                                 32        y^x
                                                 33        RCL 01
                                                 34        /
                                                 35        0.5
                                                 36        +
                                                 37        INT
                                                 38        FIX 0
display Fibonacci decomposition       39        PSE
                                                 40        ST- 04
                                                 41        STO 05
                                                 42        GTO 12
subroutine for recalling and             43        LBL 13
displaying least significant term       44        RCL 05
                                                 45        FIX 2
display least significant term           46        STOP
ready to start over                       47        GTO 14
                                                 48        END"

BEST!
SlideRule        

[Thomas Klemm]

This shorter program for the HP-42S may take a bit longer especially for bigger numbers:

Code:

00 { 27-Byte Prgm }
01▸LBL "FNS"
02 0
03 X<>Y
04 1
05▸LBL 00
06 X>Y?
07 GTO 01
08 STO+ ST Z
09 X<> ST Z
10 GTO 00
11▸LBL 01
12 R↓
13 RCL- ST Y
14 END

It should work with the HP-41C as well after the obvious transformations.
You may want to add a VIEW Y command at the end.

Examples

65 XEQ "FNS"

y: 55
x: 10

R/S

y: 8
x: 2

R/S

y: 2
x: 0

Therefore: \(65 = 55 + 8 + 2\)


1000 XEQ "FNS"

y: 987
x: 13

R/S

y: 13
x: 0

Therefore: \(1000 = 987 + 13\)

References

• Fibonacci coding
  

[Thomas Klemm]

It's easy to translate the program for the HP-15C:

Code:

   001 {           0 } 0
   002 {       44 25 } STO I
   003 {          34 } x↔y
   004 {           1 } 1
   005 {    42 21  0 } f LBL 0
   006 {    43 30  7 } g TEST x>y
   007 {       22  1 } GTO 1
   008 {    44 40 25 } STO + I
   009 {    42  4 25 } f Χ↔ I
   010 {       22  0 } GTO 0
   011 {    42 21  1 } f LBL 1
   012 {    42  4 25 } f Χ↔ I
   013 {          31 } R/S
   014 {          30 } −

Only the usage slightly changes.

Example

CLEAR PRGM
65

R/S
55.0000

R/S
10.0000

R/S
8.0000

R/S
2.0000

R/S
2.0000

R/S
0.0000