Yet another Fibonacci mini-challenge (HP-42S/Free42) - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html) +--- Forum: General Forum (/forum-4.html) +--- Thread: Yet another Fibonacci mini-challenge (HP-42S/Free42) (/thread-11902.html) Pages: 1 2 Yet another Fibonacci mini-challenge (HP-42S/Free42) - Gerson W. Barbosa - 12-05-2018 12:59 AM 00 { 22-Byte Prgm } 01▸LBL "FIB" 02 03 04 05 06 07 08 09 10 11 END 11 XEQ FIB —> 89 50 XEQ FIB —> 12586269025 Write an HP-42S program that computes the nth Fibonacci number ( 0 < n < 51 ) using nine steps or less, not including LBL and END. Of course, for this mini-challenge byte-count is less relevant than number of steps. My particular application requires n in the range from 1 to 20 at most, so the above routine is ok for me. However, programs that work for n = 0 up to the largest possible argument on both the HP-42S and Free42 are welcome as well, no matter if longer than nine or even nineteen steps. Have fun! RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Didier Lachieze - 12-05-2018 02:07 AM Seven steps, not including LBL and END: Code: 00 { 19-Byte Prgm } 01▸LBL "FIB" 02 1 03 0 04 LBL 00 05 X<>Y 06 STO+ ST Y 07 DSE ST Z 08 GTO 00 09 END It works also on the HP-41. RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Gerson W. Barbosa - 12-05-2018 02:35 AM (12-05-2018 02:07 AM)Didier Lachieze Wrote:  Seven steps, not including LBL and END: Code: 00 { 19-Byte Prgm } 01▸LBL "FIB" 02 1 03 0 04 LBL 00 05 X<>Y 06 STO+ ST Y 07 DSE ST Z 08 GTO 00 09 END It works also on the HP-41. Nice! About 3.5 seconds on my real 42S for n = 50 (I thought it would take longer). I forgot to mention my running times: less than 0.5 seconds for all arguments. RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Gerson W. Barbosa - 12-05-2018 03:12 AM (12-05-2018 02:07 AM)Didier Lachieze Wrote:  Seven steps, not including LBL and END: Code: 00 { 19-Byte Prgm } 01▸LBL "FIB" 02 1 03 0 04 LBL 00 05 X<>Y 06 STO+ ST Y 07 DSE ST Z 08 GTO 00 09 END It works also on the HP-41. 6 steps, 42S-only: Code:  00 { 18-Byte Prgm } 01▸LBL "FIB" 02 1 03 LN 04▸LBL 00 05 RCL+ ST L 06 DSE ST Y 07 GTO 00 08 END Apparently slightly faster, but not fast enough (at least on the real 42S). RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Thomas Klemm - 12-05-2018 03:15 AM The Obvious Code: 00 { 28-Byte Prgm } 01 LBL "FIB" 02 5 03 SQRT 04 1 05 + 06 2 07 ÷ 08 X<>Y 09 Y↑X 10 5 11 SQRT 12 ÷ 13 0.5 14 + 15 IP 16 END The Short 5 SQRT STO 01 1 + 2 ÷ STO 00 0.5 ST0 02 Code: 00 { 17-Byte Prgm } 01 LBL "FIB" 02 RCL 00 03 X<>Y 04 Y↑X 05 RCL÷ 01 06 RCL+ 02 07 IP 08 END The Forecast We assume the default ∑REG 11 (or whatever but > 02). EXPF CL∑ RCL 01 1/X 0 ∑+ RCL 00 RCL÷ 01 1 ∑+ Code: 00 { 13-Byte Prgm } 01 LBL "FIB" 02 FCSTY 03 RCL+ 02 04 IP 05 END Thanks for the challenge. That was fun! Cheers Thomas RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Thomas Klemm - 12-05-2018 03:22 AM Addendum With FIX 00 we can bring it down to: Code: 00 { 10-Byte Prgm } 01 LBL "FIB" 02 FCSTY 03 RND 04 END Cheers Thomas RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Gerson W. Barbosa - 12-05-2018 04:14 PM (12-05-2018 03:15 AM)Thomas Klemm Wrote:  The Obvious Code: 00 { 28-Byte Prgm } 01 LBL "FIB" 02 5 03 SQRT 04 1 05 + 06 2 07 ÷ 08 X<>Y 09 Y↑X 10 5 11 SQRT 12 ÷ 13 0.5 14 + 15 IP 16 END 14 steps... if you notice that asinh(1/2) = ln(phi) then you can easily do it in ten steps. Of course some loss of accuracy is expected, but it will work for n = 0 up to n = 50. That can be slightly modified to fit in 9 steps if Fib(0) is not required. (12-05-2018 03:15 AM)Thomas Klemm Wrote:  Thanks for the challenge. That was fun! Hopefully I haven't spoiled the fun :-) Gerson. RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Thomas Okken - 12-06-2018 01:46 AM (12-05-2018 04:14 PM)Gerson W. Barbosa Wrote:  14 steps... if you notice that asinh(1/2) = ln(phi) then you can easily do it in ten steps. I'll admit I don't see it. Replacing 5 SQRT 1 + 2 / with 0.5 ASINH E^X saves three lines, so that leaves 11, not counting the LBL and the END. How do you eliminate another two lines? EDIT: oh wait, it's easy to eliminate one more line by replacing the E^X X<>Y Y^X with * E^X. But that's still one line longer than the challenge... RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Gerson W. Barbosa - 12-06-2018 02:02 AM (12-06-2018 01:46 AM)Thomas Okken Wrote:   (12-05-2018 04:14 PM)Gerson W. Barbosa Wrote:  14 steps... if you notice that asinh(1/2) = ln(phi) then you can easily do it in ten steps. I'll admit I don't see it. Replacing 5 SQRT 1 + 2 / with 0.5 ASINH E^X saves three lines, so that leaves 11, not counting the LBL and the END. How do you eliminate another two lines? EDIT: oh wait, it's easy to eliminate one more line by replacing the E^X X<>Y Y^X with * E^X. But that's still one line longer than the challenge... Yes, that’s it! For 9 steps I made a slight change in the formula: F(n) = CEIL((phi^n - 1)/sqrt(5)) The only problem is my two-step sequence for CEIL won’t work for integer arguments (which will affect F(0) only) RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Thomas Okken - 12-06-2018 03:15 AM Ah, I see: 1 BASE+ Nifty. RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Gerson W. Barbosa - 12-06-2018 11:04 AM (12-06-2018 03:15 AM)Thomas Okken Wrote:  Ah, I see: 1 BASE+ Nifty. Thanks! I had considered that as well, but I’m using a two-byte alternative instead so the total byte count is 22. RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Thomas Okken - 12-06-2018 11:30 AM NOT +/- That's actually three bytes, not two, but 1 BASE+ is four bytes, so it does save one byte. Anyway, now I see why this cleverness causes this implementation to fail for n > 50: that's where the BASE functions' 36-bit arithmetic goes out of range. You do need to use IP if you want to avoid that limitation. RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Gerson W. Barbosa - 12-06-2018 12:31 PM (12-06-2018 11:30 AM)Thomas Okken Wrote:  NOT +/- Anyway, now I see why this cleverness causes this implementation to fail for n > 50: that's where the BASE functions' 36-bit arithmetic goes out of range. You do need to use IP if you want to avoid that limitation. Actually it starts to fail when n = 53 (Invalid Data). It gets F(52) right, but F(51) is off by one unity. Code:  00 { 22-Byte Prgm } 01▸LBL "FIB" 02 0.5 03 ASINH 04 × 05 E↑X-1 06 5 07 SQRT 08 ÷ 09 NOT 10 +/- 11 END When lines 09 and 10 are deleted the byte-count drops to 19, which has driven me to think they add up to three bytes. The least byte-count, 17, is reached when line 01 is changed to LBL F, or 15 when it is deleted. But what’s the point? MEM shows me the available memory is 1818968064 bytes :-) RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Thomas Klemm - 12-07-2018 10:42 AM (12-05-2018 04:14 PM)Gerson W. Barbosa Wrote:  … if you notice that asinh(1/2) = ln(phi) then you can easily do it in ten steps. … Hopefully I haven't spoiled the fun :-) No worries, you just made me remember an older thread where the same trick is used to solve $$x(x+1)=2n$$ (a.k.a. Inverse Little Gauss). Similarly, we can use $$x (x-1) = 1$$ to calculate the golden ratio. Kind regards Thomas RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Gerson W. Barbosa - 12-07-2018 03:41 PM (12-07-2018 10:42 AM)Thomas Klemm Wrote:   (12-05-2018 04:14 PM)Gerson W. Barbosa Wrote:  … if you notice that asinh(1/2) = ln(phi) then you can easily do it in ten steps. … Hopefully I haven't spoiled the fun :-) No worries, you just made me remember an older thread where the same trick is used to solve $$x(x+1)=2n$$ (a.k.a. Inverse Little Gauss). Similarly, we can use $$x (x-1) = 1$$ to calculate the golden ratio. By spoiling the fun I meant my somewhat premature disclosing of the inverse hyperbolic trick. Yes, I remember that old thread. Thanks for bringing it back to our attention! Meanwhile, I've tried an HP-15C version:    001 {    42 21 11 } f LBL A    002 {          48 } .    003 {           5 } 5    004 {    43 22 23 } g HYP-¹ SIN    005 {          20 } ×    006 {          12 } e^x    007 {           5 } 5    008 {          11 } √x̅    009 {          10 } ÷    010 {          48 } .    011 {           5 } 5    012 {          40 } +    013 {       43 44 } g INT    014 {       43 32 } g RTN It seems this will work for n = 0 to 41, unlike the standard formula which fails for n = 40. While testing it, I noticed that $$\varphi^{39}\approx \frac{\pi ^{17}}{2}$$. A little tweaking, making use of the apparent $$\sqrt{2}$$ factors present in both sides of the expression, gives $$\varphi \approx \sqrt[39]{\frac{\pi }{2}\left ( \pi^{16}+19\sqrt{2} \right )}$$ Cheers, Gerson. RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - pier4r - 12-07-2018 06:31 PM (12-07-2018 03:41 PM)Gerson W. Barbosa Wrote:  While testing it, I noticed that $$\varphi^{39}\approx \frac{\pi ^{17}}{2}$$. A little tweaking, making use of the apparent $$\sqrt{2}$$ factors present in both sides of the expression, gives How? I mean it is not that one computes pi to the 17 every other day. I am really interested how it comes to your mind to compute such values. Or you go through all the initial exponents. Say, 1 to 30 ? RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Thomas Klemm - 12-07-2018 08:04 PM (12-07-2018 06:31 PM)pier4r Wrote:  I am really interested how it comes to your mind to compute such values. We all know that Gerson is a wizard: Quote:Just an interesting result: 2 SQRT 23 + XEQ GL XEQ GL Kind regards Thomas RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Gerson W. Barbosa - 12-07-2018 10:49 PM (12-07-2018 06:31 PM)pier4r Wrote:   (12-07-2018 03:41 PM)Gerson W. Barbosa Wrote:  While testing it, I noticed that $$\varphi^{39}\approx \frac{\pi ^{17}}{2}$$. A little tweaking, making use of the apparent $$\sqrt{2}$$ factors present in both sides of the expression, gives How? I mean it is not that one computes pi to the 17 every other day. I am really interested how it comes to your mind to compute such values. Let’s blame it on the RPN stack which makes for quick and easy calculations. For example, fill the stack with pi and keep pressing the × key for its successive powers. After 16 keypresses the number on the display is 282844564.3, which almost matches the digits of the square root of 8. Another example: fill the stack with pi again and press × + three times. Now you get 141.4265649. Again the first five digits look familiar, don’t they? That’s the sum of the first four powers of pi. Same when raising phi to the 39th power... Edited to fix a mistake as pointed out by Valentin below. RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Valentin Albillo - 12-08-2018 12:31 AM . Hi, Gerson: You might consider correcting this in your original post: (12-07-2018 10:49 PM)Gerson W. Barbosa Wrote:  For example, fill the stack with pi and keep pressing the ENTER key for its successive powers. You really mean pressing the * ('times' key) instead, right ? Have a nice weekend and regards. V. . RE: Yet another Fibonacci mini-challenge (HP-42S/Free42) - Gerson W. Barbosa - 12-08-2018 01:11 AM (12-08-2018 12:31 AM)Valentin Albillo Wrote:  . Hi, Gerson: You might consider correcting this in your original post: (12-07-2018 10:49 PM)Gerson W. Barbosa Wrote:  For example, fill the stack with pi and keep pressing the ENTER key for its successive powers. You really mean pressing the * ('times' key) instead, right ? Have a nice weekend and regards. V. . Fixed. Thank you very much! Gerson.