RPL mini-challenge: Create an anti-Identity Matrix

[DavidM]

(05-13-2018 06:00 AM)Joe Horn Wrote:  How about this:
<< IDN << NOT >> MAP >>

Nice, Joe! I'd be surprised if a more concise version exists (this one is 33 bytes). This is actually a great example of how size and speed don't always go hand-in-hand, though. In this case, IDN is quite fast, but applying NOT with MAP slows it down considerably. But I definitely think this qualifies as elegant.

(05-13-2018 06:52 AM)Gerald H Wrote:  Slightly faster than my 1st effort:

Code:

« DUP 1. →LIST 1 CON 1. PICK3
  FOR i DUP i 0 PUT UNROT
  NEXT DROP ROW→
»

Nice refinements, Gerald! My 50g clocked in at 1.21s for this one, which I believe is the fastest I've seen yet for an output of exact integers.

(05-13-2018 10:27 AM)pier4r Wrote:  ...Fixed values, but not difficult to modify with variables.

Code:


@ Idea: create N-1 rows of the form 0 1 1 .. 1 with as many 1 as N
@ add an ending 0
@ compact it in a matrix
@0.18 seconds
\<< 1. 29.
  START 
    0. 1. 30. NDUPN DROP
  NEXT 
  0. 
  30. DUP 2. \->LIST \->ARRY
\>>

You're definitely getting great performance here, Pier! I look forward to seeing how this does once you've altered it to accept the dimension as an input variable.

[DavidM]

(05-13-2018 09:51 AM)pier4r Wrote:  Question: in user RPL how do I replace a charachter in a specific position? Like I have "12345" I want to replace 4 with 8 to get "12385". I was thinking PUT would do the job, but the AUR says no.

PUT doesn't work with strings, but REPL does:

"12345" 4 "8" REPL

yields

"12385"

If you simply want all instances of a given character replaced, use SREPL.

[Didier Lachieze]

(05-13-2018 02:44 PM)DavidM Wrote:  

(05-13-2018 06:00 AM)Joe Horn Wrote:  How about this:
<< IDN << NOT >> MAP >>

Nice, Joe! I'd be surprised if a more concise version exists (this one is 33 bytes). This is actually a great example of how size and speed don't always go hand-in-hand, though.

Same size but slower (19s):
<< DUP << ≠ >> LCXM >>

[pier4r]

(05-13-2018 03:01 PM)DavidM Wrote:  PUT doesn't work with strings, but REPL does:

"12345" 4 "8" REPL

yields

"12385"

If you simply want all instances of a given character replaced, use SREPL.

Thanks. I knew SREPL but I missed REPL. When will I finish to have an idea of all the commands (and inputs) of the RPL base library? (no additional libraries!) It is enormous. I guess counting a function for a type of input, so different types (and combinations of types) of inputs counts as different functions, the RPL base library is easily over 2000 functions. Many of which should still be investigated. For example how speedy they are. Impressive what HP has done (considering also the community support). I wonder if the prime has such extensive library as well. I did not dive deep there. Surely the casio 9860G is much more simpler with the casio basic. On the 9860G maybe other inteepreters or the SDK enable the user to close the gap with the 50g.

Already in this thread I learned more about \->ARRY and subtleties.

Anyway, the program modified to use variables. I did not test it extensively, but for the test done it works. Reals in input. Speed with input 30: 0.20 seconds.

Code:


  \<< 
    @ Idea: create N-1 rows of the form 0 1 1 .. 1 with as many 1 as N
    @ add an ending 0
    @ compact it in a matrix
    
    \->
    mDim
    
    \<<
      1. mDim 1 -
      START 
        0. 1. mDim NDUPN DROP
      NEXT 
      0. 
      
      mDim mDim 2. \->LIST \->ARRY
    \>>
  \>>

Question: the code above, I believe, can get a further speed up if one could duplicate many objects on the stack at once. I do not know any command for this. Say I have 5 objects on the stack and I want to duplicate them, without using an explicit loop (surely the command internally will have a loop, like NDUPN). Is it possible?

[Claudio L.]

(05-13-2018 02:52 AM)DavidM Wrote:  Claudio, I've tested your 2nd program on my 50g with much better results:

With exact integers (input, constants, and output): 1.62s
With approximate numbers (input, constants, and output): 0.33s

