(49G, 49g+ & 50g) ZREV: Speedily Reverse Digits of Integer

[Gerald H]

For integer input Z the programme returns the reversed digits integer,

eg for input

778

the programme returns

877.

The programme is much faster than converting to a string, SREV & converting to an object.

NB: FPTR 2 A5 has been a stable pointer at least from 1.19-6 on.

Size: 37.

CkSum: # 262Eh

ZREV

Code:

::
  CK1&Dispatch
  # FF
  ::
    FPTR 2 A5
    BINT11
    OVERLEN$
    #1-SUB$
    FPTR2 ^S>Z
  ;
;

[DavidM]

That's a nice way to use →H, Gerald!

A couple of minor issues:
- Sign is lost
- 0 (exact integer zero) has a unique representation in memory, so the algorithm generates an error for that specific input

I hope you don't mind my offering an alternative. This is bigger (mostly due to the Saturn code block), but in addition to handling the above issues, it also:
- has overloaded handlers for lists and strings so that all three types of objects can be passed to it
- is a wee bit faster for exact integers

Size: 108.5 bytes
Cksum: # 172Ah

Code:

::
   CK1NOLASTWD
   CK&DISPATCH1
   BINT255d ( zint ) ::
      TOTEMPOB
      CODE
         SAVE
         A=DAT1 A
         D1=A
         D1+5
         A=DAT1 A
         A-6 A
         C=0 A
         LC 2
         ?A<C A -> .Exit
         D1+5
         CD1EX
         D1=C
         C-1 A
         C+A A
         D0=C
         ASRB A
         A-1 A
         B=A A
         {
            A=DAT0 P
            C=DAT1 P
            DAT0=C P
            DAT1=A P
            D1+1
            D0-1
            B-1 A
            UPNC
         }
         *.Exit
         LOADRPL
      ENDCODE
      FPTR2 ^ZTrim
   ;
   list ::
      INNERCOMP
      reversym
      {}N
   ;
   str ::
      EvalNoCK:_ ROMPTR 100 F
   ;
;

[John Keith]

(03-12-2018 01:20 AM)DavidM Wrote:  it also:
- has overloaded handlers for lists and strings so that all three types of objects can be passed to it
- is a wee bit faster for exact integers

Woohoo! This is something I have been wishing for for years. I am hoping this will end up in the ListExt Library, in which case I humbly suggest the name REV.

[TheKaneB]

Some of you guys can explain to me how / why this works? I'm having a hard time trying to figure out what the code does. I know a bit of UserRPL, but nothing about SysRPL or Saturn assembly whatsoever
Thanks!

[rprosperi]

(03-14-2018 12:36 AM)TheKaneB Wrote:  Some of you guys can explain to me how / why this works? I'm having a hard time trying to figure out what the code does. I know a bit of UserRPL, but nothing about SysRPL or Saturn assembly whatsoever

Although I look forward to reading replies to this (a real challenge!), with all due respect, I'd suggest you spend time on some basic SysRPL for a while, and then some basic Saturn assembler, before trying to understand something sophisticated like this, it uses lots of SysRPL features and techniques, and it's well... sophisticated and not a good intro to these subjects. And please don't misunderstand, I don't understand much of it either, I've just seen enough of these programs to recognize them.

But as I said, I look forward to reading David's reply.

[DavidM]

(03-14-2018 01:17 AM)rprosperi Wrote:  But as I said, I look forward to reading David's reply.

I may disappoint you, Bob. Note that this response has been affected by the fact that I've been up for over 40 hours now with no sleep. While it may take some work to follow, I promise that there is actually some truth contained herein.

Rather than addressing the structural and syntactical components of SysRPL and Saturn code (which any 12-year-old with 16 years of experience could do ), I'll attempt to paraphrase what I believe the two different programs do.

Gerald's:

This one makes use of the core of one of the commands available in the "development menu" (specifically →H, the first command available in menu 256). That command converts any RPL object into a string that contains the hex representation of the actual data that is stored internally for the object.

