(35S) Fibonacci Fun for the HP35s and the number phi

[MarkHaysHarris777]

Greetings,
While playing with my new FX115es Plus from Casio I ran into the infamous Fibonacci sequence, once again, Fn = Fn-1 + Fn-2 using the classic 1 1 startup:
1 1 2 3 5 8 13 21 34 ...

The authors of the fx115 user guide were demonstrating the [Ans] + [PreAns] [=] iterative key sequence and were pleased that with the correct startup [1] [=], [+] [1] followed by repeating [Ans] + [PreAns] iteratively would generate the Fibonacci numbers line at a time 'till ad infinitum or 'till boredom; which ever came first prior to overflow.

That's the back-story; the fx115 in not programable and although the [PreAns] feature is relatively useful, the example was not terribly enlightening.

The little small exercise did give me pause to think about my new HP35s programable with classic four level stack, LASTx, RPN; ... and the iterative steps that would be necessary to conduct the same relatively painless example on the 35s--- bumping the Fibonacci sequence of numbers up the stack and out the TOP. The rules? Glad you asked: only stack manipulations allowed (no exchanges except for [x<>y]), only [+] operation, no direct nor indirect memory registers, and no loss of Fibonacci numbers until they leave the T level of the stack-- out the TOP. Also, we are assuming the classic startup of 1 1, NOT 0 1. Stop reading here and play with your HP a bit to see what you think the minimum steps are that produce the results manually, and then continue reading (you can use any classic HP to do this step).

Welcome back. The setup is:

Code:



     [1]
     [+]
     [ENTER]
     [ENTER]

... and the five(5) iterative steps are:

Code:



     [LASTx]          (retrieves old Fn-2)
     [x<>y]           (sets up the sum   LASTx will become next Fn-2)
     [+]                 (adds   Fn = Fn-1 + Fn-2    x holds Fn  y holds Fn-3)
     [LASTx]           (retrieves new Fn-2)
     [x<>y]            (x holds old Fn [new Fn-1]   y holds old Fn-1 [new Fn-2])

Try it.

So what? What if we automate the silly thing so that we can have the machine stop on whatever nth Fibonacci number we want (from a parmameter) and then allow us to step through the rest with [R/S] or watch it run 'slowly' with an embedded [PSE]?

Here is the program key sequence:

