Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant

[Paul Dale]

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

[Claudio L.]

(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...

[Paul Dale]

(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

[Didier Lachieze]

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

[Didier Lachieze]

(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

[Ángel Martin]

(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

[Ángel Martin]

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

[Gerson W. Barbosa]

(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.

[Gerson W. Barbosa]

(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.

[Gene]

(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? :-)

[Gerson W. Barbosa]

(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

[Gerson W. Barbosa]

(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.

[Paul Dale]

(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

[Didier Lachieze]

(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.

[John Keith]

(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

[Csaba Tizedes]

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

[Ángel Martin]

(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...

[Csaba Tizedes]

(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

[Gerson W. Barbosa]

(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.

[BartDB]

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

.