Post Reply 
RPN Mini-Challemge: Splice & Split register blocks
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
Post Reply 


Messages In This Thread
RE: RPN Mini-Challemge: Splice & Split register blocks - Werner - 12-29-2019 06:04 PM



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