Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant

02162017, 08:29 PM
(This post was last modified: 02162017 08:37 PM by Gerson W. Barbosa.)
Post: #1




Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant
Quoting from Wikipedia:
"The reciprocal Fibonacci constant, or ψ, is defined as the sum of the reciprocals of the Fibonacci numbers: \(\psi = \sum_{k=1}^{\infty} \frac{1}{F_k} = \frac{1}{1} + \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{8} + \frac{1}{13} + \frac{1}{21} + \cdots.\) " Our task is to write a program, the shortest the best, to compute the partial sums of this series from k=1 up to a given n. For instance, on the HP 50g, assuming the program is named RFC: 1 RFC > 1. 2 RFC > 2. 3 RFC > 2.5 4 RFC > 2.83333333333 5 RFC > 3.03333333333 6 RFC > 3.15833333333 7 RFC > 3.23525641025 Convergence to ddigit results occurs when n is around ⌈(d*ln(100)  ln(20))/(2*ln(φ)⌉, where φ is the golden ratio (1.61803398875...). Thus, on the HP41, we will need at least 46 terms for the exact 10figure result: 45 XEQ ALPHA RFC ALPHA > 3.359885665 46 XEQ ALPHA RFC ALPHA > 3.359885666 On Free42, we can get at least 33 correct digits: 160 XEQ RFC > 3.35988566624317755317201130291892(3) By the way, this might be a breeze on the wp34s, which has FIB built in :) As a reference, my counts are HP 50g: 50 bytes HP48G: 52.5 bytes HP42S: 28 bytes (HP41 compatible) HP41CV: 33 bytes These are only second (HP41 & 42), or third (HP48 and 50 g) attempts, so there surely is room for improvement. Have fun! Gerson. 

02162017, 10:24 PM
Post: #2




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant  
02162017, 11:44 PM
(This post was last modified: 02162017 11:58 PM by Gerson W. Barbosa.)
Post: #3




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant
(02162017 10:24 PM)Paul Dale Wrote:(02162017 08:29 PM)Gerson W. Barbosa Wrote: By the way, this might be a breeze on the wp34s, which has FIB built in :) Missing only three instructions between LBL A and Sigma 00: #001 SDR 003 + I had to check Walter's Blue Book ( page 124 ). 160 A gives 34 correct digits in DOUBLE mode, BTW. Gerson. PS  Nine steps only! I had to use fourteen on the HP41/42S. 

02172017, 06:44 AM
Post: #4




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant  
02172017, 07:09 AM
Post: #5




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant
(02162017 11:44 PM)Gerson W. Barbosa Wrote: PS  Nine steps only! I had to use fourteen on the HP41/42S. Thanks for the correction I'm sure the fourteen step version will be a lot faster on the 34S than mine: FIB is a fairly expensive function and Sigma is a key stroke program that Kahan sums the terms. Pauli 

02172017, 07:29 AM
(This post was last modified: 02172017 10:46 AM by Paul Dale.)
Post: #6




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant
How's this:
Code: STO 00 Twelve steps, eighteen bytes. This doesn't use any functions they don't have, although the accuracy won't be so great. In thirteen steps, twenty bytes and no register: Code:
Pauli 

02172017, 08:03 AM
(This post was last modified: 02172017 10:43 AM by Werner.)
Post: #7




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant
How can the 42S code be 28 bytes, 41compatible, yet the 41CV code is 33 bytes?
I have 27 bytes (excluding END, but including the threeletter label) on the 42 and 25 on the 41, stackonly. Of course. Code: >LBL "RFB" Cheers, Werner 41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L 

02172017, 11:16 AM
Post: #8




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant
(02172017 08:03 AM)Werner Wrote: How can the 42S code be 28 bytes, 41compatible, yet the 41CV code is 33 bytes? Why excluding "END"? My program for the 42S is pretty close to yours. Also 27 bytes, including "END" and stack only, of course Code: 01 LBL "RFC" Günter 

02172017, 12:15 PM
Post: #9




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant
I don't count the END because the 42S doesn't, either.
Code: 06 1/X Well, I would never do this ;) Even if it doesn't seem to make any difference here. Werner 41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L 

