RPN Mini-Challemge: Splice & Split register blocks

[Ángel Martin]

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.

1. Platform: HP-41CX or lesser.
2. Parameter entry for both routines: block size "n" in register X.
3. Stack is obviously available for pointers and scratch.
4. 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

[Werner]

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
 END

Cheers, Werner

[J-F Garnier]

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

[Werner]

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

[Paul Dale]

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

[Ángel Martin]

(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

[Werner]

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
 END

Of 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

[ijabbott]

(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.