Yet another Fibonacci minichallenge (HP42S/Free42)

12052018, 12:59 AM
Post: #1




Yet another Fibonacci minichallenge (HP42S/Free42)
00 { 22Byte 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 HP42S program that computes the nth Fibonacci number ( 0 < n < 51 ) using nine steps or less, not including LBL and END. Of course, for this minichallenge bytecount 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 HP42S and Free42 are welcome as well, no matter if longer than nine or even nineteen steps. Have fun! 

12052018, 02:07 AM
Post: #2




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
Seven steps, not including LBL and END:
Code: 00 { 19Byte Prgm } It works also on the HP41. 

12052018, 02:35 AM
Post: #3




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
(12052018 02:07 AM)Didier Lachieze Wrote: Seven steps, not including LBL and END: 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. 

12052018, 03:12 AM
(This post was last modified: 12052018 03:15 AM by Gerson W. Barbosa.)
Post: #4




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
(12052018 02:07 AM)Didier Lachieze Wrote: Seven steps, not including LBL and END: 6 steps, 42Sonly: Code:
Apparently slightly faster, but not fast enough (at least on the real 42S). 

12052018, 03:15 AM
Post: #5




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
The Obvious
Code: 00 { 28Byte Prgm } The Short 5 SQRT STO 01 1 + 2 ÷ STO 00 0.5 ST0 02 Code: 00 { 17Byte Prgm } 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 { 13Byte Prgm } Thanks for the challenge. That was fun! Cheers Thomas 

12052018, 03:22 AM
Post: #6




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
Addendum
With FIX 00 we can bring it down to: Code: 00 { 10Byte Prgm } Cheers Thomas 

12052018, 04:14 PM
Post: #7




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
(12052018 03:15 AM)Thomas Klemm Wrote: The Obvious 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. (12052018 03:15 AM)Thomas Klemm Wrote: Thanks for the challenge. That was fun! Hopefully I haven't spoiled the fun :) Gerson. 

12062018, 01:46 AM
(This post was last modified: 12062018 01:50 AM by Thomas Okken.)
Post: #8




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
(12052018 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... 

12062018, 02:02 AM
Post: #9




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
(12062018 01:46 AM)Thomas Okken Wrote:(12052018 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. 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 twostep sequence for CEIL won’t work for integer arguments (which will affect F(0) only) 

12062018, 03:15 AM
Post: #10




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
Ah, I see: 1 BASE+
Nifty. 

12062018, 11:04 AM
Post: #11




RE: Yet another Fibonacci minichallenge (HP42S/Free42)  
12062018, 11:30 AM
Post: #12




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
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' 36bit arithmetic goes out of range. You do need to use IP if you want to avoid that limitation. 

12062018, 12:31 PM
Post: #13




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
(12062018 11:30 AM)Thomas Okken Wrote: NOT +/ Actually it starts to fail when n = 53 (Invalid Data). It gets F(52) right, but F(51) is off by one unity. Code:
When lines 09 and 10 are deleted the bytecount drops to 19, which has driven me to think they add up to three bytes. The least bytecount, 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 :) 

12072018, 10:42 AM
Post: #14




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
(12052018 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. 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 (x1) = 1 \) to calculate the golden ratio. Kind regards Thomas 

12072018, 03:41 PM
(This post was last modified: 12072018 03:50 PM by Gerson W. Barbosa.)
Post: #15




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
(12072018 10:42 AM)Thomas Klemm Wrote:(12052018 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. 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 HP15C 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. 

12072018, 06:31 PM
Post: #16




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
(12072018 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 ? Wikis are great, Contribute :) 

12072018, 08:04 PM
Post: #17




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
(12072018 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: Kind regards Thomas 

12072018, 10:49 PM
(This post was last modified: 12082018 01:10 AM by Gerson W. Barbosa.)
Post: #18




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
(12072018 06:31 PM)pier4r Wrote:(12072018 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 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. 

12082018, 12:31 AM
Post: #19




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
.
Hi, Gerson: You might consider correcting this in your original post: (12072018 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. . All My Articles & other Materials here: Valentin Albillo's HP Collection 

12082018, 01:11 AM
Post: #20




RE: Yet another Fibonacci minichallenge (HP42S/Free42)
(12082018 12:31 AM)Valentin Albillo Wrote: . Fixed. Thank you very much! Gerson. 

« Next Oldest  Next Newest »

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