+- 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 ENDYou 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