Little problem(s) July 2022

[Albert Chan]

(07-06-2022 01:29 PM)John Keith Wrote:  This is a very good solution, especially for languages that have sets or binary trees as data types.
On the HP48, unfortunately, a UserRPL implementation would be slower than one using POS.

Solution only need O(1) array lookup, not "weird" data types.

With numbers sorted, if two ends add up to required sum, we find the pair.
If more than required sum, throw away the big one.
If less, throw away the small one.

Rinse and repeat, we can find a pair (or, all of them!), with required sum, in O(n)

Of course, depending on list size, worse algorithm may be faster.
Hybrid sorting algorithms switch over algorithms, depending on data, to gain efficiency.

[DavidM]

(07-07-2022 10:51 AM)pier4r Wrote:  (I hope GET is O(1) with lists in userRPL, now I start to have doubts).

It isn't with lists, but it is with type 3 or 4 arrays.

Remember that lists can contain many different types of objects as elements (even other lists), so the size of each element may vary and cannot be assumed in advance. Lists have no associated metadata (pointers, tables, etc.) that would assist in locating specific elements. The only way to locate element n is to sequentially step through elements 1..(n-1) first.

Conversely, type 3 (real) or 4 (complex) arrays use the same-sized data for each element, so the offset of a specific element is easily computed from its indices.

The varying size of the data elements in a type 29 (symbolic/exact) array give it a data structure very similar to a list, so GET is similarly constrained with those.

[Albert Chan]

(07-07-2022 12:02 PM)DavidM Wrote:  The varying size of the data elements in a type 29 (symbolic/exact) array give it a data structure very similar to a list, so GET is similarly constrained with those.

For elements of varying size, I would guess array just stored pointer. (like Python list)
In other words, array can lookup elements in O(1) time.

---

I think list really meant linked list.
Each cell stored pointer to element, and pointer to next cell.

Cells are not stored as continuous block in memory, thus cannot do O(1) lookup.
We have to walk the links, to get to elements, thus O(n) lookup

[DavidM]

Please note that I'm talking about some HP 49/50 RPL specifics here, not general computing approaches.

(07-07-2022 01:16 PM)Albert Chan Wrote:  For elements of varying size, I would guess array just stored pointer. (like Python list)

That's not the case for RPL symbolic arrays (type 29 -- the only kind that can contain varying-length elements). As an example, the only difference between { 12 3456 } and [ 12 3456 ] internally is the initial 5-nibble prologue that defines the array/list type. All other data (elements and epilogue) is encoded in exactly the same way.

List { 12 3456 }:
47A20 41620 80000 210 41620 A0000 65430 B2130

Type 29 symbolic array [ 12 3456 ]:
68620 41620 80000 210 41620 A0000 65430 B2130

(07-07-2022 01:16 PM)Albert Chan Wrote:  I think list really meant linked list.
Each cell stored pointer to element, and pointer to next cell.

Cells are not stored as continuous block in memory, thus cannot do O(1) lookup.
We have to walk the links, to get to elements, thus O(n) lookup

UserRPL does not support any kind of linked list. The address of a particular non-firmware object can never be assumed as stable, so pointers to the objects aren't maintainable at the UserRPL level. But the result is the same as you describe -- other than type 3/4 arrays, GET has to step through each preceding object to reach the targeted one.

Side note: RPL does define an "internal only" array type (DOLNKARRY) that encodes offsets for each element in its data structure. There's no way to create such an array using User RPL, though, and the only use for it I've ever seen is for encoding built-in arrays of strings used for system messages. That allows firmware code to quickly access those varying-length strings as needed.

[pier4r]

(07-07-2022 12:02 PM)DavidM Wrote:  

(07-07-2022 10:51 AM)pier4r Wrote:  (I hope GET is O(1) with lists in userRPL, now I start to have doubts).

It isn't with lists, but it is with type 3 or 4 arrays.

Remember that lists can contain many different types of objects as elements (even other lists), so the size of each element may vary and cannot be assumed in advance. Lists have no associated metadata (pointers, tables, etc.) that would assist in locating specific elements. The only way to locate element n is to sequentially step through elements 1..(n-1) first.

