+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html)
+--- Forum: General Forum (/forum-4.html)
+--- Thread: HP 25 Fibonacci sequence in one program step (/thread-17577.html)
Pages: 1 2
RE: HP 25 Fibonacci sequence in one program step - C.Ret - 10-14-2021 10:03 AM
(10-13-2021 04:42 PM)Gerson W. Barbosa Wrote: RPN: Y, Z, T <- k1; X <-k2 Then * * * …
RPL: Fill the infinite stack with [ [ 1 1 ] [ 1 0 ] ] Then * * * …
![[Image: c795926ab8f80e6207800de0451de69a69b8f641]](https://wikimedia.org/api/rest_v1/media/math/render/svg/c795926ab8f80e6207800de0451de69a69b8f641)
and ![[Image: f90aae99d109a6d152d80d03d0353a5e849c560e]](https://wikimedia.org/api/rest_v1/media/math/render/svg/f90aae99d109a6d152d80d03d0353a5e849c560e)
Thank to remind me this old matrix arithmetic multiplication on RPL. I remember a few decade when I try to use power exponentiation of [[1 1][1 0]] to the n to directly get Fn value. Hard time discovering sadly that the matrix exponentiation on the HP-28C/S doesn't work with ^ instruction.
(10-13-2021 06:26 PM)Dave Britten Wrote: I think you guys have figured out the gist of it.
The solution in the book is to set FIX 0, and fill the stack thusly:
T: phi
Z: phi
Y: phi
X: 1/SQRT(5)
Where phi is the golden ratio: (SQRT(5)+1)/2. The 1/SQRT(5) term is derived from Binet's formula.
OK, now I can publish my completed trace print.
[attachment=9914]
(10-13-2021 07:35 PM)David Hayden Wrote:(10-13-2021 07:11 PM)Gerson W. Barbosa Wrote: 0 1 + Then repeat RCL + ST LThat's it!
I can't applied this trick neither on my HP-41C that miss memory recall arithmetic, nor on my HP-15C who have recall arithmetic but no stack register manipulation.
The amazing HP 42S (or succedanea DM 42S or Free 42) is really a blend of the two anthology systems.
At least, like the HP-25, the HP-41 and HP-15C need a two steps naked program « LASTx + », close to a simple RPL code leaving the Fibonacci sequence reversed in the stack initiate by 1 DUP and repeating « OVER OVER + » over and over...
RE: HP 25 Fibonacci sequence in one program step - Albert Chan - 10-14-2021 02:13 PM
(10-14-2021 10:03 AM)C.Ret Wrote:
We can use this to get fib(n+m) = fib(m)*fib(n+1) + fib(m-1)*fib(n)
If n=m, we have fib(2n) = fib(n) * (fib(n+1) + fib(n-1))
Using this, we can can 1/sqrt(5) another way
φ^n ≈ fib(2n) / fib(n) = fib(n+1) + fib(n-1) ≈ fib(n) * (φ+1/φ) = fib(n) * √5
fib(n) = round(φ^n / √5)
RE: HP 25 Fibonacci sequence in one program step - rprosperi - 10-14-2021 07:04 PM
(10-14-2021 02:13 PM)Albert Chan Wrote:(10-14-2021 10:03 AM)C.Ret Wrote:
We can use this to get fib(n+m) = fib(m)*fib(n+1) + fib(m-1)*fib(n)
If n=m, we have fib(2n) = fib(n) * (fib(n+1) + fib(n-1))
Using this, we can can 1/sqrt(5) another way
φ^n ≈ fib(2n) / fib(n) = fib(n+1) + fib(n-1) ≈ fib(n) * (φ+1/φ) = fib(n) * √5
fib(n) = round(φ^n / √5)
Looks like more than 1 program step to me....
Also, where are those functions on an HP-25? I've looked at mine again today, and just can't see them anywhere...
RE: HP 25 Fibonacci sequence in one program step - Gerson W. Barbosa - 10-16-2021 02:55 PM
(10-13-2021 08:34 PM)rprosperi Wrote: Many other models support recall arithmetic (45, 27, 15C, 32S, 32SII, others?) but only the 42S includes recall arithmetic AND stack register access.
Since we’re at it, I decided to write an HP-42S program to display the Fibonacci sequence trying to use the least number of steps (Not sure whether I’ve succeeded or not – another one I tried has exactly the same number of steps and bytes). Interestingly an equivalent HP-15C program, which lacks recall stack arithmetic but does have recall arithmetic, is possible using the same number of steps (8).
Code:
00 { 20-Byte Prgm }
01▸LBL "Fib"
02 2
03 -1
04 +
05▸LBL 00
06 RCL+ ST L
07 STOP
08 GTO 00
09 ENDXEQ “Fib” → 0
R/S → 1
R/S → 1
R/S → 2
R/S → 3
R/S → 5
R/S → 8
…
RE: HP 25 Fibonacci sequence in one program step - Gerson W. Barbosa - 10-17-2021 02:17 PM
(10-16-2021 02:55 PM)Gerson W. Barbosa Wrote: (Not sure whether I’ve succeeded or not – another one I tried has exactly the same number of steps and bytes)
Surely I hadn’t. It is possible to do it in 6 steps and 17 steps.
Thanks Mike (Stgt) for his comment
“Many think a program must start
with a global label, but no, it needs not” and examples which easily lead to
Code:
00 { 17-Byte Prgm }
01 GTO 00
02▸LBL "Fib"
03 -1
04 ABS
05▸LBL 00
06 RCL+ ST L
07 ENDEdited for a minor grammar issue