Post Reply 
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
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
Find all posts by this user
Quote this message in a reply
12-20-2019, 04:41 PM (This post was last modified: 12-20-2019 05:23 PM by Werner.)
Post: #2
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

41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE
Find all posts by this user
Quote this message in a reply
12-21-2019, 09:14 AM
Post: #3
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
Visit this user's website Find all posts by this user
Quote this message in a reply
12-21-2019, 10:02 AM
Post: #4
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

41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE
Find all posts by this user
Quote this message in a reply
12-21-2019, 11:42 PM
Post: #5
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
Find all posts by this user
Quote this message in a reply
12-22-2019, 05:55 AM (This post was last modified: 12-22-2019 05:55 AM by Ángel Martin.)
Post: #6
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
Find all posts by this user
Quote this message in a reply
12-29-2019, 06:04 PM (This post was last modified: 12-30-2019 11:51 AM by Werner.)
Post: #7
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

41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE
Find all posts by this user
Quote this message in a reply
12-29-2019, 06:20 PM (This post was last modified: 12-29-2019 06:22 PM by ijabbott.)
Post: #8
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
Find all posts by this user
Quote this message in a reply
Post Reply 




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