Yet another Fibonacci mini-challenge (HP-42S/Free42)
12-05-2018, 12:59 AM
Post: #1
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
Yet another Fibonacci mini-challenge (HP-42S/Free42)
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!
12-05-2018, 02:07 AM
Post: #2
 Didier Lachieze Senior Member Posts: 1,539 Joined: Dec 2013
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)
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.
12-05-2018, 02:35 AM
Post: #3
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)
(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.
12-05-2018, 03:12 AM (This post was last modified: 12-05-2018 03:15 AM by Gerson W. Barbosa.)
Post: #4
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)
(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).
12-05-2018, 03:15 AM
Post: #5
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)
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
12-05-2018, 03:22 AM
Post: #6
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)

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
12-05-2018, 04:14 PM
Post: #7
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)
(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.
12-06-2018, 01:46 AM (This post was last modified: 12-06-2018 01:50 AM by Thomas Okken.)
Post: #8
 Thomas Okken Senior Member Posts: 1,828 Joined: Feb 2014
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)
(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-06-2018, 02:02 AM
Post: #9
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)
(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)
12-06-2018, 03:15 AM
Post: #10
 Thomas Okken Senior Member Posts: 1,828 Joined: Feb 2014
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)
Ah, I see: 1 BASE+

Nifty.
12-06-2018, 11:04 AM
Post: #11
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)
(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.
12-06-2018, 11:30 AM
Post: #12
 Thomas Okken Senior Member Posts: 1,828 Joined: Feb 2014
RE: Yet another Fibonacci mini-challenge (HP-42S/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' 36-bit arithmetic goes out of range. You do need to use IP if you want to avoid that limitation.
12-06-2018, 12:31 PM
Post: #13
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)
(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 :-)
12-07-2018, 10:42 AM
Post: #14
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)
(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
12-07-2018, 03:41 PM (This post was last modified: 12-07-2018 03:50 PM by Gerson W. Barbosa.)
Post: #15
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)
(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.
12-07-2018, 06:31 PM
Post: #16
 pier4r Senior Member Posts: 2,193 Joined: Nov 2014
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)
(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 ?

Wikis are great, Contribute :)
12-07-2018, 08:04 PM
Post: #17
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)
(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
12-07-2018, 10:49 PM (This post was last modified: 12-08-2018 01:10 AM by Gerson W. Barbosa.)
Post: #18
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)
(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.
12-08-2018, 12:31 AM
Post: #19
 Valentin Albillo Senior Member Posts: 912 Joined: Feb 2015
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)
.
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.
.

All My Articles & other Materials here:  Valentin Albillo's HP Collection

12-08-2018, 01:11 AM
Post: #20
 Gerson W. Barbosa Senior Member Posts: 1,487 Joined: Dec 2013
RE: Yet another Fibonacci mini-challenge (HP-42S/Free42)
(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.
 « Next Oldest | Next Newest »

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