▼
Posts: 1,477
Threads: 71
Joined: Jan 2005
Here's a little RPN stack manipulation problem/challenge:
What's the least number of instruction steps needed to sort the stack? Specifically, given random values in X, Y, Z and T arrange them in order with the largest value in X, next largest in Y, etc..
I can't find a solution better than the obvious one (you can figure that out for yourself) that takes 20 steps on a 12C -- a couple less on RPN calculators that have a roll-up [edited] function and/or subroutines. There must be some clever way to do this, but I'm stumped.
Edited: 25 July 2006, 2:20 p.m. after one or more responses were posted
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
I've not tried any of this on a calculator yet so forgive any obvious errors.
If we bubble sort the stack we basically need to do the following sequence lots of times:
x <= y? comparison (x < y? avoids unnecessary swaps)
x <> y swap x & y
Rv roll down
The first pass over the stack (repeating this sequence three times, followed by one Rv) puts the largest value into the t register and maybe juggles the others. The second pass only needs this sequence twice with two Rv to bring the stack back to its original position. The third and final pass only needs the sequence once and either three Rv or one R^. So 24 steps on a 12c and 22 steps on a machine with roll up.
Can we do better? Of course:
STO I
Rv
1
2
x <> I
LBL 0
x <= y?
SWAP
Rv
DSE I
GTO 0
A total of 11 steps. This skips the extra Rv's from above and replaces them with the three instruction test, swap and roll down sequence which is harmless. Do this sequence a dozen times and the stack will be sorted.
- Pauli
▼
Posts: 1,477
Threads: 71
Joined: Jan 2005
Bubble sort is the obvious method but your code doesn't work because it treats the stack as a circular list. Taking care of this problem is what complicates the coding in a loop and the straight line code is what takes 20 steps (not 24) on a 12C.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
I figured out it had a problem soon after posting. I really should have tried it out first :-(
I need to execute the trio of compares then a Rv and do that lot thrice. On a 32sii I get this program:
LBL A
X <> K
STO I
X <> K
LBL B
X <> K
STO J
X <> K
LBL C
x < y?
x <> y
Rv
DSE J
GTO C
Rv
DSE I
GTO B
Assuming that register K contains the value 3.
17 steps in all. Plus you might be able to ditch the two "x <> K" when setting up I.
- Pauli
▼
Posts: 1,477
Threads: 71
Joined: Jan 2005
Pauli, that looks a lot better! I found a few different 17 step solutions I found when using something better than a 12C. But all of them are just variations of bubble sort. I wonder if there's some totally different way to do this, maybe using some arithmetic tricks?
The 6 comparisons needed by bubble sort is the theoretical minimum for a 4 element sort. Given that all the RPN calculators (I think) only allow for comparing X and Y there's a good amount of stack manipulation is going to be needed. So probably the only way to do better than 17-20 steps is to employ some trick or make use of some not-at-all-obvious calculator function.
Posts: 3,229
Threads: 42
Joined: Jul 2006
Better is:
3
STO I
...
LBL 0
x < y?
x <> y
Rv
x < y?
x <> y
Rv
x < y?
x <> y
Rv
Rv
DSE I
GTO 0
This unrolls the inner loop at no cost in space and a good speed improvement.
15 steps so long as I can initialise the index register ahead of time.
- Pauli
Edited: 25 July 2006, 6:59 p.m.
▼
Posts: 1,477
Threads: 71
Joined: Jan 2005
Assuming a preloaded index counter is cheating! If you assume that X > Y then you can save 2 steps too :)
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
Oh well...
I figured loading the 3 into I before stacking the satck wasn't totally unreasonable. At least I did count the two steps for loading it.
If you've got a 3 stashed in another register (say 0) you can do it in three steps
X<>0, STO I, X<>0
If that isn't allowed, I can do it in four steps:
STO I, Rv, 3, x<>I
Another way to do it in 4 steps:
STO I, STO+ I, STO+ I, STO/ I
- Pauli
Posts: 130
Threads: 36
Joined: Jan 1970
Quote:
The first pass over the stack (repeating this sequence three times, followed by one Rv) puts the largest value into the t register and maybe juggles the others. The second pass only needs this sequence twice with two Rv to bring the stack back to its original position. The third and final pass only needs the sequence once and either three Rv or one R^. So 24 steps on a 12c and 22 steps on a machine with roll up.
I don't see that you need a roll up / down command after the third pass through. I got 20 steps (excluding the label) for a simple bubble routine using only roll downs.
best regards, Hal
Posts: 1,755
Threads: 112
Joined: Jan 2005
Hi, Katie:
Katie posted:
"I can't find a solution better than the obvious one (you can figure that out for yourself) that takes 20 steps on a 12C -- a couple less on RPN calculators that have a
roll-down function and/or subroutines."
You mean roll-up, right ? Because all my three HP-12C's do have a roll-down function right on the keyboard. :-)
Also, I'm pretty sure this particular stack sorting routine you're interested in was probably covered in some old PPC Journal issues, or perhaps in the excellent "Calculator Tips & Routines" by John Dearing.
It would be probably wise to look for it in this last reference first, before wasting too much time allegedly trying to reinvent the wheel.
Best regards from V.
▼
Posts: 1,477
Threads: 71
Joined: Jan 2005
Right, I meant roll-up. Thanks for catching that!
Posts: 1,477
Threads: 71
Joined: Jan 2005
I just found John Dearing's "Stack Sort" for the 41C. It's more than 30 steps! This wheel could use some reinventing. :)
▼
Posts: 801
Threads: 36
Joined: Nov 2005
I am not much of a programmer, nor am I super-adept in mathematics. I once asked someone, I think in this very forum, for a method to sort roughly thirty values in a HP-33S, or any other four-level stack RPN machine.
Needless to say, I forgot it, but I do recall it required many steps, not seventeen or twenty-five.
If I may ask, how would you sort a larger number of values than stack levels available... COMPLICATED by the fact that the 33S has twenty-six (and a half?) data registers and older beauties, like the 34C, have a few less?
I'm sure I can kluge up some way of doing it, but taking a year and three quarters and almost filling its programming memory is not a good way to do it.
▼
Posts: 1,477
Threads: 71
Joined: Jan 2005
You can program a simple bubble sort on any HP calculator that allows indirect register addressing. Even the lowly 12C can do it, and in not very many steps:
12C bubble sort
Bubble sorting 26 data elements isn't that time consuming on a 33S (30 elements would be hard on this calculator because the 27'th register is the index register needed for indirect addressing), but running time is proportional to the square of the number of data elements so you probably would want to use a better sorting algorithm on a calculator capable of addressing more registers. There are a vast number of sorting algorithms the best of which is
Quicksort in most cases.
Posts: 1,253
Threads: 117
Joined: Nov 2005
I know it's cheating but... it takes just *one* step on the 41C, using my SandMath ROM (or the SandBox):
STSORT
Best,
ÁM
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
It is pretty easy on a HP49g+ too:
<< DEPTH ->LIST SORT LIST-> DROP >>
- Pauli
|