Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
02-18-2017, 03:38 AM
Post: #21
 Paul Dale Senior Member Posts: 1,714 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,808 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,714 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,367 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,367 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,251 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,251 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 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
02-18-2017, 11:32 AM
Post: #28
 Gerson W. Barbosa Senior Member Posts: 1,405 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,405 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,187 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,405 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,405 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,714 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,367 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: 709 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: 490 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,251 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: 490 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,405 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)