Code:


     F001  LBL F
     F002  CLSTK
     F003  0.00201               ( this sets up DSE counter register mantissa
     F004  STO C                  ( iterative counter
     F005  CLx
     F006  4                         ( default  nth  Fibonacci number (3)   1 1 2 3
     F007  STOP                   ( get operator a chance to change the default
     F008  STO+ C               ( sets the final counter   4.00201
     F009  CLx
     F010  1                         (begin  1 1  setup
     F011  +
     F012  ENTER
     F013  XEQ F020             (call iterative sequence subroutine
     F014  DSE C                  (decrement the counter and prepare to loop back
     F015  GTO F013             (loop
     F016  STOP                    (display nth Fibonacci ;   stack holds last four Fibs
     F017  XEQ F020              (begin automated continue with PSE
     F018  PSE
     F019  GTO F017              (loop ad infinitum, or until boredom
     
     F020  LASTx                    (entry point of iterative sequence subroutine
     F021  x<>y 
     F022  +
     F023  LASTx
     F024  x<>y
     F025  RTN

Run this code with the standard [XEQ] F [ENTER].

The machine will stop with 4 in x, waiting for the operator to accept the default, or change it to a higher integer. The largest integer which may be entered (without overflow) is 59. Clear the 4, and place 59 in the x stack position, then press [R/S].

Four and a half seconds later the stack will contain the last four Fibs from the nth and x will hold 956,722,026,041.

Run the program again, this time leaving the default of 4. The stack will hold

t 1
z 1
y 2
x 3

Now, press [R/S] and watch the Fibonacci numbers bump up the stack ad infinitum or boredom... whichever comes first prior to overflow.

Do THAT on your FX115es Plus, I double dare you.

PS It is well known that the ratio of any two consecutive Fibonacci numbers produces a more and more accurate convergence on the number phi:
(SQ(5)+1)/2. This happens accurately (more or less) for the HP35s at about the 29th iteration of the above program. Stop the sequence at the 29th iteration and then press [x<>y] [/] and you should see: 1.61803398875 ~phi more or less!

PSS The program may be interrupted with [R/S] but remember that since the main program never hits a RTN the program counter is stuck in the F program. Inadvertently hitting [R/S] again will restart the program (which you may not want).
To avoid this, when you're done playing, either delete F or press [GTO] [.] [.] to set the program counter to the TOP.
[/php]

Cheers
marcus

[Massimo Gnerucci]

Just a question: Why the poor Fibonacci sequence should be infamous?

[MarkHaysHarris777]

(01-22-2015 09:07 AM)Massimo Gnerucci Wrote:  Just a question: Why the poor Fibonacci sequence should be infamous?

In two words, perceived infamy. Because (as in the case of the FX115es example) the series is demonstrated with an almost trivial cast as a simple iterative summation without meaning; begging the 'perceived' infamous question, "So what?" The Fibonacci sequence is wrapped up in phi and phi, well, phi is wrapped up in virtually everything from corn rows to flower petals, from sea shells to rabbit expansion, from Greek architecture to renaissance painting.

I am fascinated with phi, and with the Fibonacci sequence (as you might have guessed); yet, I often get sort of a trivial (meh) response to the passion--- that's why infamous.

Good to meet you Massimo. Good night (at least here its night, and good).

[Didier Lachieze]

Keeping your program structure but optimizing it for the 35s feature set, you can do:

Code:

F001  LBL F
F002  0.002               ( this sets up DSE counter register mantissa – step is 1 by default
F003  STO C               ( iterative counter
F004  CLSTK
F005  4                   ( default  nth  Fibonacci number (3)   1 1 2 3
F006  STOP                ( get operator a chance to change the default
F007  STO+ C              ( sets the final counter   4.00201
F008  CLx
F009  1                   (begin  1 1  setup
F010  REGX
F011  REGX+REGY           (calculate Fn+1   
F012  DSE C               (decrement the counter and prepare to loop back
F013  GTO F011            (loop
F014  STOP                (display nth Fibonacci ;   stack holds last four Fibs
F015  REGX+REGY           (begin automated continue with PSE
F016  PSE
F017  GTO F015            (loop ad infinitum, or until boredom

• Step F002: for the DSE counter step is 1 by default, no need to specify it
• Step F004: by moving the CLSTK here you don’t need anymore the CLx
• Step F010 is to duplicate register X : REGX is accessed by [YellowShift][Mem][RDN] then select X with the left Arrow and [ENTER]
• Step F011 and step F015 are entered as equations: [EQN][enter REGX as explained above][+][enter REGY][ENTER], they replace XEQ F020 and the subroutine.
  

[MarkHaysHarris777]

(01-22-2015 10:56 AM)Didier Lachieze Wrote:  Keeping your program structure but optimizing it for the 35s feature set, you can
...

[*]Step F004: by moving the CLSTK here you don’t need anymore the CLx
[*]Step F010 is to duplicate register X : REGX is accessed by [YellowShift][Mem][RDN] then select X with the left Arrow and [ENTER]
[*]Step F011 and step F015 are entered as equations: [EQN][enter REGX as explained above][+][enter REGY][ENTER], they replace XEQ F020 and the subroutine.
[/list]

Very nice! Thanks for your comments; nice to meet you Didier! I'll play with it tomorrow... going to bed now!

[MarkHaysHarris777]

(01-22-2015 10:56 AM)Didier Lachieze Wrote:  [*]Step F010 is to duplicate register X : REGX is accessed by [YellowShift][Mem][RDN] then select X with the left Arrow and [ENTER]

Well, I finally did get to play with this late today... what an education! I am surprised at this undocumented REGX command. I finally realized that RDN means rolldown! [R|] duh. As it turns out, on the HP35s, the REGX REGY REGZ REGT commands can be accessed from *any* menu followed by a rolldown [R|]. This is huge under some circumstances, because it reduces the amount of storage required on many of my subroutines.

As is usually the case, there is a trade-off. I am not yet sure if its the inclusion of an equation EQN (REGX+REGY) in the loop, or the hidden stack commands themselves, but the new Fibonacci routine (although taking less storage steps) has a significantly longer runtime. The original stored program runs in just over 4 seconds (59th Fib #) while the new stored program with equation embedded runs in just under 7 seconds... a +75% increase in runtime!

That surprised me until I thought about it a bit... there is apparently a significant overhead in the calling mechanism to run an equation rather than using the native stack rolling manipulation; although, with the positive trade-off of having a simplified stored program with less steps in storage; 76 vs 84 bytes (17 vs 25 steps) as in this case study.

Anyway, thanks again for the fun, and the education. Every day I learn something new about HP35s, and every day I love it more than the day before!

Cheers

[Didier Lachieze]

(01-23-2015 07:08 AM)MarkHaysHarris777 Wrote:  I am surprised at this undocumented REGX command.

See "Accessing Stack Register Contents" in the 35s User's Guide Appendix B (B-7), it describes how to access the stack registers in EQN mode but doesn't describe that you can do it out of EQN mode.

(01-23-2015 07:08 AM)MarkHaysHarris777 Wrote:  I finally realized that RDN means rolldown! [R|] duh. As it turns out, on the HP35s, the REGX REGY REGZ REGT commands can be accessed from *any* menu followed by a rolldown [R|]. This is huge under some circumstances, because it reduces the amount of storage required on many of my subroutines.

I like to use the Mem menu as it makes sense for accessing registers.

(01-23-2015 07:08 AM)MarkHaysHarris777 Wrote:  As is usually the case, there is a trade-off. I am not yet sure if its the inclusion of an equation EQN (REGX+REGY) in the loop, or the hidden stack commands themselves, but the new Fibonacci routine (although taking less storage steps) has a significantly longer runtime. The original stored program runs in just over 4 seconds (59th Fib #) while the new stored program with equation embedded runs in just under 7 seconds... a +75% increase in runtime!

This is the trade-off for using equations. For step F010 you can enter it in two different ways: starting with a menu (such as Mem) and then pressing Roll down, or starting with EQN and then pressing Roll down as documented in the user's guide. You will end-up in both cases with "F010 REGX" but if you entered starting with EQN, the EQN indicator will be on and if you look at the program you'll see that entering REGX as an EQN adds 4 bytes (7 bytes for EQN vs. 3 bytes for direct entry from Mem).

[Thomas Klemm]

(01-22-2015 08:07 AM)MarkHaysHarris777 Wrote:  Stop reading here and play with your HP a bit to see what you think the minimum steps are that produce the results manually, and then continue reading (you can use any classic HP to do this step).

This is what I came up with:

Code:

+
LASTX
X<>Y

I assume this works on most classic HP calculators.

Cheers
Thomas

[MarkHaysHarris777]

(01-24-2015 01:51 AM)Thomas Klemm Wrote:  This is what I came up with:

Code:

+
LASTX
X<>Y

I assume this works on most classic HP calculators.

It does work to produce the Fibonacci sequence, but it does not meet my programming challenge because the numbers do not lift up the stack and out the TOP!

In other words at each iteration you will only have Fib numbers in X and y; z and t will contain zero. Without the REGX and REGY (hidden) instructions it takes at least five steps to generate the sequence in such a way that the numbers lift up the stack (bump up the stack and out the top) so that at any iteration past 4 the x,y,z,t stack regs will contain the last four Fib numbers in descending order as you move up the stack. So, at iteration 5 the stack will look like this:
t 1
z 2
y 3
x 5

Your algorithm will leave the stack looking like this after 5 iterations:
t 0
z 0
y 3
x 5

So just the equation REGX+REGY does the trick. Didier is correct to point out that the hidden REGx instructions are documented 'loosely' in Appendix B-7. And even so, the instructions are not very intuitive in their use, and secondarily they are painfully slow. Without the REGx instructions the minimum steps to bump the Fib numbers up the stack are five(5)
LASTx
X<>Y
+
LASTx
X<>Y

If not the intermediate results simply collapse back into the X and Y and the Z and T never get the replicated values.

Cheers


PS ... smile and wave boys, just smile and wave.

[Paul Dale]

The 34S can do this in well under five steps:

Code:

RCL L
INC X
FIB

You need to set the first value in L, but only the first (i.e. you don't need to begin with two values). Of course having a Fibonacci function helps a bit


- Pauli

[Thomas Klemm]

(01-24-2015 10:03 AM)Paul Dale Wrote:  The 34S can do this in well under five steps:

Only two steps for the HP-42S:

Code:

01 RCL ST Y
02 RCL+ ST Y

Which works as well using the WP-34S.

Or one byte shorter:

Code:

01 ENTER
02 RCL+ ST Z

Cheers
Thomas

[Thomas Klemm]

(01-24-2015 09:53 AM)MarkHaysHarris777 Wrote:  It does work to produce the Fibonacci sequence, but it does not meet my programming challenge because the numbers do not lift up the stack and out the TOP!

Oh, my bad that I missed that part. I was just wondering why you would do that calculation in an overly complicated way. Now it's clear.

Best regards
Thomas

[Paul Dale]

(01-24-2015 12:19 PM)Thomas Klemm Wrote:  Only two steps for the HP-42S:

Code:

01 RCL ST Y
02 RCL+ ST Y

Which works as well using the WP-34S.

Or one byte shorter:

Code:

01 ENTER
02 RCL+ ST Z

Yeah, I thought of this solution lying in bed last night but couldn't be bothered getting up to post it. The 34S doesn't save a byte in the second instance.


- Pauli

[MarkHaysHarris777]

(01-24-2015 10:03 AM)Paul Dale Wrote:  The 34S can do this in well under five steps:

Code:

RCL L
INC X
FIB

You need to set the first value in L, but only the first (i.e. you don't need to begin with two values). Of course having a Fibonacci function helps a bit

Yes, thanks Pauli, I'm so looking forward to having one to play with soon! Everything is either ordered or accounted for, and the cable box is under construction. The 30b's are waiting expectantly and the pogo connector is coming along nicely. I got some great pogo pins from Sparkfun (they got them shipped to me in 24 hours no extra charge) through the mails.

Thanks for all you do, buddy. I am genuinely so impressed with this project/ I think one of the best, if not the best, to come along in 15 years. Thanks again!

[Gamo]

This is my favorite Fibonacci Sequence routine.

ENTER
ENTER
Rv // Roll Down
Rv // Roll Down
+

To run simply fill the stack with 1 [ENTER] 1 then keep continue with [R/S]


Gamo

[Thomas Klemm]

(07-21-2018 01:58 AM)Gamo Wrote:  This is my favorite Fibonacci Sequence routine.

I'm afraid you neither meet MarkHaysHarris777's requirement:

(01-24-2015 09:53 AM)MarkHaysHarris777 Wrote:  

(01-24-2015 01:51 AM)Thomas Klemm Wrote:  This is what I came up with:

Code:

+
LASTX
X<>Y

I assume this works on most classic HP calculators.

It does work to produce the Fibonacci sequence, but it does not meet my programming challenge because the numbers do not lift up the stack and out the TOP!

But then I guess he doesn't care anymore.

Cheers
Thomas