RPL mini-challenge: Create an anti-Identity Matrix

[DavidM]

Inspired by Ángel Martin's 41CL quiz, I am intrigued by the concept of the "anti-Identity" matrix. Not having a 41CL prevents me from participating in the quiz, but I thought I might experiment with an RPL version of the first part his challenge: creating the anti-Identity matrix.

John Keith came up with a very similar RPL program to my first attempt, which essentially creates the matrix by generating a matrix of 1s and subtracting its identity from it. This makes for a compact solution, but it strikes me that it's not very internally efficient. The result is good, of course, but the majority of computation to create it is unnecessary (there's lots of 1-0 going on to get the final matrix). This extra computation slows it down.

So here's the challenge:

Given an integer input in stack level 1 representing the dimension of the square matrix, create the anti-Identity form as quickly as possible (all 1s except for 0s on the diagonal).

Rules:
- To simplify the approach, you may assume that the input is a valid integer > 1.
- Standard User RPL commands only for HP 49G and later systems (no SysRPL, Saturn, SYSEVALs, or third-party commands).
- To make it more interesting on the 48-series systems, strategic SYSEVAL commands may be used if desired (provided they aren't used to simply execute an entire block of SysRPL or Saturn code).
- Winners will be based on execution time of an input of 30, but the program should work properly with other inputs as well.
- Execution time is defined as the time to complete the program on real hardware as opposed to an emulator.
- Assume approximate mode for both constants and calculations on systems that support exact integers (49G-49g+-50g-48gII).

[Gerald H]

Processes 30 in 1.4 sec on 50g.

SIZE 80.

CKSUM # 14A3h

Code:

« → S
  « { S } 1 CON 1 S
    FOR i DUP i 0 PUT SWAP
    NEXT DROP S ROW→
  »
»

[Claudio L.]

Basic concept, squeezed a byte here and there:

Code:


«
  IDN NEG DUP 1 CON + 
»

And element-by-element concept:

Code:


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

I don't have timings or byte counts since I did it in newRPL. Somebody with a 50g in hand could measure?

[Zaphod]

(05-12-2018 07:33 PM)Claudio L. Wrote:  I don't have timings or byte counts since I did it in newRPL. Somebody with a 50g in hand could measure?

1st version 5.5secs ish
2nd version 3 secs ish

[3298]

There is a weird little command called RDM that's probably not that useful in many contexts, but here it can do some work.
The idea is that a matrix like this:

Code:

[
  [ 0. 1. 1. 1. 1. ]
  [ 0. 1. 1. 1. 1. ]
  [ 0. 1. 1. 1. 1. ]
]

is almost identical to a 4-by-4 anti-identity matrix when read line by line (only the final 0. is missing). And RDM is all we need to reformat this into the desired anti-identity matrix (it creates new elements with value 0. as needed, so the missing element is not a problem; we don't even need to overwrite it afterwards because in this case we want exactly that value). In the end all we have to do is generate this other matrix which looks nicely uniform, so we can just do it with a pair of NDUPN and some \->ARRY and ROW\-> sprinkled in. The rest of the code should be trivial to follow:

Code:

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

Comparing the average timing over 20 runs with input 30. (1.02098_s) with that of the trivial solution using primarily IDN and CON (2.443935_s in my implementation), the RDM approach seems to be quite a bit faster. For reference, this is my implementation of the trivial solution:

Code:

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

[Gerald H]

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.

[DavidM]

These are some great solutions so far, please keep them coming!

I should have foreseen the exact vs. approximate number issue and clarified it before this came up, but I think the appropriate standard in this case is to assume approximate mode for all constants and calculations. Though there are obviously exceptions, I still think that should help more implementations than it hurts.

I'm open-minded on the topic, though. If the majority feel otherwise, please speak up.

[pier4r]

Nice thread!

Why I don't see any Axl?

The idea if the identity matrix complemented, although slow, is neat.

[DavidM]

(05-12-2018 10:00 PM)pier4r Wrote:  Why I don't see any Axl?

Because you haven't posted yours yet.

Give it a try!

[Claudio L.]

(05-12-2018 08:04 PM)Zaphod Wrote:  1st version 5.5secs ish
2nd version 3 secs ish

Thanks for the timings. Ouch, very slow...

(05-12-2018 10:00 PM)pier4r Wrote:  Why I don't see any Axl?

It's not going to be any faster, but perhaps more minimalist:

Code:


«
  IDN AXL NOT AXL 
»

EDIT: Here's a second attempt at an element-by-element method:

Code:


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

[DavidM]

(05-13-2018 02:29 AM)Claudio L. Wrote:  

(05-12-2018 08:04 PM)Zaphod Wrote:  1st version 5.5secs ish
2nd version 3 secs ish

Thanks for the timings. Ouch, very slow...

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

I'm not sure about the difference with Zaphod's timings. Perhaps he was using a different calculator? The above figures were the average of 10 iterations using 30 (or 30.) as the input, each iteration being prefaced by a GC that was excluded from the timing window.

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.

Edit: We were posting at (nearly) the same time. The timings above are for the second program in your original post, not the most recent one you posted. I'll post an update after I run the most recent one under the same conditions. I think it will be slower, though.

[DavidM]

...and Claudio's most recent program (included here for clarity):

Code:

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

Exact mode: 21.03s
Approx. mode: 4.42s

[DavidM]

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

[Joe Horn]

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

How about this:

<< IDN << NOT >> MAP >>

[Zaphod]

(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

Quote:I'm not sure about the difference with Zaphod's timings. Perhaps he was using a different calculator?

It was definitely a 50g , I'll check it again later , I did run it one or three times just for an average.

Quote: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.

oh yeah I had to remove the single quotes too of course, I forgot to mention.

[Gerald H]

Slightly faster than my 1st effort:

SIZE 59.5

CKSUM # A3AAh

Code:

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

[pier4r]

First and foremost I would like to write some opinions.

I learned in some threads of this forum that variety is really nice and healthy, so I am really happy to see different solutions, and not only those that are "fast" (or in many other threads "short").
Also I like when a problem lead to solutions of related problems or topics that do not solve the original problem, but are nonetheless valuable.

My first approach is already covered by 3298 in short:

Make a constant matrix, then subtract the identity matrix.

With fixed values just for testing

Code:


\<<
30 IDN
{ 30 30 } 1 CON
-
\>>

This is 2.49 seconds on my 50g. Although the creation of the two matrix themselves is quite fast (0.6 seconds or so) so it is the subtraction that takes time.


PS: I recently checked on youtube a video from the HHC 2011, about speed comparisons between the 15c and the 15c LE. Namir did them.
Well it is an interesting approach that can be done for userRPL (or in general) too. Putting single commands in a loop, at least the most common ones, and see how much time they take.
Although such endeavor would be quite time consuming, but highly informative.

update1: now I am attemping to use AXL (I will also use some libraries to go out of the box and have a comparison, as I wrote. Variety is nice).

Code:


@first make an identity matrix, transform in list, apply the NOT, back to matrix. 
@In newRPL can be done directly on a matrix. 
@ With MAP as Joe wrote, can be done directly too, but I don't want to change the approx mode.
\<< 30. IDN AXL 1.
  \<< 1.
    \<< NOT
    \>> DOSUBS
  \>> DOSUBS AXL
\>>
@ 5.23 secs
@ the AXL costs a bit

Code:


@ pack several lists, then AXL
@ 10.3 seconds
@ AXL here is quite quick, is the resto of the code that takes 10 seconds.
@ likely the repeated IFT
\<< 1. 30.
  FOR iter 1. 30. NDUPN \->LIST 1.
    \<< NSUB iter == NOT IFT
    \>> DOSUBS
  NEXT 30. \->LIST AXL
\>>

[grsbanks]

You need a NEG or a SWAP in there somewhere otherwise the resulting matrix has -1 (instead of 1) everywhere but on the diagonal.

Code:

\<< \-> n \<< n IDN { n n } 1 CON SWAP - \>> \>>

[pier4r]

Playing around, not yet done. The problem is the construction. The matrix routines are blazing fast but then editing them is a pain (subtraction for example). So better to construct them right directly.

Still fixed values (adapting with variables shouldn't be that hard but will cost some additional time).
Edit: oh this idea is very similar to the one from Claudio already.

Code:


@1.04 seconds
\<< -1. 28.
  FOR iter 1. 29. NDUPN iter - 0. SWAP ROLLD 30. \->LIST
  NEXT 30. \->LIST AXL
\>>

The code from claudio (post http://www.hpmuseum.org/forum/thread-107...l#pid97587) here is pretty fast. It is like mine, only he is better, he is creating all the 900 elements on the stack (I create 30 elements each time) and then using the array command to compact them in a matrix. Neat. I did not know!
The part that I never like is that without comments one has to debug the code to understand what the code is doing. And that shouldn't happen.

Code:


@0.32 seconds
\<< 0. 29.
  FOR K 
  1. 29. NDUPN 1. + K - 0. SWAP ROLLD
  NEXT 
  29. 1. + 
  DUP 2. \->LIST 
  \->ARRY
\>>

Code:


@6.5 seconds
@ replacing { with [ in string operations.
@ so AXL is not that bad
\<< -1. 28.
  FOR iter 
    1. 29. NDUPN iter - 0. SWAP ROLLD 
    30. \->LIST
  NEXT 
  30. \->LIST 
  \->STR 
  "{" "[" SREPL DROP 
  "}" "]" SREPL DROP 
  OBJ\->
\>>

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.

[pier4r]

OK thanks to Claudio I discovered that \->ARRY is pretty flexible (I did not know, therefore I was in love with AXL) and thanks to 3298 with his idea (see, comments! I likely had ignored his code without comments) it gets even faster.

I'd say that the merit is 60% the observation of 3298, 25% the properly picked commands by Claudio, 15% my luck combining and testing things while ranting about comments.

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
\>>

For example with absence of comments or discussions I - I speak only for myself - will never bother to use code that is difficult to decode without copying it and debugging it. Unless getting a similar solution by myself (or via google) is harder.

I picked the code of Claudio only because I got a similar solution by myself, and therefore I could "decode" it, plus David commented on it that was 0.3 seconds and added interest on it. Otherwise I wouldn't have checked it.


edit: next step. using additional list processing commands, like listExt.