Now we are talking speed, I was thinking that 3 seconds to shuffle numbers in the stack was a bit much, but I had no reason to doubt his results.

(05-13-2018 02:52 AM)DavidM Wrote:  I did have to make one small change, though: dropping the tick marks around K in the FOR loop declaration. That's probably a subtle difference between New- and Old-RPL.

Ahhh, newRPL doesn't require the quotes (you can type it either way), but it does add them when decompiling (just to show it's the name of the variable), so they came out when I copy/pasted. Good that you caught that.

[Joe Horn]

(05-13-2018 02:44 PM)DavidM Wrote:  

(05-13-2018 06:00 AM)Joe Horn Wrote:  How about this:
<< IDN << NOT >> MAP >>

Nice, Joe! I'd be surprised if a more concise version exists (this one is 33 bytes). This is actually a great example of how size and speed don't always go hand-in-hand, though. In this case, IDN is quite fast, but applying NOT with MAP slows it down considerably.

<< IDN ::NOT MAP >>

is even shorter (24 bytes!) but only a tad faster (30. [real] takes 8.2 seconds, and 30 [integer] takes 12.7 seconds). The null-tag trick for delaying execution goes back to the heyday of comp.sys.hp48, but I forget who first posted it.

Pier4r: I thought of some truly marvelous comments to include with the above program, but its margin is too narrow to contain them.

[3298]

(05-12-2018 09:07 PM)Gerald H Wrote:  Very good, 3298.

Your programme is faster for reals, but if you change the programme to

\<<
0 1 PICK3 NDUPN 1. + \->ARRY
OVER 1. - NDUPN ROW\->
SWAP DUP 2. \->LIST RDM
\>>

slower for integer matrix than my programme.

That can be fixed by using \->LIST in place of \->ARRY and the pair of commands \->LIST AXL in place of ROW\->. That speeds it up from around 1.38_s to around 1.20_s. The same change to the real number version would slow it down, though - by about 0.12_s.

---

I also put some finishing touches like a size parameter into pier4r's program, including slight optimizations (loop counter value range, shuffling the size parameter through the stack intelligently). I avoided UserRPL loops in my own solution because I expected them to be too slow to be of any use (perhaps I'm too used to the speed of SysRPL, and even there I squeeze every last bit of performance out of the loop structure with e.g. runstream shenanigans) - but it seems that handling larger elements (like my matrix rows and eventually the wrongly dimensioned matrix) isn't actually better, whereas in this program the large object doesn't even exist up to the last command. The internal structure of real/complex number matrices (which enforces same-size elements) allows for a very efficient implementation of \->ARRY for that argument type too.

Code:

\<<
  2. OVER START
    0. 1. ROT NDUPN
  NEXT
  0. SWAP
  DUP 2. \->LIST \->ARRY
\>>

Timing: 0.18306_s for the real number version, 0.645375_s for the integer version (drop the period of the 0. and 1. occurences for that). Averages over 20 runs on input 30., as with my previous measurements.

(05-13-2018 07:32 PM)pier4r Wrote:  Say I have 5 objects on the stack and I want to duplicate them, without using an explicit loop (surely the command internally will have a loop, like NDUPN). Is it possible?

Sounds like NDUP, but I don't think it's worth the effort here. You could make 2 matrix rows from 1, but you cannot make N rows from 1 row without putting it into your own loop (like the one that currently houses NDUPN). You'd also have to retain the code for generating a single row so NDUP has something to duplicate.

[Claudio L.]

(05-13-2018 03:19 AM)DavidM Wrote:  

(05-13-2018 02:29 AM)Claudio L. Wrote:  It's not going to be any faster, but perhaps more minimalist:

Code:


«
  IDN AXL NOT AXL 
»

I really like that this works in NewRPL! Unfortunately, it doesn't in standard UserRPL -- NOT isn't recursive into the sublists, so it results in a "Bad Argument Type" error on a standard 50g.

My apologies, in my head the lines between userRPL and newRPL are becoming blurry, I can't recall the slight differences sometimes. All operators map element-by-element on lists on newRPL, but not in userRPL.

PS: On the other hand, the official rules forgot to ban newRPL, so perhaps I should get some timings....

[Claudio L.]

(05-13-2018 10:27 AM)pier4r Wrote:  

Code:


