HP Forums

Full Version: Fibonacci Sequence
You're currently viewing a stripped down version of our content. View the full version with proper formatting.

OK,

Following an interesting discussion earlier this evening I thought it might be fun to see just how few keystrokes you would need to calculate successive terms of the Fibonacci Sequence, preferably without using any storage registers...

I doubt it I have the best solution but thought the answer I came up with demonstrated really nicely why I like my old RPN calculator so much and that it would be interesting so see what other people came up with.

Start with a one in 'x' - all other registers zero.


Mike T.

I'm assuming this is a keystroke procedure only (not a program).

In that case, I think it's just

Enter
Enter
Roll Up
+

Then repeat, ad infinitum.

Edit: I failed to observe initially that there is no "roll up" key on most machines, including the 12C. I was surprised to realize that this also won't work on a 42S, where the keyboard up-arrow is actually BST. However, it does work on my daily calc, the 17BII, because the up-arrow key performs a RollUp. Unfortunately it is only a keystroke solution, not a program. Obviously this is not intended for RPL machines, as it depends on a revolving 4-level stack.

Edited: 21 Oct 2009, 10:23 a.m.

On an RPL machine (three command, ? keystroked):

SWAP OVER +

On a 42 (five keystrokes, two commands):

x<>y  RCL+ ST Y

Still thinking about other models....

In the 20b scientific firmware there is a generalised Fibonacci function :-)

- Pauli

Quote:
On a 42 (five keystrokes, two commands):
x<>y  RCL+ ST Y

One command:

RCL+ ST L

Edited: 20 Oct 2009, 5:51 p.m. after one or more responses were posted

Nice!

I'd come up with an alternating sequence of:

    STO+ ST Y
STO+ ST X

But that isn't nearly as nice.

- Pauli

I recently worked on this so I could try and show off the new 7 line program display mode of the 42s/Free42 in iTunes. I came up with:

01 LBL "Fibonac"
02 1
03 STO ST L
04 LBL 00
05 STOP
06 RCL+ ST L
07 GTO 00

It's not perfect because it creates the sequence 1,2,3,... instead of 1,1,2,...

Hi, all;

Amongst many others, Valentim would be one of the guys to add some valuable comments to this thread...

Cheers.

Luiz (Brazil)

Edited: 20 Oct 2009, 6:34 p.m.

Try:

01 LBL "Fibonac"
02 0
03 STO ST L
04 1
05 LBL 00
06 STOP
07 RCL+ ST L
08 GTO 00

- Pauli

Yea, that's better, but I was trying to get it to fit in 7 lines.

Replace the "0 STO ST L" with CLSTK and you get to 7 steps :-)

- Pauli

Hi
My program for the HP-41 of the Fibonacci sequence is:

01 0
02 1
03 LBL 00
04 X<>Y
05 ST+ Y
06 PSE
07 GTO 00
08 .END.

The advantages are that all terms are shown and is very efficient.

Edited: 20 Oct 2009, 7:26 p.m.

OK, a program on our old friend, the 12c, using no registers and 7 steps:

1
enter
+
pse
lastx
x<-->y
goto 03

Don- Nice work.. I love how you program the Finance Calcs!!!

On a TI A.O.S. machine like the TI-59 start with 1 in the t register and 1 in the display. Then press x<>t + and see each successive term in the display after each + .

How about:

0
E^X
LBL 00
STOP
RCL+ ST L
GTO 00

Initialization isn't pretty, but it's as non destructive as you can get, and it begins the sequence correctly.

Hi Don,

Too late for the show, anyway an alternative 12c program that produces 0,1,1,2,3,... if we don't mind clearing some registers:

01- CLEAR SIGMA
02- 1
03- x<>y
04- PSE
05- +
06- LST x
07- GTO 03

Regards,

Gerson.

LASTx
x<>y
+
That's four keystrokes on most RPN machines. On a line-addressed machine like the HP-25, the program becomes
01 LASTx
02 x<>y
03 +
04 PAUSE
05 GTO 01

Actually this exactly key sequence that I first came up with on my HP33C.

Each sucessive iteration takes just four steps/key strokes which I thought was quite efficent, but a little cumbersome to key in...

Mike T.

Very close in approach to my 'preferred' solution and it doesn't even rely on 'Last x', but since I was using an HP33C I couldn't use Roll Up...

Mike T.

After thinking about it for a little bit on my HP33C I came up with

Enter, Enter, Rdn, Rdn, +

Admittedly not the absolutly the shortest number of keystrokes but it has a certain appeal...

I like it. Has a nice rhythm to it.

In an earlier submission I gave a very short keyboard sequence for finding the series on an A.O.S. machine. The idea wasn't mine. I had seen it somewhere but couldn't locate it. Now I have found the original reference which is from V5N4/5P16 of TI PPC Notes:

Quote:
SHORTEST USEFUL ROUTINE - Samuel G. Allen sends me the shortest do-something-useful routine I have seen so far: 000: X<>T + PRT RST . With the t-register clear and 1 in the display, press RST R/S and it will print a listing of the Fibonacci numbers. ...

Another 3 command RPL:

DUP ROT +

If we can alter the initial stack conditions, it can be done in one step.

Set up the stack:

5
sqrt
1
+
2
/
ENTER
ENTER
FIX 0
5
sqrt
1/x
You'll need an additional ENTER if the FIX 0 doesn't enable stack lift.

After that, press * (multiply) to see 1. Press * again to see 1. Keep going to see 2, 3, 5, 8, 13, etc.

Not sure that qualifies as the shortest but it is interesting and does show just how useful the stack can be...

Mike T.

Impressive. Most impressive. You may be an HP Jedi yet.

Very clever!

Quote:
...it is interesting and does show just how useful the stack can be...

The stack is really useful: quite by accident (as almost everything I discover) I found it can be used to solve the equation

     x
----- = k , k > e
ln(x)

Start by filling the stack with k then iterate 'ln *' until the answer on the display converges (somewhat slowly if k is close to e) to the second real solution.

On my HP-45:

pi
ex
ENTER
ENTER
ENTER
ln * (16 times)

-> 1.084423455e02

As a comparison the HP-33s solver gives 108.442345473 (initial guess = 100). Can a non-programmable algebraic calculator do this? :-)

Gerson.

Gerson:

You asked:

Quote:
Can a non-programmable algebraic calculator do this? :-)

The answer is yes. Try this on a TI-30:

pi
INV ln
STO

then do

ln x RCL =

After 16 iterations you will see 108.44235 in the display with 108.44234529 in the display register.

I suspect that this will work with any algebraic which has a memory. It works on my Sharp EL-501W where it yields 108.4423436 after twelve iterations.

Palmer

Edited: 8 Nov 2009, 1:51 p.m.

Quote:
You asked:
Quote:
Can a non-programmable algebraic calculator do this? :-)

The answer is yes.


Thanks! Next time I'll try to solve the problem on an algebraic calculator before asking :-)
By the way, long ago, for a while, I had a TI-51-III and a TI-59. Too bad the first got broken (my fault) and the latter was stolen...

Gerson.