+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant (/thread-7783.html)
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Paul Dale - 02-18-2017 03:38 AM
The 34S [Sigma] command deliberately sums from the last term to the first on the assumption that summations will often be of convergent series and this should generally increase accuracy.
The 34S can also save a step not omitting the LBL 00 and using BACK for the looping (and INC instead of ISG if the latter is used to initialise the stack).
Pauli
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Claudio L. - 02-18-2017 04:12 AM
(02-18-2017 03:38 AM)Paul Dale Wrote: The 34S [Sigma] command deliberately sums from the last term to the first on the assumption that summations will often be of convergent series and this should generally increase accuracy.
Pauli
I didn't think of that! I'll add ∑LISTR command to do summation from end to start in newRPL, and let the user decide which direction the summation goes. While using REVLIST is fine, it's much slower than just adding in reverse order.
Can't do the reverse by default all the time because in RPL ∑LIST could very well be concatenating strings...
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Paul Dale - 02-18-2017 05:11 AM
(02-18-2017 04:12 AM)Claudio L. Wrote: I didn't think of that! I'll add ∑LISTR command to do summation from end to start in newRPL, and let the user decide which direction the summation goes.
Sorting the list by absolute value and then summing from smallest to largest would be most accurate way to do this. I didn't have this luxury in the 34S. It lacks the memory to store the terms but for newRPL, you've got them all in the list already.
Quote:While using REVLIST is fine, it's much slower than just adding in reverse order.
Wouldn't the time for the floating point additions far outweigh the time to reverse the list???
Pauli
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Didier Lachieze - 02-18-2017 07:06 AM
12 steps and 26 bytes on the WP 34S (including the END) :
Code:
01 LBL 'RFC'
02 0
03 c#001
04 1/x
05 STO+ Z
06 x<>L
07 STO+ Y
08 x<>Y
09 DSZ T
10 BACK 006
11 RCL Z
12 ENDRE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Didier Lachieze - 02-18-2017 07:36 AM
(02-16-2017 11:44 PM)Gerson W. Barbosa Wrote:(02-16-2017 10:24 PM)Paul Dale Wrote: And a summation command
[pre]LBL A
[Sigma] 00
RTN
LBL 00
FIB
1/x
[/pre]
I've not tried this code.
Pauli
Missing only three instructions between LBL A and Sigma 00:
#001
SDR 003
+
[...]
PS - Nine steps only! I had to use fourteen on the HP-41/42S.
You can do it in 7 steps (8 including the END):
Code:
01 LBL A
02 Σ 00
03 RTN
04 LBL 00
05 FIB
06 x#0?
07 1/x
08 ENDRE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Ángel Martin - 02-18-2017 08:49 AM
(02-18-2017 12:54 AM)Gerson W. Barbosa Wrote: ... I think I've found out what happened. I keyed the same program into my HP-41C and got 32 bytes, which is still the wrong byte count. In both calculators that was the last program in the catalog list. After entering another small program into the HP-41C I finally obtained 30 bytes. Apparently the CAT 1 method doesn't work for the most recent program in the calculator. I've been using an infrared module and an HP-82240B printer.
Gerson.
Probably due to the NULL bytes inserted automatically between two numeric program steps, like in the sequence below:
02 0
03 0
04 1
which adds two "hidden" bytes to the byte count.
In fact that sequence has the same byte count that if you inserted ENTER^ between each line:
02 0
03 ENTER^
04 0
05 ENTER^
06 1
Mystery solved,
ÁM
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Ángel Martin - 02-18-2017 09:22 AM
And here's the MCODE for this exercise. It includes four different functions, as follows:
1. FIB, the "straight' Fibonacci number. Enter n in X, result Fn in X and n in Lastx.
2. sFIB, partial sum of Fibonacci numbers. ("s" is the SIGMA char). Straight addition of all Fibonacci numbers up to n.
3. sIFIB, partial sum of the inverse of Fibonacci numbers, the subject of this thread. For n>=46 this is the PSI constant as Gerson explained. The execution time for n=46 is 2.87 seconds on a normal-speed HP-41.
4. FIBI, the "Fibonacci Inverse" Defined as F'n = 1/F'n-2 + 1/F'n-1. Note that this is not the same as the inverse of Fibonacci, which would simply be 1/Fn
This last one is probably of no real interest but the code was "asking for it", if you know what I mean.
Code:
082 "B"
009 "I" Sum of inverses of Fibonnaci
006 "F" PSI constant with n>-46
009 "I"
04E "S"
248 SETF 9 inverse flag
033 JNC +06
082 "B"
009 "I" Sum of Fibonacci
006 "F"
04E "S"
244 CLRF 9 not inverse
108 SETF 8 summation flag
063 JNC +12d
089 "I" Fibonnaci Inverse
002 "B" (not inverse of Fibinacci)
009 "I"
006 "F"
248 SETF 9 inverse flag
02B JNC +05
082 "B" Fibonnaci
009 "I"
006 "F"
244 CLRF 9 not inverse
104 CLRF 8 no sums
0F8 READ 3(X) x
128 WRIT 4(L)
2EE ?C#0 ALL x=0?
3A0 ?NC RTN yes, end here.
361 ?NC XQ (this includes SETDEC)
050 ->14D8 [CHK_NO_S]
05E C=0 MS absolute value
088 SETF 5 do integer portion
0ED ?NC XQ leaves result in 13-digit form
064 ->193B [INTFRC]- doesn't need DEC
0E8 WRIT 3(X) n = int(|x|)
10E A=C ALL
04E C=0 ALL
268 WRIT 9(Q) Fn-2
35C PT=12 C= 1
050 LD@PT- 1
36E ?A#C ALL n=1?
3A0 ?NC RTN yes, end here.
070 N=C ALL Fn-1
10C ?FSET 8
013 JNC +02 [NOSUM]
168 WRIT 5(M) initial sum = 1
10E A=C ALL ko = 1
04E C=0 ALL
35C PT=12 C= 1
050 LD@PT- 1
01D ?NC XQ k+1
060 ->1807 [AD2_10]
128 WRIT 4(L) k=k-1
278 READ 9(Q) Fn-2
10E A=C ALL
0B0 C=N ALL Fn-1
268 WRIT 9(Q) becomes the next Fn-2
01D ?NC XQ Fn = Fn-1 + Fn-1
060 ->1807 [AD2_10]
070 N=C ALL becomes the next Fn-1
24C ?FSET 9 inverses?
033 JNC +06 no, skip
239 ?NC XQ
060 ->188E [ONE_BY_X13]
10C ?FSET 8 summation?
027 JC +04 yes, skip
070 N=C ALL becomes the next Fn-1
10C ?FSET 8 summation?
02B JNC +05 no, skip
178 READ 5(M) get partial sum
025 ?NC XQ add term
060 ->1809 [AD1_10]
168 WRIT 5(M) update partial sum
138 READ 4(L) k
10E A=C ALL
0F8 READ 3(X) n
36E ?A#C ALL
317 JC -30d [LOOP]
0B0 C=N ALL
10C ?FSET 8 summation?
013 JNC +02 nope
178 READ 5(M)
331 ?NC GO Overflow, DropST, FillXL & Exit
002 ->00CC [NFRX]Cheers,
ÁM
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Gerson W. Barbosa - 02-18-2017 11:32 AM
(02-18-2017 08:49 AM)Ángel Martin Wrote: Probably due to the NULL bytes inserted automatically between two numeric program steps, like in the sequence below:
02 0
03 0
04 1
Which means this saves one byte on the HP-41:
02 0
03 RCL X
04 1
Cheers,
Gerson.
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Gerson W. Barbosa - 02-18-2017 11:57 AM
(02-18-2017 09:22 AM)Ángel Martin Wrote: 2. sFIB, partial sum of Fibonacci numbers. ("s" is the SIGMA char). Straight addition of all Fibonacci numbers up to n.
I can't follow MCODE so I don't know how you've implemented that. Anyway, sFIB = Fn+2 - 1.
(02-18-2017 09:22 AM)Ángel Martin Wrote: 3. sIFIB, partial sum of the inverse of Fibonacci numbers, the subject of this thread. For n>=46 this is the PSI constant as Gerson explained. The execution time for n=46 is 2.87 seconds on a normal-speed HP-41.
That's about 4.5 times faster than my RPN version! Thanks for your interest!
Gerson.
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Gene - 02-18-2017 03:08 PM
(02-18-2017 09:22 AM)Ángel Martin Wrote: And here's the MCODE for this exercise. It includes four different functions, as follows:
1. FIB, the "straight' Fibonacci number. Enter n in X, result Fn in X and n in Lastx.
2. sFIB, partial sum of Fibonacci numbers. ("s" is the SIGMA char). Straight addition of all Fibonacci numbers up to n.
3. sIFIB, partial sum of the inverse of Fibonacci numbers, the subject of this thread. For n>=46 this is the PSI constant as Gerson explained. The execution time for n=46 is 2.87 seconds on a normal-speed HP-41.
4. FIBI, the "Fibonacci Inverse" Defined as F'n = 1/F'n-2 + 1/F'n-1. Note that this is not the same as the inverse of Fibonacci, which would simply be 1/Fn
Cheers,
ÁM
Gene: And these will be added to which of your roms ? Any room in Sandmath? :-)
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Gerson W. Barbosa - 02-19-2017 01:13 AM
(02-17-2017 01:58 PM)Gerson W. Barbosa Wrote: HP-50g (50 bytes)
« 0. 1. DUP2 5. ROLL
START SWAP OVER + ROT OVER INV + UNROT
NEXT DROP2
»
HP-48G (52.5 bytes)
« 0 1 DUP2 ROT 5 ROLL
START OVER + ROT
OVER INV + SWAP ROT
NEXT DROP2
»
HP-42S
00 { 28-Byte Prgm }
01>LBL "RFC"
02 0
03 0
04 1
05>LBL 00
06 +
07 LASTX
08 1/X
09 STO+ ST Z
10 X<> ST L
11 X<>Y
12 DSE ST T
13 GTO 00
14 RCL ST Z
15 .END.
HP-41
01>LBL 'RFC
02 0
03 0
04 1
05>LBL 00
06 +
07 LASTX
08 1/X
09 STO+ Z
10 X<> L
11 X<>Y
12 DSE T
13 GTO 00
14 RCL Z
15 .END.
A couple more HP 50g programs and another HP-42S RPN program (HP-41 compatible). No improvements here except perhaps for the lesser number of steps in the latter. The second HP 50g program is 2.5 bytes longer, but has one less instruction inside the loop. I think I've tried all possible stack-order combinations, but I can't break the 50-byte barrier (which doesn't mean it's not possible, of course).
HP-50g (50 bytes)
Code:
« 0. 1. DUP2 5. ROLL
START UNROT PICK3 +
DUP UNROT INV + UNROT
NEXT DROP2
»HP-50g (52.5 bytes)
Code:
« 0. 1. DUP2 ROT 5.
ROLL
START PICK3 + SWAP
OVER INV + ROT
NEXT ROT DROP2
»HP-42S ( 28 bytes, excluding END )
Code:
00 { 28-Byte Prgm }
01>LBL "RFC"
02 0
03 RCL ST X
04 1
05>LBL 00
06 1/X
07 STO+ ST Y
08 X<> ST L
09 STO+ ST Z
10 X<> ST Z
11 DSE ST T
12 GTO 00
13 X<>Y
14 .END.HP-41 ( 29 bytes, including END )
Code:
01>LBL "RFC"
02 0
03 RCL X
04 1
05>LBL 00
06 1/X
07 ST+ Y
08 X<> L
09 ST+ Z
10 X<> ST Z
11 DSE T
12 GTO 00
13 X<>Y
14 ENDRE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Gerson W. Barbosa - 02-19-2017 01:21 AM
(02-18-2017 07:36 AM)Didier Lachieze Wrote:(02-16-2017 11:44 PM)Gerson W. Barbosa Wrote: Missing only three instructions between LBL A and Sigma 00:
#001
SDR 003
+
[...]
PS - Nine steps only! I had to use fourteen on the HP-41/42S.
You can do it in 7 steps (8 including the END):
Code:
01 LBL A
02 Σ 00
03 RTN
04 LBL 00
05 FIB
06 x#0?
07 1/x
08 END
This appears to be a record for RPN. Any idea regarding the byte-count on the wp34s?
Gerson.
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Paul Dale - 02-19-2017 01:44 AM
(02-19-2017 01:21 AM)Gerson W. Barbosa Wrote: This appears to be a record for RPN. Any idea regarding the byte-count on the wp34s?
Every step is two bytes. This is true for all 34S instructions except the three letter alpha commands (which take four bytes). To be comparable to the 41 programs, there should be a LBL'RFC instead of LBL A at the start I think.
END is also interesting. If it is the final END in RAM space, it costs zero bytes. If it is between two programs it costs two bytes. I'm don't remember if the final END in the backup area or the library area costs two bytes or not.
Pauli
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Didier Lachieze - 02-19-2017 10:08 AM
(02-19-2017 01:44 AM)Paul Dale Wrote:(02-19-2017 01:21 AM)Gerson W. Barbosa Wrote: This appears to be a record for RPN. Any idea regarding the byte-count on the wp34s?
Every step is two bytes. This is true for all 34S instructions except the three letter alpha commands (which take four bytes). To be comparable to the 41 programs, there should be a LBL'RFC instead of LBL A at the start I think.
END is also interesting. If it is the final END in RAM space, it costs zero bytes. If it is between two programs it costs two bytes. I'm don't remember if the final END in the backup area or the library area costs two bytes or not.
Pauli
I think we should count the END as in real life usage you have more than one program in your calculator. So the 8-step program with a LBL'RFC instead of LBL A is 18 bytes.
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - John Keith - 02-19-2017 02:27 PM
(02-18-2017 04:12 AM)Claudio L. Wrote: While using REVLIST is fine, it's much slower than just adding in reverse order.
Can't do the reverse by default all the time because in RPL ∑LIST could very well be concatenating strings...
On a physical HP50, REVLIST adds about 10ms for an input of 66, which seems to be the smallest value that gives a correct 12-digit result. Seems to me a small price to pay for accuracy.
John
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Csaba Tizedes - 02-19-2017 04:04 PM
Little OFF, but I wrote it also for my CASIO 50f. The original version was 12 steps and works as I want.
This new version is 19 steps and collects separately the numerator and denominator:
\(\frac{N_i}{D_i}=\frac{N_{i-1}}{D_{i-1}}+\frac{1}{F_i}=\frac{F_i · N_{i-1}+D_{i-1}}{D_{i-1} · F_i}\)
This version works well also, need only one improvement: a short fraction simplification routine - I hope I can fit it into the remained 10 steps, or I must to go to fx-3600P, where 39 steps available.
The results:
Code:
i Ni Di Ni/Di Running time(s)
10 3.64E10 1.09E10 3.342.... 7.5
15 2.79E23 8.30E22 3.358.... 10.8
20 3.56E41 1.06E41 3.3597... 14.0
25 7.64E64 2.27E64 3.359872. 17.3
30 2.75E93 8.18E92 3.3598845 20.5The program code:
Code:
--------
KOUT2
+
X<->K1
=
KIN2 //F_i
--------
×
KOUT4
+
KOUT5
=
KIN4 //N_i
--------
KOUT2
KIN×5 //D_i
--------
1
KIN-3
KOUT3
x>0? //check counter
--------
[alpha]D //numerator
[alpha]E //denominator
--------The variables and initial values:
Code:
K1: F_i-1, store 0 before start
K2: F_i, store 1 before start
K3: counter, store i before start
K4: N_i-1, store 1 before start
K5: D_i-1, store 1 before startCsaba
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Ángel Martin - 02-19-2017 05:04 PM
(02-18-2017 03:08 PM)Gene Wrote: Gene: And these will be added to which of your roms ? Any room in Sandmath? :-)
The SandMath is packed but stay tuned for the forthcoming "RECURSION" module - a suitable home for these I think...
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Csaba Tizedes - 02-19-2017 06:12 PM
(02-19-2017 04:04 PM)Csaba Tizedes Wrote: need only one improvement: a short fraction simplification routine
Just tested on Maple for i=30, the simplified fraction is:
Code:
sum(1/fibonacci(i),i=1..30);
749834838730291036724679978054421559742504181594378621231
---------------------------------------------------------
2231728538440975119185120462177331245496343366535382984001.) This is significantly less numerator and denominator like without fraction simplification.
2.) The number of digits is 57 for both part, so I guess that simplify routine do not will help us (a 12 digits GCD routine maybe do not works on 57 digits numbers)
Csaba
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - Gerson W. Barbosa - 02-19-2017 07:57 PM
(02-19-2017 04:04 PM)Csaba Tizedes Wrote: Little OFF, but I wrote it also for my CASIO 50f. The original version was 12 steps and works as I want.
No, not OFF at all. Code for non-RPN/RPL calculators, new ideas and new algorithms are most welcome. Thanks for your contribution!
The following is an adaptation from an original program by C.Ret here:
TI-57
Code:
00 32 0 STO 0
01 00 0
02 32 5 STO 5
03 32 7 STO 7
04 01 1
05 86 1 2nd Lbl 1
06 32 6 STO 6
07 25 1/x
08 34 5 SUM 5
09 33 6 RCL 6
10 34 7 SUM 7
11 22 x<>t
12 56 2nd Dsz
13 51 1 GTO 1
14 33 5 RCL 5
15 81 R/S
16 71 RSTRST 36 R/S --> 3.3598856 (27 s).
Gerson.
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant - BartDB - 02-19-2017 10:25 PM
Taking into account Joe's comment on accuracy by summing from 1/F (n) first, my attempt on the 50g:
Code:
« 0. 1. 1. 4. PICK
START DUP INV 4. ROLLD
DUP ROT + NEXT
DROP2 0. 1. ROT
START + NEXT »62.5 bytes
.