Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
02-20-2017, 12:40 AM
Post: #41
 Gerson W. Barbosa Senior Member Posts: 1,419 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(02-19-2017 10:25 PM)BartDB Wrote:  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

.

Nice use of the infinite stack! Well, that's what it is for, anyway.

Too bad ΣLIST doesn't work with one-element lists (any reason berhind this feature?), otherwise you could have saved 1.5 bytes:

Code:
 « 0. 1. 1. 4. PICK   START DUP INV 4. ROLLD DUP ROT +   NEXT DROP2 →LIST REVLIST ΣLIST »

60 bytes, but fails for n = 1 ( ΣLIST Error: Invalid Dimension ).

Gerson.
02-20-2017, 08:08 AM
Post: #42
 Werner Senior Member Posts: 648 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(02-17-2017 07:09 AM)Paul Dale Wrote:  Sigma is a key stroke program that Kahan sums the terms.
Pauli

(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

My respect for you guys just went up another two notches.
Werner
02-20-2017, 08:41 AM
Post: #43
 Werner Senior Member Posts: 648 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(02-17-2017 01:58 PM)Gerson W. Barbosa Wrote:  HP-48G (52.5 bytes)

« 0 1 DUP2 ROT 5 ROLL

START OVER + ROT
OVER INV + SWAP ROT

NEXT DROP2

»

I have not verified all of them, but this one is not correct.
2 returns 1.5 and it should be 2, of course.
Moreover, it's 50 bytes, not 52.5

Werner
02-20-2017, 10:34 AM
Post: #44
 Gerson W. Barbosa Senior Member Posts: 1,419 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(02-20-2017 08:41 AM)Werner Wrote:
(02-17-2017 01:58 PM)Gerson W. Barbosa Wrote:  HP-48G (52.5 bytes)

« 0 1 DUP2 ROT 5 ROLL

START OVER + ROT
OVER INV + SWAP ROT

NEXT DROP2

»

I have not verified all of them, but this one is not correct.
2 returns 1.5 and it should be 2, of course.
Moreover, it's 50 bytes, not 52.5

Werner

52.5 bytes here. Down to 50 without the first ROT, which causes the program to behave the way you mention. Are you sure you have entered it correctly?

Regards,

Gerson.
02-20-2017, 10:59 AM
Post: #45
 Werner Senior Member Posts: 648 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
I'm pretty sure I haven't ;-)
missed the ROT after the DUP2.

Werner
02-20-2017, 01:57 PM
Post: #46
 xerxes Member Posts: 113 Joined: Jun 2014
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
FX-180P solution using K vars only:

Code:
 01  Kout3  02  x<->K2  03  Kin+3  04  Kout3  05  1/x  06  Kin+4  07  1  08  Kin-1  09  Kout1  10  x>0  11  Kout4

Usage example: KAC 5 Kin1 1 Kin2 P1

or using the pending operator method:

Code:
 01  Kout3  02  x<->y  03  =  04  Kin3  05  1/x  06  Kin+2  07  1  08  Kin-1  09  Kout1  10  x>0  11  Kout2

Usage example: KAC 5 Kin1 1 + + P1

Calculator Benchmark
02-20-2017, 04:41 PM
Post: #47
 Claudio L. Senior Member Posts: 1,823 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.

(02-18-2017 05:11 AM)Paul Dale Wrote:  Wouldn't the time for the floating point additions far outweigh the time to reverse the list???

(02-19-2017 02:27 PM)John Keith Wrote:  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.

You are both right, my tests revealed (at default 32-digit precision):
REVLIST for 2000 integers on a list: 5.7 ms
INV for 2000 integers on a list: 86 ms
ΣLIST for 2000 integers on a list: 63 ms

So it's not worth adding the reverse sum, just use REVLIST. I didn't think it would be that fast.
02-21-2017, 12:33 PM
Post: #48
 Werner Senior Member Posts: 648 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
to 'Kahan sum' an exploded list, you may use:
In: ob1..obN N
Out: Sum(ob1..obN)

Code:
\<<   0 0 ROT   1 SWAP START      @ xi s c     ROT + DUP2 +    @ s y t     ROT OVER -      @ y t s-t     ROT +           @ s c   NEXT   DROP \>>

Unfortunately, for 12-digit machines it makes no difference in RFC(25) and RFC(37) (summing small to large)

Werner
02-23-2017, 09:01 PM
Post: #49
 Gerson W. Barbosa Senior Member Posts: 1,419 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
