![]() |
RPN programming exercise - Fibonacci numbers - Printable Version +- HP Forums (https://archived.hpcalc.org/museumforum) +-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html) +--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html) +--- Thread: RPN programming exercise - Fibonacci numbers (/thread-208623.html) |
RPN programming exercise - Fibonacci numbers - Gerson W. Barbosa - 01-07-2012 Write a short program on your favorite RPN calculator to display the Fibonacci sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... No manual initialization allowed. On the HP-15C LE you might want to use R/S instead of PSE. Currently I have a couple of 7-step HP-12C programs and one 6-step WP 34S program, but this can always be improved (except by creating a new firmware just for this task - FIB can of course be used if needed :-). Happy programming!
Re: RPN programming exercise - Fibonacci numbers - Paul Dale - 01-07-2012 Two completely untest 34S solutions both six steps.
01 iC 0 Clx The left version is more suitable to other RPN calculators of course. Both are untested and likely broken but the ideas are probably okay.
Re: RPN programming exercise - Fibonacci numbers - Gerson W. Barbosa - 01-07-2012 It works. It's similar to the one I came up with when using FIB. I forgot to mention the step count should include LBL when applicable, sorry!
001 LBL 99 Gerson.
Edited: 7 Jan 2012, 9:20 p.m.
Re: RPN programming exercise - Fibonacci numbers - Allen - 01-07-2012 For 42S:
00 { 10-Byte Prgm } Edited: 7 Jan 2012, 9:46 p.m.
Re: RPN programming exercise - Fibonacci numbers - Gerson W. Barbosa - 01-07-2012 10 bytes! One step shorter here... but 1 byte longer.
Re: RPN programming exercise - Fibonacci numbers - Gerson W. Barbosa - 01-08-2012 This is supposed to be just an exercise, not a challenge. Feel free to submit your solutions. Different approaches are always interesting, regardless of code size or register usage.
Here are my solutions: WP-34S
Re: RPN programming exercise - Fibonacci numbers - Fouad M. Kaadou - 01-08-2012 Here are a few for the HP41C:
01 LBL 00
16 Bytes
01 LBl 00
01 LBL 00
14 Bytes
I used local labels and synthetic instructions to make the programs shorter. . = 0 E = 1 Cheers,
Fouad
Re: RPN programming exercise - Fibonacci numbers - Gerson W. Barbosa - 01-08-2012 Thanks for your participation! I'd completely forgotten about this old thread. Not exactly the same problem, but some interesting ideas there, like Kioshi Ashima's as implemented on the WP 34S:
001 LBL 11Regards, Gerson.
Edited: 8 Jan 2012, 3:21 p.m.
RPL programming exercise - One Fibonacci number - Oliver Unter Ecker - 01-08-2012 On an RPL machine, these two instructions DUP2 +will compute the *next* Fibonacci number, given the two previous ones on the stack.
So, a full program becomes \<< 0 1 (Though, on an RPL machine you'd want to collect the resulting numbers in a list, of course, and not just dump them on the stack.)
With this being too easy for an RPL machine, here's the advanced RPL programming exercise:
(You're welcome to try this on your RPN machine, too, and I will be multo impressed if you can solve this...)
Re: RPL programming exercise - One Fibonacci number - Gerson W. Barbosa - 01-08-2012 Quote:
Just a guess: 6875.
Re: RPL programming exercise - One Fibonacci number - Oliver Unter Ecker - 01-08-2012 lol. For a guess, that's pretty good! Did a calculator help you with your guess?
Re: RPL programming exercise - One Fibonacci number - Gerson W. Barbosa - 01-08-2012 Yes. I used your program to check it up to F(10^5) on my HP 50g: %%HP: T(3)A(R)F(,); These appear to follow a pattern. P.S.: The latter has 20,899 digits (~10^5*log10(phi)). It took about one hour or so on the real 50g (I haven't timed it).
Edited: 8 Jan 2012, 7:06 p.m.
Re: RPL programming exercise - One Fibonacci number - Oliver Unter Ecker - 01-08-2012 Brilliant, Gerson! Ok. So, for the tenacious ones: how about the last 14 decimal digits of F(10^14)? EDIT: you could have used the MOD instruction to keep the number of digits down. That would compute F(10^5) *a lot* faster. But, still, 10^14 is out of reach with this approach.
Edited: 8 Jan 2012, 7:21 p.m.
Re: RPL programming exercise - One Fibonacci number - Gerson W. Barbosa - 01-08-2012 The last four digits of F(10^4) coincide with the last four digits of F(10000) because 10^14 mod 15000 equals 10000.So it suffices to compute F(10000), easily done on the real 50g. See Pisano periods here. There is a calculator for the cycle lengths (scroll down halfway through the page). For modulus 10000 the result is
Fibs mod 10000: cycle length is 15000 It will not compute the cycle length for modulus 10^14, but it can be extrapolated from lower power of 10. The length appears to be 1.5*10^14, which means this approach won't be of help in this case. Cheers, Gerson. P.S.: The fourth and higher powers of 10 modulus 15000 equals 10000 - so my guess was indeed right :-)
Edited: 8 Jan 2012, 10:07 p.m.
Re: RPL programming exercise - One Fibonacci number - Thomas Klemm - 01-09-2012 My approach was slightly different: It's clear that the last digit of Fn has to repeat since there are only 10x10 = 100 possibilities for the two previous values. I used the following program with initial values ST X: 1 and ST Y: 0:
X<>Y It turns out the length of the period is 60. So I added a loop to find the period for the last two digits:
00 { 27-Byte Prgm }
This gave me the following sequence: y: 20 40 60 80 0 Thus the period is: 60 x 5 = 300
Next step was to change line 03 to 300 and line 08 to 1E3 to find another sequence of 5: y: 600 200 800 400 0
After changing line 03 to 1500 and line 08 to 1E4 I got a sequence of 10: y: 8000 6000 4000 2000 0 8000 6000 4000 2000 0
Thus I ended up with a period of 60 x 5 x 5 x 10 = 15,000.
y: 30626
Cheers
Edited: 9 Jan 2012, 3:07 a.m.
Re: RPL programming exercise - One Fibonacci number - Oliver Unter Ecker - 01-09-2012 Wow, Thomas, very nice! I *am* impressed.
Re: RPL programming exercise - One Fibonacci number - Oliver Unter Ecker - 01-09-2012 Yes, your guess was right. I volunteer your result is even right to 5 digits. Re: RPL programming exercise - One Fibonacci number - Oliver Unter Ecker - 01-09-2012 If you look up the Fibonacci page on wikipedia, you'll see various methods for direct computation of F(n). One is matrix exponentiation: F(n) = [[0 1][1 1]] ^ n
This program for the 50g will tell you what F(100) mod 10^14 is, for example: \<< 1.E14 R\->I MODSTOIt takes about 1s on Emu48, so I figure about 10s on a 50g. Now, if you change 1.E2 to 1.E3 it will produce a negative result. No idea why. If you try 1.E14 it will tell you: "POWMOD Error: Integer too large" I conclude that on the 50g POWMOD first does the POW, then the MOD, which, uhm, renders this instruction pretty much useless for matrices. (You want to MOD while you're POW'ing, or else you don't avoid the giant intermediate numbers.) Well, it works on ND1, and the result is: 88299560546875 Modular matrix exponentiation can be made very fast with the binary method, where you're, essentially, moving in powers of 2 with every iteration. There're only ~50 (~log2(10^14)) matrix multiplications necessary to arrive at 10^14. This could also be made to work on the 50g with ~10 lines of code to write a proper version of POWMOD. I'm pretty sure this could be made to run in under a minute, for F(10^14). There's a Project Euler problem (#304) where finding this number (almost this number, there's a different modulus) is the first part of the simple but brutal task of summing up the Fibonacci numbers for each of 100,000 primes following 10^14.
On the 50g, 10 of those primes \<< 1.E14 R\->I 1 10 START NEXTPRIME NEXT \>>take about a minute to find (5s in Emulator; not sure how long exactly on the 50g), so 100,000 is a bit... daunting. (I'm not sure what's done on the 50g, but this speed suggests to me that they're not using Miller-Rabin for the probabilistic primality check that kicks in for large numbers, used by NEXTPRIME.) Once you have the F(NEXTPRIME(10^14)) and F(PREVPRIME(10^14)), you can use normal Fibonacci iteration (with MOD) to compute the spans between primes and eliminate the need to use matrix exponentiation to find each F(n). With an average of 33 numbers from prime to prime in this range, you're looking at having to compute 3.3 million Fibonacci numbers, though.
If you're interested, here's RPL+ code to do all that: \<< 1234567891011 =m
Note that the matrix exponentiation method actually computes F(n-1), F(n), F(n+1) at once. So, to continue with Fib iteration you can pick two of them from the result matrix, and you're ready to go.
Re: RPL programming exercise - One Fibonacci number - Thomas Klemm - 01-09-2012 Quote: We can combine the Fibonacci- and the Lucas-Sequence to find a fast algorithm to calculate both sequences using the following identities:
The idea is similar to binary exponentiation (a.k.a square-and-multiply algorithm). Here's a Python-program:
#!/usr/bin/python And that's the output:
N B K F L My guess is that this algorithm should be fast on a HP-50g as well. Due to the lack of arbitrary precision the HP-42S doesn't qualify for this.
Kind regards Re: RPN programming exercise - Fibonacci numbers - Paul Dale - 01-09-2012 How about another:
01 iC 0 Six steps, seven with an initial label.
Re: RPN programming exercise - Fibonacci numbers - Gerson W. Barbosa - 01-09-2012 Nice use of CENTER as DUP2 in RPL!
%%HP: T(3)A(R)F(,);
Gerson.
Re: RPN programming exercise - Fibonacci numbers - Paul Dale - 01-09-2012 And another:
01 iC 0 Same length though.
Re: RPN programming exercise - Fibonacci numbers - Gerson W. Barbosa - 01-09-2012 There's more than a way to skin a cat. On the HP-15C: 001- f LBL AGerson.
Edited: 9 Jan 2012, 11:20 p.m.
Re: RPL programming exercise - One Fibonacci number - Oliver Unter Ecker - 01-10-2012 Nice work, again, Thomas.
Quote: That's what I used to think too, until, almost exactly one year ago, an intrepid bunch (some active posters here) showed the way: Making Fib bits visible (on Silicium.org) (I think this is my all-time favorite calculator-related discussion. It starts slow but quickly shows real ingenuity. I still can't get over those HP-28C print-outs.) Now, I'd be willing to bet that F(10^14) mod 10^14 can even be solved on a 15C (LE).
Edited: 10 Jan 2012, 9:08 a.m.
Re: RPL programming exercise - One Fibonacci number - Thomas Klemm - 01-11-2012 Thanks for link: it's an interesting post! I didn't mean to say it's impossible to do it using the HP-42S. Or we could use Peter's MCODE Multi-Precision Library for HP-41. I might give it a try but this is definitely not my first choice.
Thanks for the challenge as well! Re: RPN programming exercise - Fibonacci numbers - Paul Dale - 01-11-2012 I'm very tempted to add some more complex constants to the 34s "[cmplx] 1" e.g.
Re: RPN programming exercise - Fibonacci numbers - Gerson W. Barbosa - 01-11-2012 That would be useful, not just for this task, so go ahead if there's room enough. By the way, is it possible to enter i (1 0) in one step only? Thanks!
Gerson.
Re: RPN programming exercise - Fibonacci numbers - Paul Dale - 01-11-2012 I can't think of a way to get i on the stack in one step. Can do it in two though. We do have a complex version of the constants catalogue which puts zero in Y already. This doesn't include any small integers though. "CPX h-shift CONST"
- Pauli
Re: RPN programming exercise - Fibonacci numbers - Gerson W. Barbosa - 01-11-2012 Quote: Yes, I had checked that but then I realized it wouldn't make sense to include small integers there. Changing the behavior of the CPX key before numeric keys and [.] might be a option, for instance CPX 123 would put 0 in Y and 123 in X. [CPX] [R/S] might be a non-intuitive shortcut for entering i. I don't know the impact of these changes in the executable size though. Also, this may not be useful enough to be worth the trouble. Gerson.
Re: RPN programming exercise - Fibonacci numbers - Paul Dale - 01-11-2012 A function that does pretty much nothing requires of the order of 100 bytes. This is function table overheads, catalogue overheads and the actual function prelude/epilogue that seems almost unavoidable. Making small changes to the keyboard handler isn't so bad -- much of this is table based now so adding a command to an unused location is usually cheap. Adding a complex prefix to digit entry is quite a different change. No idea how large this would be.
Re: RPN programming exercise - Fibonacci numbers - Marcus von Cube, Germany - 01-11-2012
XLBL"i"
This should do the trick with minimum overhead. We have to add a catalogue entry and a command table entry but that's not too expensive.
Re: RPN programming exercise - Fibonacci numbers - Paul Dale - 01-11-2012 Quote: Not quite -- the stack dynamics would be incorrect :-(
XLBL"i" will work however. The code is 8 bytes, the command table is 10 - 12 bytes (I forget which) and the catalogue entry is 10 bits but can't live in the complex constants catalogue which is compiled automatically -- the complex functions catalogue seems like an okay place to put it. Pauli
Edited: 11 Jan 2012, 5:21 p.m.
Re: RPN programming exercise - Fibonacci numbers - Paul Dale - 01-12-2012 We've got a shorter solution on the 34s now:
01 [cmplx]i
Re: RPN programming exercise - Fibonacci numbers - Gerson W. Barbosa - 01-12-2012 That's what [cmplx]i was for! If the steps 02 and 03 are swapped the sequence will begin with F(0). I'd searched for an i constant in the HP-42S catalog but there was none. I think this first appeared in the HP-28C. If now WP 34S has it, then it was worth posting this simple RPN exercise :-) BTW, how [cmplx]i is entered?
Gerson.
Re: RPN programming exercise - Fibonacci numbers - Marcus von Cube, Germany - 01-12-2012 Quote:
It's in the complex catalogue (CPX 3) but I just mapped it to CPX dot as well. I'm sure Walter will find a better place on the keyboard.
Re: RPN programming exercise - Fibonacci numbers - Marcus von Cube, Germany - 01-12-2012 Remember that WP 34S instructions are generally 16 bits long. This allows to cramp so much functionality into a single instruction but costs more bytes than other designs. We are down to 10 bytes here, still pretty decent...
Re: RPN programming exercise - Fibonacci numbers - Paul Dale - 01-12-2012 We couldn't put it in the complex constants catalogue since that is automatically produced alongside the real version. Still, the complex catalogue is a decent place and Walter will likely find somewhere decent on the keyboard to locate it. "CPX 1" might be okay which would allow "CPX 0" as well :-)
Re: RPN programming exercise - Fibonacci numbers - Paul Dale - 01-12-2012 We have way more than 256 different instructions kind of required this and by doing so the argument can be squeezed into the instruction as well. We currently have 571 instructions and that is not counting integer, real & complex as different functions (there are 660 if you do that). We've almost got as many different functions as the 15C has total op-codes. - Pauli
Edited: 12 Jan 2012, 5:38 p.m.
Re: RPN programming exercise - Fibonacci numbers - Morten Nygaard Åsnes - 01-13-2012 HP 35s
F001 LBL F Re: RPN programming exercise - Fibonacci numbers - Gerson W. Barbosa - 01-13-2012 Great! The first 6-step program for an unmodified HP calculator! Since it does show F(0) and F(1) before looping (thanks to the 2-line display) that's okay. Also, this allows us to match Allen's 10-byte step solution for the HP-42S above:
00 {10-Byte Prgm } Gerson.
Re: RPL programming exercise - One Fibonacci number - Werner - 01-13-2012 The 42S not, no, but Free42 decimal (as on the iPhone) can determine the last 12 digits this way.
Cheers, Werner
Re: RPN programming exercise - Fibonacci numbers - Paul Dale - 01-13-2012 I rather doubt the 35s solution is less than 10 bytes.
Re: RPN programming exercise - Fibonacci numbers - Gerson W. Barbosa - 01-13-2012 Sorry! I think I didn't make myself clear. I meant showing F(0) and F(1) at the same time like Morten did would allow me to achieve the 10-byte count in the HP-42S. My post was really ambiguous, I realize now.
Gerson.
Re: RPL programming exercise - One Fibonacci number - Thomas Klemm - 01-14-2012 Challenge accepted:
1E12
gives: y: 245361328127
Cheers
00 { 90-Byte Prgm } Edited: 14 Jan 2012, 3:11 a.m.
|