+- 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: RPN Mini-Challemge: Splice & Split register blocks (/thread-14194.html)
RPN Mini-Challemge: Splice & Split register blocks - Ángel Martin - 12-20-2019 02:52 PM
No doubt there must be more interesting ways to spend a couple of hours, but if you'd fancy this subject here's the mini-challenge description:
#1:- Splice: Given two equal-sized blocks of data registers, {R01-Rn} and {Rn+1, R2n} your mission is to write a data splicing routine that has one register from each block stored consecutively, i.e. {R1, Rn+1, R2, Rn+2,... Rn, R2n}.
#2:- Split.- Separate the interlaced 2n-block of registers into two n-Regs blocks, so the routine does the inverse task.
In both cases the resulting block occupies the same memory area, i.e. from R01 to R2n.
- Platform: HP-41CX or lesser.
- Parameter entry for both routines: block size "n" in register X.
- Stack is obviously available for pointers and scratch.
- R00 is free to use, all others are for data.
a) Expert Level: it's ok to use an auxiliary data registers area for scratch.
b) Master Level: do it in-place using swapping actions.
Rumor has it that the master level fits in the page' margins of this post... ;-)
BTW solutions in RPL and BASIC are kinda trivial, but I predict this is going to make us all hate RPN for a while...
Disclaimer: I haven't done it yet, so we're all in equal condition here (kinda how I like it).
Cheers,
ÁM
RE: RPN Mini-Challemge: Splice & Split register blocks - Werner - 12-20-2019 04:41 PM
Quick hack, and probably not what you had in mind:
Code:
>LBL"SPLICE"
1
X<>Y
X=Y?
RTN
.1
%
2
+
>LBL 02
RCL Y
RCL Y
>LBL 03
ISG T
X<>Y
X<> IND T
X<> IND Z
X<> IND T
ISG Z
GTO 03
ISG X
GTO 02
ENDCheers, Werner
RE: RPN Mini-Challemge: Splice & Split register blocks - J-F Garnier - 12-21-2019 09:14 AM
Nice in-place solution, Werner, and a great RPN programming lesson with the % trick and optimal stack usage.
Each element is moved several times, so for large data set a more efficient algorithm may be used instead, like described in this HP Journal, p.34 right side about the HP-15C.
Maybe, Angel, was it the application you had in mind?
J-F
RE: RPN Mini-Challemge: Splice & Split register blocks - Werner - 12-21-2019 10:02 AM
That's what I really wanted to do as well, but it needs a way of tagging which elements have been moved and which haven't. The 15C uses the exponent sign for that (as it does to store permutations in LU decomp), but I see no way of achieving that, so far.
Cheers, Werner
RE: RPN Mini-Challemge: Splice & Split register blocks - Paul Dale - 12-21-2019 11:42 PM
The 15C manual does this as an example of a matrix transpose. Transpose can be done with a minimal amount of extra storage.
For this specific case (2 by n), there are likely optimisations available.
Pauli
RE: RPN Mini-Challemge: Splice & Split register blocks - Ángel Martin - 12-22-2019 05:55 AM
(12-20-2019 04:41 PM)Werner Wrote: Quick hack, and probably not what you had in mind:
Cheers, Werner
Chapeau , Werner, very nice indeed - it has all the ingredients I had in mind. It's hard to keep all those indirect sub-indices in mind while tracing the program flow.
Thank you for the references J-F and Pauli, once again it pays off going to the sources. I had totally forgotten how good those HP Journal articles were - it's delightful to re-read them and I learn something each time I revisit them.
Thank you for chiming in and sharing your findings.
Best,
ÁM
RE: RPN Mini-Challemge: Splice & Split register blocks - Werner - 12-29-2019 06:04 PM
Well, I wasn't done ;-)
I can do it in ~N*LOG(N) steps when N is a power of 2.
When it isn't, it will use up the return stack, as follows:
(I took the liberty of calling it 'LACE', because it is slightly different from SPLICE: SPLICE will leave the first and last elements in place, while LACE interleaves 1 2 3 4 .. 2N as N+1 1 N+2 2 .. so SPLICE(N) is equivalent to LACE(2,N-1) )
(BTW is there any way to get these tabs aligned? It shows up nicely in Notepad)
(Edited in the meantime, thanks Ian)
Code:
X Y Z T
>LBL"LACE" N A
>LBL 11
1
X<Y?
GTO 00
Rv 1 A 1
X<>Y
ST+ Y A A+1 1
R^ 1 A A+1
X<> IND Y
X<> IND Z
X<> IND Y
RTN
>LBL 00
Rv N A
ST+ Y N A+N
2
/
RCL Y
RCL Y N/2 A+N N/2 A+N
-
INT A+[N/2] N/2 A+N A+N
X<>Y
R^
DSE X
,1
% ,A+N-1 A+N-1 N A+[N/2]
R^
+ ISG-1 ISG-2 N N
R^ N ISG-1 ISG-2 N
>LBL 02
ISG Z
X<>Y
X<> IND Y
X<> IND Z
X<> IND Y
ISG Y
GTO 02
N A+N,A+N-1
X<>Y
INT
X<>Y
INT [N/2] A+N
LASTX
X#Y?
GTO 00
Rv
XEQ 11 N/2 A+N
ST- Y
ST- Y
XEQ 11 N/2 A
ST+ X
RTN
>LBL 00
Rv
ISG Y
X<>Y
XEQ 11 [N/2] A+N+1
ST- Y
ST- Y
DSE Y
DSE Y
XEQ 11
ST+ X
ISG X
ENDOf course, in Free42, the return stack length is not such a problem ;-)
Algorithm for SPLICE(9) == LACE(2,8):
LACE(2,8) ==
SWAP(6..9,10..13);
LACE(2,4);
LACE(10,4);
[code] 1 1
2 10 2 6
3 11 3 7
4 12 4 8
5 13 -> 5 9
6 14 10 14
7 15 11 15
8 16 12 16
9 17 13 17
18 18[\code]
for SPLICE(8) == LACE(2,7):
LACE(2,7) ==
SWAP(5..8,9..12);
LACE(2,3);
LACE(10,3);
[code] 1 1
2 9 2 5
3 10 3 6
4 11 4 7
5 12 -> 9 8
6 13 10 13
7 14 11 14
8 15 12 15
16 16[\code]
or, in general:
LACE(A,N) ==
SWAP(A+[N/2]..A+N-1,A+N..A+N+[N/2])
IF N EVEN
THEN DO LACE(A,N/2); LACE(A+N,N/2); END;
ELSE DO LACE(A,[N/2]); LACE(A+N+1,[N/2]); END;
Cheers, Werner
RE: RPN Mini-Challemge: Splice & Split register blocks - ijabbott - 12-29-2019 06:20 PM
(12-29-2019 06:04 PM)Werner Wrote: (BTW is there any way to get these tabs aligned? It shows up nicely in Notepad)
Not if you use TAB characters. The forum software displays every TAB character in a code section as 4 characters wide, no matter which column it starts in. The only way to avoid that is to convert TAB characters to the appropriate number of spaces before pasting. Some text editors have commands to convert tabs to spaces.