(02-21-2017 12:33 PM)Werner Wrote:  to 'Kahan sum' an exploded list, you may use:
In: ob1..obN N
Out: Sum(ob1..obN)

Code:
\<<   0 0 ROT   1 SWAP START      @ xi s c     ROT + DUP2 +    @ s y t     ROT OVER -      @ y t s-t     ROT +           @ s c   NEXT   DROP \>>

Unfortunately, for 12-digit machines it makes no difference in RFC(25) and RFC(37) (summing small to large)

But RFC(37) is now only one ULP away from the exact 12-digit result.

SysRPL which doesn't round intermediate results to 12 digits might handle these and all others, no matter the summing order, I think. But I can't check this as I am SysRPL illiterate.

Gerson.
02-23-2017, 09:15 PM
Post: #50
 Gerson W. Barbosa Senior Member Posts: 1,419 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
Just a long, slow and rather exotic solution:

Code:
 « 1. - → n   « 'Σ(n=0.,n,INV(Σ(k =0.,IP(n/2.),COMB(n-k ,k))))' EVAL   » »

Or, in HP 50g-compatible text:

Code:
 %%HP: T(3)A(R)F(.); \<< 1. - \-> n   \<< '\GS(n=0.,n,INV(\GS(k=0.,IP(n/2.),COMB(n-k,k))))' EVAL   \>> \>>

111 bytes

« 56. RFC » TEVAL --> 3.35988566622, s:30.4553

https://en.wikipedia.org/wiki/Fibonacci_number

Gerson.
02-25-2017, 02:49 PM (This post was last modified: 02-25-2017 02:55 PM by Gerson W. Barbosa.)
Post: #51
 Gerson W. Barbosa Senior Member Posts: 1,419 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
If our only goal is just to compute the constant, the following does it faster by summing up about four times as less terms and adding a correction term:

HP-42S
Code:
 00 { 39-Byte Prgm } 01>LBL "RFC" 02 STO+ ST X 03 0 04 RCL ST X 05 1 06>LBL 00 07 1/X 08 STO+ ST Y 09 X<> ST L 10 STO+ ST Z 11 X<> ST Z 12 DSE ST T 13 GTO 00 14 STO- ST Z 15 STO+ ST X 16 1/X 17 RCL+ ST Z 18 1/X 19 - 20 .END.

6 XEQ RFC --> 3.35988566624 ( 1.4 s )

HP-42S code on wp34s:

18 A --> 18 XEQ RFC --> 3.359885666243177553172011302918926 ( 0.2 s, timed with TICKS )

HP-41
Code:
 01>LBL 'RFC 02 STO+ X 03 0 04 RCL X 05 1 06>LBL 00 07 + 08 LASTX 09 1/X 10 STO+ Z 11 X<> L 12 X<>Y 13 DSE T 14 GTO 00 15 ST- Y 16 ST+ X 17 1/X 18 + 19 1/X 20 - 21 .END.

7 XEQ ALPHA RFC ALPHA --> 3.359885666 ( 3.7 s )

HP 50g
Code:
 %%HP: T(3)A(D)F(.); \<< DUP + 0. 1. DUP2 ROT 5. ROLL   START PICK3 + SWAP  OVER INV + ROT   NEXT ROT OVER + DUP + INV - INV + \>>

<< 6 RFC >> TEVAL --> 3.35988566624 ; s: .0946

Notes:

1) non-optimized codes;
2) no proof why this works.
02-25-2017, 03:01 PM
Post: #52
 Gerald H Senior Member Posts: 1,458 Joined: May 2014
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
"four times less" is a very awkward expression.
02-25-2017, 09:55 PM (This post was last modified: 02-28-2017 06:08 PM by Gerson W. Barbosa.)
Post: #53
 Gerson W. Barbosa Senior Member Posts: 1,419 Joined: Dec 2013
RE: Programming exercise (RPL/RPN) - Reciprocal Fibonacci Constant
In fact it is possible to obtain 10 digits starting with only the first four terms. A simple 7-term continued fraction suffices for the rest:

1+1+1/2+1/3 + 1/(2-1/(10-1/(12-4/(22-9/(34-16/(56-25/(90))))))) = 3.35988566602

Denominators of the continued fraction:

F(4-1)=2
F(4-1)+F(4+2)=10
10+2=12
12+10=22
22+12=34
34+22=56
56+34=90
...

Numerators:

1, 1, 1, 4, 9, 16, 25...

Equal numbers of regular terms and continued fraction terms might be better.

Edited to add a missing 's'.

