Yet another Fibonacci mini-challenge (HP-42S/Free42)

[Gerson W. Barbosa]

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!

[Didier Lachieze]

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.

[Gerson W. Barbosa]

(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.

[Gerson W. Barbosa]

(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).

[Thomas Klemm]

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

[Thomas Klemm]

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

[Gerson W. Barbosa]

(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.

[Thomas Okken]

(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...

[Gerson W. Barbosa]

(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)

[Thomas Okken]

Ah, I see: 1 BASE+

Nifty.

[Gerson W. Barbosa]

(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.

[Thomas Okken]

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.

[Gerson W. Barbosa]

(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 :-)

[Thomas Klemm]

(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

[Gerson W. Barbosa]

(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.

[pier4r]

(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 ?

[Thomas Klemm]

(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

[Gerson W. Barbosa]

(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.

[Valentin Albillo]

.
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.
.

[Gerson W. Barbosa]

(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.