(41) Fibonacci Decomposition (integer) - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Software Libraries (/forum-10.html) +--- Forum: HP-41C Software Library (/forum-11.html) +--- Thread: (41) Fibonacci Decomposition (integer) (/thread-14788.html) (41) Fibonacci Decomposition (integer) - SlideRule - 04-05-2020 12:48 AM 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         RE: (41) Fibonacci Decomposition (integer) - Thomas Klemm - 06-25-2022 02:10 AM 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 RE: (41) Fibonacci Decomposition (integer) - Thomas Klemm - 06-25-2022 08:15 AM 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