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