PS -

Or more generically, for an even n:

$\psi \simeq \frac{1}{F_{1}}+\frac{1}{F_{2}}+\frac{1}{F_{3}}+\cdots +\frac{1}{F_{n-1}}+\frac{1}{F_{n}}+\frac{1}{F_{n-1}-\frac{1}{F_{n+2}\cdot F_{1}+F_{n-1}\cdot F_{2}-\frac{1^{2}}{F_{n+2}\cdot F_{2}+F_{n-1}\cdot F_{3}-\frac{2^{2}}{F_{n+2}\cdot F_{3}+F_{n-1}\cdot F_{4}-\frac{3^{2}}{F_{n+2}\cdot F_{4}+F_{n-1}\cdot F_{5}-\frac{4^{2}}{F_{n+2}\cdot F_{5}+F_{n-1}\cdot F_{6}-\frac{5^{2}}{F_{n+2}\cdot F_{6}+F_{n-1}\cdot F_{7}-... }}}}}}}$

PPS -

The following have been calculated with 10, 8 and 6 terms of the continued fraction, respectively.

n=2 --> 3.359876595167099
n=6 --> 3.359885666018419
n=8 --> 3.359885666243172

These examples require further tests to significantly more terms of the continued fraction.

PPPS -

Although the first four or five terms of the continued fraction in the generalization above are certainly correct it appears there is a problem with it as it obviously doesn't converge to the tree constants, no matter the number of continued fraction terms is increased, at least in my tests on the HP 50g. Anyway, these first few terms of the continued fraction do improve the convergence, especially for larger n. While this isn't solved the '=' symbol will be replaced with '≃'. Perhaps this should be done with 34 digits of accuracy on Free42 or wp34s in double precision with an equivalent RPN program.

Code:
 %%HP: T(3)A(D)F(.); \<< 0. 1. 1. 4. PICK   START DUP 4. ROLLD DUP ROT +   NEXT + 4. PICK ROT 2. + ROLLD LASTARG ROLLD LASTARG 2. - 0. 1. ROT   START SWAP INV +   NEXT 4. ROLLD 1. 4. PICK   START DUP 4. ROLLD DUP ROT +   NEXT DROP2 2. - 1.   FOR i i SQ SWAP / NEG + -1.   STEP INV NEG + INV + \>>

This is based upon Bart's program and requires two arguments: k (number of terms of the continued fraction in level 2: and n (number of terms of the regular series), with even n and k >= 3.

Examples:

10 2 --> 3.35987659517
50 2 --> 3.35987659517
100 2 --> 3.35987659517

3 4 --> 3.35988200590
4 4 --> 3.35988562091
5 4 --> 3.35988566563
6 4 --> 3.35988566601
7 4 --> 3.35988566602
10 4 --> 3.35988566602

4 6 --> 3.35988566623
5 6 --> 3.35988566624

3 8 --> 3.35988566624

PPPPS -

Now, this appears to be correct:

$\psi = \frac{1}{F_{1}}+\frac{1}{F_{2}}+\frac{1}{F_{3}}+\cdots +\frac{1}{F_{n-1}}+\frac{1}{F_{n}}+\frac{1}{F_{n-1}-\frac{F_{1}^{2}}{F_{n+2}\cdot F_{1}+F_{n-1}\cdot F_{2}-\frac{F_{2}^{2}}{F_{n+2}\cdot F_{2}+F_{n-1}\cdot F_{3}-\frac{F_{3}^{2}}{F_{n+2}\cdot F_{3}+F_{n-1}\cdot F_{4}-\frac{F_{4}^{2}}{F_{n+2}\cdot F_{4}+F_{n-1}\cdot F_{5}-\frac{F_{5}^{2}}{F_{n+2}\cdot F_{5}+F_{n-1}\cdot F_{6}-\frac{F_{6}^{2}}{F_{n+2}\cdot F_{6}+F_{n-1}\cdot F_{7}-... }}}}}}}$

This should be obvious and indeed that's what I had tried in the beginning, but somehow I skipped one index, which may have led me astray.

The first terms of the regular reciprocal series, 1/1 + 1/1 and 12 terms of the continued fraction give 12 correct digits:

2+1/(1-1/(4-1/(5-4/(9-9/(14-25/(23-64/(37-169/(60-441/(97-1156/(157-3025/(254-7921/441))))))))))) = 3.359885666241351

I will rewrite the RPL program above later and test this with 100 digits using the LongFloat library.
 « Next Oldest | Next Newest »

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