Somehow I forgot (or I wanted to forget) this part. So even GET is O(n) ? Brutal, but that is the limit of small machines and arbitrary data in lists.

[DavidM]

My attempt at #3.

I wouldn't even try this without the use of the following ListExt commands:

LSUM: basically a slightly faster ΣLIST (and is a heck of lot easier to type ).
LPICK: given a list and a corresponding set of indices, returns the values from the original list indicated by those indices. Similar to calling GET for each specified index against the original source list.
DOCOMB: generates specified combinations of the provided indices and passes them to a supplied program (similar to DOLIST/DOSUBS, but passes combinations of the elements instead of each element).

DOCOMB also has a feature wherein you can tell it to abort further processing by storing something that evaluates to TRUE in the local 'XCMB'. This local is created by DOCOMB automatically and is only available while the command is processing. It is used in this case to only provide the first solution encountered.

This will slow down rather noticeably as the list size grows, of course. I believe this will be the case with just about any approach, but I don't assume that the method I've used is necessarily the best or fastest. But I believe it works for this particular situation.

Code:

\<<
   OVER SIZE DUP LSEQ                  @ setup local vars
   \-> list targ n ndx                 @ list: original list (given)
                                       @ targ: the target sum for comparison (given)
                                       @ n: current count of elements for summing, initially = count of elements
                                       @ ndx: static list of index numbers (1..count of elements)
   \<<
      {} n                             @ preload stack for loop: {}=no solution yet, count of elements to check
      WHILE
         OVER SIZE NOT AND             @ continue if no solution yet and count > 0
      REPEAT
         DROP                          @ drop the previous (empty) list of solutions
         ndx                           @ recall the complete index list
         n                             @ recall the current count
         \<<
            list OVER LPICK            @ obtain the values from the original list for summing
            LSUM targ SAME             @ check for sum = target value
            DUP 'XCMB' STO             @ set to exit DOCOMB if target found
            NOT DROPN                  @ drop the current list of indices if it did not match
         \>>
         DOCOMB                        @ execute the above program object for each combination of n indices
         'n' DECR                      @ decrement index count, recall to stack
      END
      DUP SIZE ::EVAL IFT              @ if non-empty list for final result, remove inner list brackets
   \>>
\>>

[pier4r]

Nice.

The only reference to XCMB that I could find is here. I thought that were "inside" variables.

[John Keith]

At the risk of stating the obvious, David's program without the XCMB line will return all valid combinations like Albert's Lua program. The combinations are returned in size order.

Here is a simplified version:

Code:


\<< OVER SIZE DUP R\->I LSEQ \-> list targ n ndx
  \<< 1. n
    FOR k ndx k
      { list OVER LPICK LSUM targ SAME NOT DROPN
      } DOCOMB
    NEXT n \->LIST LXIL
  \>>
\>>

[Didier Lachieze]

Here is a solution to #1 on the Texas SR-52, the first programmable calculator with indirect register addressing back in 1975. It includes the list input.

Usage: 0 STO 99 then input each list element followed by [ A ], when finished input number N and press [ B ], after some time the program will return the index of the first element, press [RUN] to get the second element. You can then input another value for N and press [ B ] without having to input the list again. If there is no solution it returns 0 and 1.

Example: 0 [STO] 99 2 [A] 7 [A] 11 [A] 15 [A] 17 [ B ] returns 1 and 4 then 18 [ B] returns 2 and 3

Performance: On my SR-52 with upgraded memory it can handle lists up to 49 elements (vs. 19 on a regular SR-52).
With the list {1,2,3...48,49} searching for 3 returns 1 and 2 in 14 minutes. This is the worst case as the loops with dsz are done starting from the last element and going down.

Code:

Texas SR-52: 73  steps
Note: it uses the same notation as in the SR-52 manual:
* for the 2nd key and ' for the numeric labels (1', 2', 3')

//List input
000 46 11         *LBL A
002 65            x
003 01 44 09 09   1 SUM 99
007 95            =
008 36 42 09 09   *IND STO 99
012 56            *rtn

