Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
02-18-2017, 03:38 AM
Post: #21
 Paul Dale Senior Member Posts: 1,770 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
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
02-18-2017, 04:12 AM
Post: #22
 Claudio L. Senior Member Posts: 1,847 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(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...
02-18-2017, 05:11 AM
Post: #23
 Paul Dale Senior Member Posts: 1,770 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(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
02-18-2017, 07:06 AM
Post: #24
 Didier Lachieze Senior Member Posts: 1,540 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
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 END
02-18-2017, 07:36 AM
Post: #25
 Didier Lachieze Senior Member Posts: 1,540 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(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 END
02-18-2017, 08:49 AM (This post was last modified: 02-18-2017 08:51 AM by Ángel Martin.)
Post: #26
 Ángel Martin Senior Member Posts: 1,379 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(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
02-18-2017, 09:22 AM (This post was last modified: 02-18-2017 09:26 AM by Ángel Martin.)
Post: #27
 Ángel Martin Senior Member Posts: 1,379 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
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
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
128    WRIT 4(L)        k=k-1
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
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
168    WRIT 5(M)        update partial sum
10E    A=C ALL
36E    ?A#C ALL
317    JC  -30d         [LOOP]
0B0    C=N ALL
10C    ?FSET 8          summation?
013    JNC +02          nope
331    ?NC GO           Overflow, DropST, FillXL & Exit
002    ->00CC           [NFRX]

Cheers,
ÁM
02-18-2017, 11:32 AM
Post: #28
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(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.
02-18-2017, 11:57 AM
Post: #29
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(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.
02-18-2017, 03:08 PM
Post: #30
 Gene Moderator Posts: 1,293 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(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? :-)
02-19-2017, 01:13 AM
Post: #31
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(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 END
02-19-2017, 01:21 AM
Post: #32
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(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.
02-19-2017, 01:44 AM (This post was last modified: 02-19-2017 01:48 AM by Paul Dale.)
Post: #33
 Paul Dale Senior Member Posts: 1,770 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(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
02-19-2017, 10:08 AM
Post: #34
 Didier Lachieze Senior Member Posts: 1,540 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(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.
02-19-2017, 02:27 PM
Post: #35
 John Keith Senior Member Posts: 861 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(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
02-19-2017, 04:04 PM
Post: #36
 Csaba Tizedes Senior Member Posts: 562 Joined: May 2014
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
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.5

The 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 start

Csaba
02-19-2017, 05:04 PM
Post: #37
 Ángel Martin Senior Member Posts: 1,379 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(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...
02-19-2017, 06:12 PM
Post: #38
 Csaba Tizedes Senior Member Posts: 562 Joined: May 2014
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(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
---------------------------------------------------------
223172853844097511918512046217733124549634336653538298400

1.) 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
02-19-2017, 07:57 PM (This post was last modified: 02-19-2017 08:00 PM by Gerson W. Barbosa.)
Post: #39
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(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        RST

RST 36 R/S --> 3.3598856 (27 s).

Gerson.
02-19-2017, 10:25 PM
Post: #40
 BartDB Member Posts: 162 Joined: Feb 2015
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
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

.

 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)