To see examples of this command, first execute 256 MENU in RPN mode. You'll see a menu that starts with →H. Now, place any object on the stack, then press the F1 key (which maps to →H). You'll see the hex representation of that object as the result. Now try to convert some exact integers (reals are also interesting, but not as important for the discussion du jour). You'll find that the exact integers are converted to a string that always starts with "41620..." (which is the defined prologue for an exact integer, reversed), then has 5 more characters that represent the length (in nibbles) of everything except that first "41620" (reversed), then the digits of the integer in reverse order of the integer in question, then either a 0, a 9, or nothing (if you convert 0). That last digit represents the sign of the integer (0=+, 9=-). The astute reader may notice that I've used the word "reversed" (or some form of it) quite a bit here. This is not an accident. Stare at these hex representations of exact integers for a little while and I promise you'll see why this penchant for reversing is helpful here.

After determining that you provided an exact integer argument, Gerald's program simply converts it to hex form (as a string), then extracts the digits needed for the result (as a string), then converts that string back to an integer. He essentially always starts at the 11th character and takes everything up to (and including) the penultimate character as that substring. If you look at the hex data for the exact integer 0, you'll see why that one doesn't work.

David's:

I'll ignore the part of the code that "overloads" specific functionality for different object types, as that fits squarely into the "structural/syntactical" realm which is beyond the scope of what I'm trying to convey here.

Given an exact integer, my program starts off by making a copy of what it was given. This is important because the "reversing" of the digits in this program is actually performed "in place" for the raw object, so a copy must be made to fulfill the calculator's need to still support things like Last Stack, UNDO, LASTARG, etc. By "etc.", I mean some fairly esoteric but important things such as "if you directly change one object that is duplicated on the stack, all of the duplicates will show the same edited version". This is not what most people expect to happen on their calculators, so it should be avoided unless you simply like to write programs that confuse people.

Since we already know the structure of the exact integer in memory (see above), we can make an important assumption based on the length of the object: if the length (less 6) is less than 2, then we don't have to do anything at all. Yay! Go Directly to GO, collect $200. We're done! Notice that this logic automatically handles 0 in the same fashion as all other single-digit integers, despite the fact that it has a severe attitude about its independent representation ("I'm 0 -- I don't need no stinkin' sign digit!").

If the count of the digits (length-6) is 2 or more, then "a-swapping we will go, a-swapping we will go, hi ho the derry oh, a-swapping we will go!". The core of the subroutine then simply uses a time-honored approach to performing a reversal. Start with the first and last digits, swap them, then move "inward" to the next two digits and repeat! (a total of length DIV 2 times). A happy bi-product of this approach is that an odd number of digits ignores that central digit, which of course can't be swapped with itself without a visit to a psychiatrist.

If you're still paying attention (and I'm quite certain very few of you are), then you may have noticed that I've used 6 several times as an offset to the length. Why is that???? Here's a hint: that 6 can be thought of as 5+1. 1 is the sign digit. What is the 5? See if you can figure it out.

Note that by only swapping the digits (and ignoring the sign), we end up carrying the sign to the result without even trying. Those are my favorite kinds of programming results. We get to claim a feature ("I added support for preserving the sign!") simply by not doing anything at all. It's hard work, but somebody has to do it.

[TheKaneB]

Thank you David! That was exactly the kind of explanation I was looking for

I suspected that you did manipulate the raw nibble representation of the integer, but I couldn't figure out the details.

[Gerald H]

Only just noticed your programme, DavidM, & pleased you took the time to write your programme.

Your programme processes a 27,890 digit integer in a quarter the time my programme takes, so will replace my programme in my integer library.

Bravo!

[DavidM]

(03-20-2018 08:09 PM)Gerald H Wrote:  Only just noticed your programme, DavidM, & pleased you took the time to write your programme. ...

Thanks, Gerald. I still think your approach was inspired -- I'm sure I never would have thought of using that method. I'll definitely remember it in the future, though. I'm sure a need for it will come up again sometime.