RPN Mini-Challemge: Splice & Split register blocks
12-20-2019, 02:52 PM (This post was last modified: 12-20-2019 03:04 PM by Ángel Martin.)
Post: #1
 Ángel Martin Senior Member Posts: 1,341 Joined: Dec 2013
RPN Mini-Challemge: Splice & Split register blocks
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
12-20-2019, 04:41 PM (This post was last modified: 12-20-2019 05:23 PM by Werner.)
Post: #2
 Werner Senior Member Posts: 696 Joined: Dec 2013
RE: RPN Mini-Challemge: Splice & Split register blocks
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
12-21-2019, 09:14 AM
Post: #3
 J-F Garnier Senior Member Posts: 633 Joined: Dec 2013
RE: RPN Mini-Challemge: Splice & Split register blocks
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
12-21-2019, 10:02 AM
Post: #4
 Werner Senior Member Posts: 696 Joined: Dec 2013
RE: RPN Mini-Challemge: Splice & Split register blocks
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
12-21-2019, 11:42 PM
Post: #5
 Paul Dale Senior Member Posts: 1,752 Joined: Dec 2013
RE: RPN Mini-Challemge: Splice & Split register blocks
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
12-22-2019, 05:55 AM (This post was last modified: 12-22-2019 05:55 AM by Ángel Martin.)
Post: #6
 Ángel Martin Senior Member Posts: 1,341 Joined: Dec 2013
RE: RPN Mini-Challemge: Splice & Split register blocks
(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
12-29-2019, 06:04 PM (This post was last modified: 12-30-2019 11:51 AM by Werner.)
Post: #7
 Werner Senior Member Posts: 696 Joined: Dec 2013
RE: RPN Mini-Challemge: Splice & Split register blocks
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
12-29-2019, 06:20 PM (This post was last modified: 12-29-2019 06:22 PM by ijabbott.)
Post: #8
 ijabbott Senior Member Posts: 1,129 Joined: Jul 2015
RE: RPN Mini-Challemge: Splice & Split register blocks
(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.

— Ian Abbott
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)