[SOLVED] DSRN (dog slow roman numerals)

[DavidM]

(06-13-2014 05:40 PM)rprosperi Wrote:  Please do share it. The folks that know SysRPL will enjoy it (and likely attempt to improve it) and the folks that don't will get a taste of what SysRPL is like, to compare. Also, please post the analogous performance numbers as an additional incentive for the non-SysRPL folks.

OK. This was what I started out with, and there's certainly room for improvement.

To help those less familiar with SysRPL, I've included lots of comments to help clarify what the code is doing. This probably makes the code seem bigger than it really is; in compiled form, it only consumes 301.5 bytes. All of the UserRPL examples are larger than that, although Thomas' last submission is close at 318.5 bytes.

From a performance standpoint, when I test this code using the same loop as the others (converting 1000-1499) it shows a cycle time of 0.01923 sec.

Here's the code:

Code:

RPL

( constants [and their definitions] used by the app )
DEFINE  TotalLAMs     BINT3
DEFINE  RomNumSub     1GETLAM EVAL
DEFINE  GetResult     2GETLAM
DEFINE  PutResult     2PUTLAM
DEFINE  GetCurVal     3GETLAM
DEFINE  PutCurVal     3PUTLAM

::
  CK1NOLASTWD                         ( must have at least one item on stack          )
  CK&DISPATCH1                        ( check the value's type [real or zint->real]   )
  real
  ::
    COERCE                            ( LAM 3 - CurVal [converted to a BINT]          )
    NULL$                             ( LAM 2 - Result                                )
    ' ::                              ( LAM 1 - RomNumSub subroutine                  )
                                      ( upon entry: SL2-> String, SL1-> Magnitude     )

      GetCurVal SWAP #/               ( divide current value by magnitude             )
                                      ( note: #/ returns #r #q                        )
      SWAP PutCurVal                  ( save remainder as new current value,          )
                                      (    leave quotient on stack                    )
      NDUPN                           ( make [quotient] copies of roman numerals      )
      DUP#0<>                         ( check to see if any digits need to be added   )
      ITE
      ::                              ( yes - accumulate digits                       )
        BEGIN
          #1-DUP #0<>                 (   loop 1 less time than # of duplicates       )
        WHILE
          :: UNROT &$SWAP ;           (   combine digits, swap counter into SL1       )
        REPEAT
        DROP                          (   drop the duplicate count                    )
        GetResult SWAP&$ PutResult    (   append the new digits to the result         )
      ;
        DROP                          ( no digits to add - just drop the count        )
    ;
    NULLLAM TotalLAMs NDUPN DOBIND    ( Bind LAMs                                     )

    ( build the result string )
    "M"   # 3E8     RomNumSub         ( 1000 )
    "CM"  # 384     RomNumSub         (  900 )
    "D"   # 1F4     RomNumSub         (  500 )
    "CD"  # 190     RomNumSub         (  400 )
    "C"   BINT100   RomNumSub         (  100 )
    "XC"  BINT90    RomNumSub         (   90 )
    "L"   BINT50    RomNumSub         (   50 )
    "XL"  BINT40    RomNumSub         (   40 )
    "X"   BINT10    RomNumSub         (   10 )
    "IX"  BINT9     RomNumSub         (    9 )
    "V"   BINT5     RomNumSub         (    5 )
    "IV"  BINT4     RomNumSub         (    4 )
    "I"   BINT1     RomNumSub         (    1 )

    GetResult                         ( retreive result                               )
    ABND                              ( abandon LAMs                                  )
  ;
;

[Thomas Klemm]

(06-13-2014 11:19 AM)Dave Britten Wrote:  IDIV2 isn't present on the 48, however.

Actually I had longer to implement a replacement for NDUPN.

Thanks a lot for your contributions. The comments in your program are very helpful.
I had to fumble a little with Debug4x but I finally made your SysRPL program run in the HP-50g emulator.

Cheers
Thomas

[Dave Britten]

(06-13-2014 09:14 PM)Thomas Klemm Wrote:  

(06-13-2014 11:19 AM)Dave Britten Wrote:  IDIV2 isn't present on the 48, however.

Actually I had longer to implement a replacement for NDUPN.

Oh yeah, didn't even notice that one was missing too. This is a pretty fast NDUPN replacement.

Code:

\<< \-> X \<< 2 X START DUP NEXT X \>> \>>

I don't know if it responds the same way as a real 50g if you feed it nonsense, though (e.g. n < 2).

[kakima]

Doesn't do much for the speed, but a ridiculously simple change shaves more than 10% off the size.

Code:


RPL

( constants [and their definitions] used by the app )
DEFINE  TotalLAMs     BINT3
DEFINE  GetResult     1GETLAM
DEFINE  PutResult     1PUTLAM
DEFINE  RomNumSub     2GETEVAL
DEFINE  GetCurVal     3GETLAM
DEFINE  PutCurVal     3PUTLAM

::
  CK1NOLASTWD                         ( must have at least one item on stack          )
  CK&DISPATCH1                        ( check the value's type [real or zint->real]   )
  real
  ::
    COERCE                            ( LAM 3 - CurVal [converted to a BINT]          )
    ' ::                              ( LAM 2 - RomNumSub subroutine                  )
                                      ( upon entry: SL2-> String, SL1-> Magnitude     )

      GetCurVal SWAP #/               ( divide current value by magnitude             )
                                      ( note: #/ returns #r #q                        )
      SWAP PutCurVal                  ( save remainder as new current value,          )
                                      (    leave quotient on stack                    )
      NDUPN                           ( make [quotient] copies of roman numerals      )
      DUP#0<>                         ( check to see if any digits need to be added   )
      ITE
      ::                              ( yes - accumulate digits                       )
        BEGIN
          #1-DUP #0<>                 (   loop 1 less time than # of duplicates       )
        WHILE
          :: UNROT &$SWAP ;           (   combine digits, swap counter into SL1       )
        REPEAT
        DROP                          (   drop the duplicate count                    )
        GetResult SWAP&$ PutResult    (   append the new digits to the result         )
      ;
        DROP                          ( no digits to add - just drop the count        )
    ;
    NULL$                             ( LAM 1 - Result                                )
*   NULLLAM TotalLAMs NDUPN DOBIND    ( Bind LAMs                                     )
    PTR 27208 BIND

    ( build the result string )
    "M"   # 3E8     RomNumSub         ( 1000 )
    "CM"  # 384     RomNumSub         (  900 )
    "D"   # 1F4     RomNumSub         (  500 )
    "CD"  # 190     RomNumSub         (  400 )
    "C"   BINT100   RomNumSub         (  100 )
    "XC"  BINT90    RomNumSub         (   90 )
    "L"   BINT50    RomNumSub         (   50 )
    "XL"  BINT40    RomNumSub         (   40 )
    "X"   BINT10    RomNumSub         (   10 )
    "IX"  BINT9     RomNumSub         (    9 )
    "V"   BINT5     RomNumSub         (    5 )
    "IV"  BINT4     RomNumSub         (    4 )
    "I"   BINT1     RomNumSub         (    1 )

    GetResult                         ( retrieve result                               )
    ABND                              ( abandon LAMs                                  )
  ;
;

In case it's not obvious, I mainly rearranged the temporaries so as to be able to use the 2GETEVAL word, saving 32.5 bytes. I also saved another five bytes in the binding.

[Thomas Klemm]

(06-14-2014 12:38 AM)Dave Britten Wrote:  This is a pretty fast NDUPN replacement.

Code:

\<< \-> X \<< 2 X START DUP NEXT X \>> \>>

Since we need NDUPN DROP we could avoid the local variable:

Code:

\<< 2 SWAP START DUP NEXT \>>

Quote:I don't know if it responds the same way as a real 50g if you feed it nonsense, though (e.g. n < 2).

Unfortunately this nonsensical case happens often.

Cheers
Thomas

[DavidM]

(06-14-2014 02:27 AM)kakima Wrote:  Doesn't do much for the speed, but a ridiculously simple change shaves more than 10% off the size.

Code:

...
DEFINE  RomNumSub     2GETEVAL
...

Thanks for pointing that out, kakima. 2GETEVAL is one of the (many) SysRPL statements that I hadn't yet run across.

(06-14-2014 02:27 AM)kakima Wrote:  ...
PTR 27208 BIND
...I also saved another five bytes in the binding.

For anyone else that's using Debug4x, the line referenced above doesn't seem to compile properly (at least it didn't on my system). You can substitute the following:

Code:

3NULLLAM{}_ BIND

This does the same thing.

- David

[DavidM]

(06-14-2014 07:36 AM)Thomas Klemm Wrote:  Unfortunately this nonsensical case happens often.

As was the case in my original DOLIST version of the roman numeral program. It depended on the characters being deleted (in the case of 0) or simply not duplicated at all (in the case of 1).

NDUPN is actually available in the ROM of the 48 series, but you would have to use SYSEVALs to gain access to it from UserRPL. In a controlled situation, it may make sense to use them if you are careful.

Fine print: All the usual disclaimers apply for using SYSEVALs

Edit: added "from UserRPL" above

[Claudio L.]

(06-13-2014 05:15 PM)DavidM Wrote:  I was curious as to how these various algorithms performed, so I did some testing and came up with the following for cycle timings:

HP1 (HP67's original): 0.11592 sec
DB1: 0.07968 sec
TK1: 0.13363 sec
TK2: 5.02521 sec
DM1: 0.91066 sec
TK3: 0.89567 sec

Very interesting thread.
I did a series of runs of the same code on newRPL (running on a PC, not on real hardware). I ran 100 times your loop from 1000 to 1499 to get more accurate time measurements. They are not comparable with your results but comparing between algorithms shows how a different implementation of RPL can affect the times:

HP1: 0.789 seconds
DB1: 0.516 seconds
TK1: 0.793 seconds
TK2: 1.173 seconds

Scaling everything to the original HP1 algorithm I get:

userRPL / newRPL
HP1 (by definition) = 1.0 / 1.0
DB1 = 0.687 / 0.653
TK1 = 1.153 / 1.005
TK2 = 43.351 / 1.487

So it seems in terms of loops, newRPL and userRPL show about the same ratios. Actually, TK1, which is more dependent on local variable evaluation shows newRPL doing a little better. List processing (STREAM used in TK2), however, shows only a slight slowdown in newRPL (expected due to the overhead of manipulating lists), versus a huge slowdown in userRPL. This might be due to list processing being implemented in sysRPL in the ROM.
I couldn't run TK2 and DM since they use a couple of words that aren't implemented yet.

(06-13-2014 05:15 PM)DavidM Wrote:  While doing the timings, I also found a bug in my app. If the resulting string only has one character (as in "M" for 1000), \GSLIST will error out proclaiming an invalid dimension. So I had to insert an empty string into the list ("" +) just before \GSLIST was called to make sure it always had something to add.

I found that behavior when implementing \GSLIST and it didn't make any sense. The sum of an empty list should give an error, but a list with one element has a clear result. So in newRPL that command is implemented as it should be.
I couldn't run your version, but your code would've executed correctly under newRPL.

Claudio

[kakima]

Quote:I found that behavior when implementing \GSLIST and it didn't make any sense.

It makes sense from a misguided efficiency viewpoint. Someone apparently optimized it by making it require only n-1 trips through the loop for an n-element list. Unfortunately it also means we have to guard against it anytime a list may have only one element.

The same thing applies to the product.

[Dave Britten]

(06-14-2014 07:36 AM)Thomas Klemm Wrote:  

(06-14-2014 12:38 AM)Dave Britten Wrote:  This is a pretty fast NDUPN replacement.

Code:

\<< \-> X \<< 2 X START DUP NEXT X \>> \>>

Since we need NDUPN DROP we could avoid the local variable:

Code:

\<< 2 SWAP START DUP NEXT \>>

Quote:I don't know if it responds the same way as a real 50g if you feed it nonsense, though (e.g. n < 2).

Unfortunately this nonsensical case happens often.

Cheers
Thomas

Alright, here's an NDUPN that behaves a little more like the 50G if you feed it a negative/zero/non-integer N:

Code:

\<< 0 RND 0 MAX \-> X N
  \<<
    IF N
    THEN 1 N
      START X
      NEXT
    END N
  \>>
\>>

[Thomas Klemm]

(06-15-2014 01:22 AM)Claudio L. Wrote:  I found that behavior when implementing \GSLIST and it didn't make any sense.

Look at it as: \<< + \>> STREAM
What happens when you execute + with only one number on the stack?
Error: Too Few Arguments

Quote:The sum of an empty list should give an error, but a list with one element has a clear result.

Or then the sum of an empty list is 0 as in Lisp.
And the product of an empty list is 1.

Code:

 > (+ 3 4)
=> 7
 > (+ 3)
=> 3
 > (+)
=> 0
 > (* 3 4)
=> 12
 > (* 3)
=> 3
 > (*)
=> 1

Cheers
Thomas

[Claudio L.]

(06-15-2014 04:30 AM)Thomas Klemm Wrote:  Look at it as: \<< + \>> STREAM
What happens when you execute + with only one number on the stack?
Error: Too Few Arguments

The real question to ask is "Why should I look at it that way?"
I look at it from its meaning and what a user/developer might use it for. It tripped David, and forced him to adapt his code to the limitations of the function. That shouldn't happen with a good API unless there's a good reason for it. Back in the day of userRPL, there probably was a good reason, as they needed to implement it in the simplest/fastest way, but in 2014 I can't find any good reason.

(06-15-2014 04:30 AM)Thomas Klemm Wrote:  Or then the sum of an empty list is 0 as in Lisp.
And the product of an empty list is 1.

Code:

 > (+ 3 4)
=> 7
 > (+ 3)
=> 3
 > (+)
=> 0
 > (* 3 4)
=> 12
 > (* 3)
=> 3
 > (*)
=> 1

Yes, I thought about that too, and I'm still open to change it, but then I thought that the elements of the list may not be numbers, but for example strings.
The sum of a list of strings is a string, so the empty list should give an empty string, not a number. Same thing for a list of vectors: shouldn't it be a zero vector?
In the end I thought that it was more appropriate to say that the sum of an empty list is undefined because we don't know the object type of the answer, so an error is appropriate after all.
On the other hand, if you have one element, the result is that element and it's a clear and fully defined answer.
For the product is the same: should I return the number one? or an identity matrix?

Claudio

[HP67]

(06-11-2014 08:23 PM)Dave Britten Wrote:  I'm guessing it could be even faster if you get rid of the A subroutine and unroll it wherever it's used, but then the program will get even more bloated.

As mentioned earlier, I didn't add the code at the end of the while until the 2nd pass, where I factored it out of each case condition. Putting the code back in both versions (not using a local subroutine) and using your modification of changing the case into a bunch of whiles runs 33% faster. Net, removing the local subroutine saves about 9 seconds on a test of 1,000 tries. So most of the time savings was in your case --> while (which I really like) and not so much in whether we use a local subroutine, put the code at the end of the while, to be executed for each pass, or whether we unroll the code and put it next to each case/while clause.

As far as what was brought up about \gslist not exactly behaving nicely for edge cases, yeah. I have some code that goes the other way (from roman numerals to real values) using lists, and I bumped into this a couple of weeks ago. I don't know how much this happens with other commands, but I really prefer the way LISP handles this rather than having to deal with 3 classes of input lists (size > 1, size = 1, size = 0). It's easy to wrapper this, but annoying.

As much as command and operator overloading look nice on the surface, I think this is another example of where the downside is apparent and TIINSTAFL.

[Claudio L.]

(06-13-2014 05:15 PM)DavidM Wrote:  So I had to insert an empty string into the list ("" +) just before \GSLIST was called to make sure it always had something to add.

This is a neat trick, and it also solves the problem of an empty list: if the list is empty, by adding the additive zero object (in whatever object type you are working on, on your case strings), the list ends up with the element zero of the correct type, so \GSLIST implemented to work on one element would return the proper value.

For the current implementation you'd have to append the zero object twice to make sure it doesn't fail for empty lists:

Code:


<< "" + "" + >>

And the same trick works by adding the unity object for the product of a list.
I'll make sure to remember this trick to put in the documentation of these commands (I hope you are not planning to patent this trick!).

Claudio

[Claudio L.]

(06-15-2014 12:02 PM)HP67 Wrote:  As much as command and operator overloading look nice on the surface, I think this is another example of where the downside is apparent and TIINSTAFL.

Excuse my ignorance... but what's the meaning of TIINSTAFL?

Claudio

[Massimo Gnerucci]

(06-15-2014 06:28 PM)Claudio L. Wrote:  

(06-15-2014 12:02 PM)HP67 Wrote:  As much as command and operator overloading look nice on the surface, I think this is another example of where the downside is apparent and TIINSTAFL.

Excuse my ignorance... but what's the meaning of TIINSTAFL?

Claudio

There Is No Such Thing As A Free Lunch?

[Claudio L.]

(06-15-2014 06:33 PM)Massimo Gnerucci Wrote:  

(06-15-2014 06:28 PM)Claudio L. Wrote:  Excuse my ignorance... but what's the meaning of TIINSTAFL?

Claudio

There Is No Such Thing As A Free Lunch?

Thanks, sometimes people forget that some of us are not native english speakers, I would've never guessed it on my own.

Claudio

[Claudio L.]

(06-15-2014 12:02 PM)HP67 Wrote:  As much as command and operator overloading look nice on the surface, I think this is another example of where the downside is apparent and TIINSTAFL.

Now that Massimo helped me with the language (thanks!), I finally understood what you meant, but what's the downside that is so apparent? I fail to see it, the backend is been working solid for several months now with overloadable operators doing all the grunt work.
What would be a down side in your opinion?

Claudio

[Thomas Klemm]

(06-15-2014 06:48 PM)Claudio L. Wrote:  What would be a down side in your opinion?

I have a problem with overloading + for operations that violate basic rules of addition.
In the case of string concatenation it is the commutative property: "a" + "b" ≠ "b" + "a"
For this operation another symbol should be used: . or ~ or ++ or whatever.

It's the same with concatenating lists. But it gets worse with the "addition" of an element to a list.
Why is { 1 2 3 } + 4 = { 1 2 3 4 } but { 5 6 7 } - 4 = { 1 2 3 }?
But then 4 + { 1 2 3 } = { 5 6 7 }.
And if you really want to add a number to each element you have to use ADD: { 1 2 3 } ADD 4 = { 5 6 7 }
I still think this was the worst decision when designing RPL.

Cheers
Thomas

[Thomas Klemm]

(06-15-2014 11:49 AM)Claudio L. Wrote:  The real question to ask is "Why should I look at it that way?"

You don't have to. However it shows consistency of ΣLIST and ΠLIST with STREAM.

I agree with you that the current implementation violates the principle of least surprise. It not only tripped David but me as well. But trying to understand doesn't mean I prefer the current implementation.

Besides this I was also surprised by the FOR-loop: why is the loop executed at least once even when finish < start?

In both cases I guessed corner cases wrong. Most probably because I'm more familiar with other languages than RPL.

Quote:The sum of a list of strings is a string, so the empty list should give an empty string, not a number.

Besides the violation of the commutative property this is another reason why + shouldn't be overloaded for string concatenation: 0 is not a neutral element.

Thinking about it a little more maybe providing foldl, foldr and filter similar to Haskell would be more beneficial than trying to fix the behavior of existing functions.

You may not agree with the Linux way: never ever break user experience. But I think there is truth in the following quote:

Quote:The biggest thing any program can do is not the technical details of the program itself; it’s how useful the program is to users.

Kind regards
Thomas