02172017, 01:07 PM
Post: #10




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant  
02172017, 01:58 PM
Post: #11




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant
Here are mine, all stackonly of course, mainly because these run faster. However, numbered registers and local variable versions might be better if lower byte count is the only goal. Perhaps we can divide the solutions into two groups. So far for the HP42S we have a few stackonly 27byte solutions and one 25byte solution, the latter using one number register.
Congratulations to all! Gerson. HP50g (50 bytes) « 0. 1. DUP2 5. ROLL START SWAP OVER + ROT OVER INV + UNROT NEXT DROP2 » HP48G (52.5 bytes) « 0 1 DUP2 ROT 5 ROLL START OVER + ROT OVER INV + SWAP ROT NEXT DROP2 » HP42S 00 { 28Byte 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. HP41 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. 

02172017, 02:09 PM
(This post was last modified: 02172017 02:41 PM by Gerson W. Barbosa.)
Post: #12




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant
(02172017 08:03 AM)Werner Wrote: How can the 42S code be 28 bytes, 41compatible, yet the 41CV code is 33 bytes? I think it's strange too, but that's what I got on my HP41CV with CAT 1 and the printer on, after PACKING. Perhaps I should do a manual byte count. Cheers, Gerson. PS (02172017 08:03 AM)Werner Wrote: 55 XEQ RFB > 3.3598856622 (7.9 seconds) 

02172017, 02:15 PM
Post: #13




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant
(02172017 07:09 AM)Paul Dale Wrote: I'm sure the fourteen step version will be a lot faster on the 34S than mine: FIB is a fairly expensive function and Sigma is a key stroke program that Kahan sums the terms. Indeed, 21+ seconds versus slightly less than one second. Only 33 correct digits, however. Gerson. 

02172017, 02:23 PM
(This post was last modified: 02172017 02:28 PM by Gerson W. Barbosa.)
Post: #14




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant
(02172017 07:29 AM)Paul Dale Wrote: How's this: One more step, considering the initial LBL. 25 and 27 bytes on the HP42S, respectively. 55 iterations in 9.0 s and 8.1 s, respectively. Gerson. 

02172017, 09:50 PM
Post: #15




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant
(02172017 01:58 PM)Gerson W. Barbosa Wrote: [font=Courier]HP50g (50 bytes) Here's an alternative, using local variables and lists for readability: Code:
I didn't measure on stock firmware since I have my calc with newRPL, but for comparison your code was 72 bytes in newRPL and the alternative is 80 bytes. One glitch: it only works for N=3 and higher. Just a different point of view. 

02172017, 10:36 PM
Post: #16




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant
(02172017 02:09 PM)Gerson W. Barbosa Wrote:(02172017 08:03 AM)Werner Wrote: How can the 42S code be 28 bytes, 41compatible, yet the 41CV code is 33 bytes? The HP42S' byte count doesn't include the END, which of course is cheating, because that END (or .END.) really does take up three bytes. That still doesn't explain the discrepancy, though, and there is another factor that should make the 41 version one byte shorter than the 42S version, not two bytes longer: on the 42S, numbers are always preceded by a null byte, while the 41 only inserts a null byte between consecutive number lines. 

02172017, 11:54 PM
Post: #17




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant
(02172017 09:50 PM)Claudio L. Wrote:(02172017 01:58 PM)Gerson W. Barbosa Wrote: HP50g (50 bytes) 59 bytes in RPL. (02172017 09:50 PM)Claudio L. Wrote: Just a different point of view. Also, a great idea. Thank you very much for your contribution! This modified stackonly version is 1.5 bytes longer. The glitch still persists for N=1, but only because ∑LIST doesn't accept oneelement lists, at least here in old RPN. Gerson. Code:


02182017, 12:53 AM
Post: #18




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant
(02162017 08:29 PM)Gerson W. Barbosa Wrote: 7 RFC > 3.23525641025 Many of the programs submitted in this thread suffer from avoidable roundoff error due to summing the reciprocals starting with the largest and ending with the smallest, which is always a Bad Thing to do. For example, the above value is incorrect (the last digit should be 6), but if the reciprocals are summed in the opposite order, beginning with 1/F(7) and ending with 1/F(1), then the correct result is obtained. In general, the following RFC(n) when obtained by summing 1/F(1) through 1/F(n) are incorrect (in a 12digit mantissa machine), but when obtained by summing 1/F(n) through 1/F(1) they are correct (rounded to 12 significant digits of course): RFC 7; 8; 1324; 2729; 3136; and all n>=38. Both summation orders fail only for RFC 25 & 37; higher precision methods are required for those two values of n. For reference, here are their correct rounded values: RFC(25) = 3.35986409965 RFC(37) = 3.35988559927 <0ɸ0> Joe 

02182017, 12:54 AM
(This post was last modified: 02182017 12:56 AM by Gerson W. Barbosa.)
Post: #19




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant
(02172017 10:36 PM)Thomas Okken Wrote:(02172017 02:09 PM)Gerson W. Barbosa Wrote: I think it's strange too, but that's what I got on my HP41CV with CAT 1 and the printer on, after PACKING. Perhaps I should do a manual byte count. Thanks for your detailed explanation. I think I've found out what happened. I keyed the same program into my HP41C 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 HP41C 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 HP82240B printer. Gerson. 

02182017, 01:26 AM
Post: #20




RE: Programming exercise (RPL/RPN)  Reciprocal Fibonacci Constant
(02182017 12:53 AM)Joe Horn Wrote:(02162017 08:29 PM)Gerson W. Barbosa Wrote: 7 RFC > 3.23525641025 Yes, I do remember this fact from another program exercise I first did in 1984 when I was studying Pascal, exercise 8.3 in Systematic Programming, An Introduction, by Prof. Niklaus Wirth. :) That's one of the reasons, along with Kahan's sum in the builtin summation command, that Paul Dale's first wp34s program gives all 34 correct digits. I had tried REVLIST after INV in Claudio L.'s program and noticed some improvement in accuracy. Doing the sum backwards make programs longer, however. But your are right, accuracywise, that's the method that should be used. Thank you! Gerson. 

« Next Oldest  Next Newest »

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