@ Idea: create N-1 rows of the form 0 1 1 .. 1 with as many 1 as N
@ add an ending 0
@ compact it in a matrix
@0.18 seconds
\<< 1. 29.
  START 
    0. 1. 30. NDUPN DROP
  NEXT 
  0. 
  30. DUP 2. \->LIST \->ARRY
\>>

Nice one! No need to ROLLD anything, 0 followed by 30 ones will shift the position of the 0 on every row. Brilliant! (and faster!)

[Claudio L.]

I did some timings with newRPL on real 50g hardware. All times are for 1000 executions with argument of 30:

Code:


«
  IDN NEG DUP 1 CON + 
»

Total time: 12.411 seconds
Bytes: 32

Code:


«
  1 - → 
    N « 0 N FOR 'K' 1 N NDUPN 1 + K - 0 SWAP ROLLD 
    NEXT
    N 1 + DUP 2 →LIST →ARRY 
  »
»

Total time: 2.336 sec
Bytes: 132

Code:


«
  IDN AXL NOT AXL 
»

Total time: 96.751 sec
Bytes: 24

Code:


«
  → 
    N « 1 N FOR 'I' 1 N FOR 'J' I J ≠ 
      NEXT
    NEXT
    N N 2 →LIST →ARRY 
  »
»

Total time: 11.969 sec
Bytes: 112

And finally, I think the fastest implementation is Pier idea with 3298 improvements:

Code:


«
  2 OVER START
    0 1 ROT NDUPN 
  NEXT
  0 SWAP DUP 2 →LIST →ARRY 
»

Total time: 1.946 sec
Bytes: 64

Clearly, the advantage is in the element-by-element approach (EDIT: versus the full matrix ones, and "packed" elements using NDUPN is the winner approach).

EDIT: Added total bytes of each version in newRPL (for completeness only).

[DavidM]

Lots of great work happening here!

@Joe:
Color me surprised re: the small size of your most recent contribution. The null-tagging method is something I must have missed in the comp.sys.hp48 discussions, and it's a neat way to delay execution of a single command. That would also have nice uses for other list processing commands when a single command is needed for processing.

@Didier:
Thanks for the pointer to LCXM. It's yet another RPL command that I've never become acquainted with up until now. While not a speed demon, I can see where it might be really useful in situations where you need to build a 2d matrix whose elements have a defined relationship to their position.

@Pier:
Thanks for your updated (and excellent) submission. You captured the essence of what I was suspecting might be the winning algorithm, and your solution is better than my own attempt at it before I posted the challenge (see below). Great job!

@Claudio:
Interesting notes about the newRPL differences, which are IMHO improvements that will be useful. Thanks also for "taking the time" to time the various approaches with newRPL implementations (pun slightly intended) -- once again we can clearly see what the hardware platform is truly capable of when not being constrained by the emulated Saturn environment. Your efforts are succeeding in creating a great new platform.

@3298:
Bravo! Your adaptation of Pier's approach is a model of efficiency and optimization. You've definitely set the target for any future UserRPL implementations, and I suspect it will be hard to beat. Great job!

@All:
I was hesitant to post my own submission before, but now that others have already done a much better job of implementing what I was attempting to do with it, I don't mind sharing it:

Code:

\<<
  1. DUP2 - UNROT OVER +
  \-> lp dim cnt
  \<<
    0.
    1. dim NDUPN NOT
    WHILE
      'lp' DECR
    REPEAT
      cnt DUPN
    END
    { dim dim } \->ARRY
  \>>
\>>

Although it performed reasonably well (0.30s for approximate results), I knew that the indefinite loop and use of named locals was slowing it down. While these would have been easy to overcome in SysRPL, I was struggling to come up with UserRPL fixes. It was great to see both Pier's and 3298's better solutions which overcame the problems I was having.

[DavidM]

(05-13-2018 07:32 PM)pier4r Wrote:  Question: the code above, I believe, can get a further speed up if one could duplicate many objects on the stack at once. I do not know any command for this. Say I have 5 objects on the stack and I want to duplicate them, without using an explicit loop (surely the command internally will have a loop, like NDUPN). Is it possible?

As 3298 has mentioned, NDUP will duplicate a group of stack objects. But it only makes one copy, so you would have to loop the calls to NDUP to replicate a group of objects multiple times.

The SysRPL program listed below implements a command I've named "NMDUP", which does what I think you're referring to. It requires a 49g/49g+/50g/48gII, and its arguments are as follows:

N+2: object 1
...
3: object N
2: N (the count of discrete objects to replicate)
1: M (the number of duplicates of the above objects after replication)

So to make 4 sets of 1, 2, and 3:

5: 1
4: 2
3: 3
2: 3
1: 4
NMDUP

yields the following result
12: 1
11: 2
10: 3
9: 1
8: 2
7: 3
6: 1
5: 2
4: 3
3: 1
2: 2
1: 3

Code:

::
   ( stack on entry:
     n: anything
     ...
     2: group count [integer]
     1: repeat factor [integer]
   )

   CK2NOLASTWD                         ( stack must contain at least 2 objects )
   CK&DISPATCH1
   BINT17 ( ..., real, real ) ::       ( SL1/2 must contain numbers )
      COERCE2                          ( convert to BINTs )
      OVER #3+                         ( check stack depth )
      DEPTH #> case SETSTACKERR        ( error if stack not deep enough )

      ( special cases )
      DUP#0=case :: DROP NDROP ;       ( repeat factor of 0 )
      DUP#1= casedrop DROP             ( repeat factor of 1 )
      OVER#0= casedrop DROP            ( group count of 0 )

      ( otherwise )
      SWAP 1LAMBIND                    ( save group count in NULLLAM )
      ONE_DO (DO)                      ( loop repfactor - 1 times )
         1GETLAM NDUP                  ( NDUP the current group )
      LOOP
      ABND                             ( abandon NULLLAM )
   ;
;

(I've also attached the code object if you want to try it out)

Using a SysRPL component is outside the scope of this challenge , but here's an example of how NMDUP might have been used:

Code:

\<<
  DUP \-> dim                     @ save the dimension
  \<<
    0. 1. ROT NDUPN               @ build the data to replicate
    DUP 1. +                      @ count of objects (N)
    SWAP 1. -                     @ total number of instances (M)
    NMDUP                         @ replicate!
    0.                            @ need final 0
    dim DUP 2. \->LIST \->ARRY    @ convert stack objects to final matrix
  \>>
\>>

Edit: changed the error that is thrown if the stack doesn't have enough objects for NMDUP, and clarified the compatible platforms.

[Gerald H]

HP 38G solves the problem economically:

Code:

MAKEMAT(I≠J,Ans,Ans):

[Gerald H]

Although some have a different definition

https://www.mathworks.com/matlabcentral/...ity-matrix

38G solution provided by

Code:

MAKEMAT(I+J==Ans+1,Ans,Ans):

[pier4r]

(05-14-2018 07:12 PM)DavidM Wrote:  Nmdup

Neat! listext? at least hpcalc.org?

[DavidM]

(05-15-2018 05:45 AM)Gerald H Wrote:  HP 38G solves the problem economically:

Code:

MAKEMAT(I≠J,Ans,Ans):

That looks similar to Didier's version that used LCXM. Does MAKEMAT work in a similar way to LCXM? How does it perform on the 38g?

[DavidM]

(05-15-2018 10:36 AM)pier4r Wrote:  

(05-14-2018 07:12 PM)DavidM Wrote:  Nmdup

Neat! listext? at least hpcalc.org?

ListExt already has a similar list-focused command (LMRPT). It doesn't need the "group size" argument, as that is inherently defined by the list argument itself.

Example:
{ 1 2 3 } 4 LMRPT => { 1 2 3 1 2 3 1 2 3 1 2 3 }

It also accepts a non-list object as the first argument, and in that case simply acts like NDUPN →LIST:

1 4 LMRPT => { 1 1 1 1 }

LMRPT is a relatively good performer. « 30 1 OVER LMRPT SWAP LMRPT » creates a 900-element list in about 0.08s on a 50g.

NMDUP could be useful as a post in the General Software Library, so I'll put something together for that.

[Gerald H]

38G programme processes input 30 in a commendable 20 sec.

[David Hayden]

Code:

DUPDUP 2. \->LIST 1. CON SWAP IDN -

With input 30, it takes 2.47 seconds on a 50g.

A modified version of Claudio's program takes 3.4 seconds:

Code:

IDN DUP 1. CON SWAP -

[toml_12953]

(05-15-2018 05:45 AM)Gerald H Wrote:  HP 38G solves the problem economically:

Code:

MAKEMAT(I≠J,Ans,Ans):

The Prime works the same way but its execution time is measured in milliseconds.