//Search
013 46 12         *LBL B
015 42 06 08      STO 68   
018 43 09 09      RCL 99
021 42 00 00      STO 00

024 46 87         *LBL *1’
026 43 00 00      RCL 00    
029 42 06 09      STO 69    
032 58 88         *dsz *2’
034 41 89         GTO *3’

036 46 88         *LBL *2’
038 43 06 08      RCL  68
041 75            -
042 36 43 06 09   *IND RCL 69
046 75            -
047 36 43 00 00   *IND RCL 00
051 95            =
052 90 89         *if zro *3’
054 58 88         *dsz *2’

056 43 06 09      RCL 69
059 42 00 00      STO 00
062 58 87         *dsz *1’

064 46 89         *LBL *3’
066 43 00 00      RCL 00
069 81            HLT
070 43 06 09      RCL 69
073 56            *rtn

[pauln]

(07-10-2022 10:37 PM)Didier Lachieze Wrote:  Here is a solution to #1 on the Texas SR-52, the first programmable calculator with indirect register addressing back in 1975. It includes the list input.

Usage: 0 STO 99 then input each list element followed by [ A ], when finished input number N and press [ B ], after some time the program will return the index of the first element, press [RUN] to get the second element. You can then input another value for N and press [ B ] without having to input the list again. If there is no solution it returns 0 and 1.

Example: 0 [STO] 99 2 [A] 7 [A] 11 [A] 15 [A] 17 [ B ] returns 1 and 4 then 18 [ B] returns 2 and 3

Performance: On my SR-52 with upgraded memory it can handle lists up to 49 elements (vs. 19 on a regular SR-52).
With the list {1,2,3...48,49} searching for 3 returns 1 and 2 in 14 minutes. This is the worst case as the loops with dsz are done starting from the last element and going down.

Code:

Texas SR-52: 73  steps
Note: it uses the same notation as in the SR-52 manual:
* for the 2nd key and ' for the numeric labels (1', 2', 3')

//List input
000 46 11         *LBL A
002 65            x
003 01 44 09 09   1 SUM 99
007 95            =
008 36 42 09 09   *IND STO 99
012 56            *rtn

//Search
013 46 12         *LBL B
015 42 06 08      STO 68   
018 43 09 09      RCL 99
021 42 00 00      STO 00

024 46 87         *LBL *1’
026 43 00 00      RCL 00    
029 42 06 09      STO 69    
032 58 88         *dsz *2’
034 41 89         GTO *3’

036 46 88         *LBL *2’
038 43 06 08      RCL  68
041 75            -
042 36 43 06 09   *IND RCL 69
046 75            -
047 36 43 00 00   *IND RCL 00
051 95            =
052 90 89         *if zro *3’
054 58 88         *dsz *2’

056 43 06 09      RCL 69
059 42 00 00      STO 00
062 58 87         *dsz *1’

064 46 89         *LBL *3’
066 43 00 00      RCL 00
069 81            HLT
070 43 06 09      RCL 69
073 56            *rtn

Nice.

By the way, I have never heard of an SR-52 with upgraded memory and I don't find any info online. Is this calculator one-of-a-kind? And does it also add more steps or only more registers?

[Didier Lachieze]

(07-11-2022 05:34 AM)pauln Wrote:  By the way, I have never heard of an SR-52 with upgraded memory and I don't find any info online. Is this calculator one-of-a-kind? And does it also add more steps or only more registers?

This upgrade adds 30 registers, not more steps. It is described here, you just need one TMC0599 Multi-Register Chip.

[pauln]

(07-11-2022 08:29 AM)Didier Lachieze Wrote:  

(07-11-2022 05:34 AM)pauln Wrote:  By the way, I have never heard of an SR-52 with upgraded memory and I don't find any info online. Is this calculator one-of-a-kind? And does it also add more steps or only more registers?

This upgrade adds 30 registers, not more steps. It is described here, you just need one TMC0599 Multi-Register Chip.

Quite impressive. This is the one time that it is a good thing that SR-52 steps were not merged. I don't think this would have been possible at all in an HP-67 without using indirect addressing.

I would guess that TI had plans to have these additional registers from the start but eventually didn't do so because of the cost.