List Commands Library for 50g

[John Keith]

(01-06-2018 07:29 PM)DavidM Wrote:  I was thinking that's what GoferList's Insert did, but after looking at it more closely, Insert is more like an "append". That's an odd misnomer, given that "+" is much easier to enter into a program (and it essentially does the same thing as far as I can see). Insert does at least call AppendList, which might perform better than >TCOMP in some cases (which is what + does).

What GoferLists' Insert command actually does is to append an object to the list if and only if the list does not already contain the object. Sort of like

Code:

DUP2 POS { DROP } { + } IFTE

or perhaps + LDDUP or + Nub

I can see a benefit to either (or both!) interpretations of LINSR / Insert. What Gilles is proposing is easy enough in UserRPL but a fast Library command would of course be preferable.

John

[DavidM]

I've attached a beta release of the ListExt library with a few new commands to the first post in this thread. Gilles' LINSR command has been included. Here is its command description:

LINSR (List Insert)
(alias: LINSRT)

Input
3: { list of 0 or more objects }
2: any object or { list of objects }
1: number (insertion index)

Output
1: { list with elements inserted at the indicated position }

Inserts the object(s) given in stack level 2 into the list given in stack level 3, starting at the position indicated in stack level 1. An index value less than 2 will result in the new elements being added to the beginning of the source list, and a value greater than the length of the list will result in the elements being added to the end of the source list. Indices are rounded to the nearest integer in the range 0..1048575 prior to processing. Both the source list and/or insertion list (stack levels 2 and 3) may contain empty lists.

Examples:
{ 1 2 3 5 6 } 4 4 LINSR => { 1 2 3 4 5 6 }
{ 1 2 3 } { 4 5 6 } 999 LINSR => { 1 2 3 4 5 6 }
{ 1 2 3 4 5 6 } { A B C } 5 LINSR => { 1 2 3 4 A B C 5 6 }
{ 1 2 3 } { A B C } -50 LINSR => { A B C 1 2 3 }
{ } { 1 2 3 } 50 LINSR => { 1 2 3 }



On several occasions I have needed to create a list of numbers such as all odd/all even/every third/every fourth/etc. Noting the similarity of this type of operation to the methods used by LSEQ, I decided to add a command that creates an arithmetic sequence:

LASEQ (List Arithmetic Sequence)

Input
3: number (starting value)
2: number (common difference)
1: number (total number of elements in the result list)

Output
1: { list containing the identified sequence }

Provides a list of real numbers in sequence starting with the first number identified, then repeatedly adding the common difference to determine each successive value. The result list will always contain real numbers, regardless of the input given or numeric mode selected.

Examples:
1 1 0 LASEQ => { }
1 2 5 LASEQ => { 1. 3. 5. 7. 9. }
0 0.25 11 LASEQ => { 0. .25 .5 .75 1. 1.25 1.5 1.75 2. 2.25 2.5 }
100 -5 3 LASEQ => { 100. 95. 90. }
10 10 10 LASEQ => { 10. 20. 30. 40. 50. 60. 70. 80. 90. 100. }


While creating the code for this command, I realized that it would be very easy to make a slight change to the main loop that would facilitate creating both geometric sequences as well as "division" sequences (what are those called?). So LASEQ/LMSEQ/LDSEQ all use the same engine for creating their sequences. The engine uses Saturn routines that are specific to real numbers, so the results are always in that domain (regardless of mode settings). That also makes them all reasonably good performers:

LMSEQ (List Multiplicative Sequence)

Input
3: number (starting value)
2: number (common ratio)
1: number (total number of elements in the result list)

Output
1: { list containing the identified sequence }

Provides a list of real numbers in sequence starting with the first number identified, then repeatedly multiplying the previous result by the common ratio to determine each successive value. The result list will always contain real numbers, regardless of the input given or numeric mode selected.

Examples:
1 1 0 LMSEQ => { }
2 2 5 LMSEQ => { 2. 4. 8. 16. 32. }
1 -1 10 LMSEQ => { 1. -1. 1. -1. 1. -1. 1. -1. 1. -1. }
1 1.05 20 LMSEQ => { 1. 1.05 1.1025 1.157625 1.21550625 1.2762815625 1.34009564063 1.40710042266 1.47745544379 1.55132821598 1.62889462678 1.71033935812 1.79585632602 1.88564914232 1.97993159944 2.07892817941 2.18287458838 2.2920183178 2.40661923369 2.52695019538 }



LDSEQ (List Division Sequence)

Input
3: number (starting value)
2: number (common divisor)
1: number (total number of elements in the result list)

Output
1: { list containing the identified sequence }

Provides a list of real numbers in sequence starting with the first number identified, then repeatedly dividing the previous result by the common divisor to determine each successive value. The result list will always contain real numbers, regardless of the input given or numeric mode selected.

Examples:
1 0 2 LDSEQ => Error: Infinite Result
1 3 5 LDSEQ => { 1. .333333333333 .111111111111 .037037037037 1.23456790123E-2 }
59049 3 10 LDSEQ => { 59049. 19683. 6561. 2187. 729. 243. 81. 27. 9. 3. }


Thanks again to Gilles for pointing out the lack of an insert command. Hopefully these new features will prove useful!

[brickviking]

Attached? Where? Apologies if I've missed it. That new LST-INSRT could be pretty useful.

(Post 166)

[DavidM]

(02-03-2018 10:59 PM)brickviking Wrote:  Attached? Where? Apologies if I've missed it. That new LST-INSRT could be pretty useful.

(Post 166)

It's attached to the first post in this thread, which is here. Hope you find the new commands useful!

- David

[pier4r]

awesome DavidM.

[John Keith]

Looks great, David. I always look forward to updates. I see LASEQ and LINSR as being especially useful.

A couple of suggestions:

1). Reverse the order of the level 1 and level 2 arguments (index and object to be inserted) of LINSR. This would make it consistent with built-in commands such as REPL, as well as INSERT on the Prime.

2). LMSEQ always returns a list of reals, even in exact mode. If it can be done without undue penalties in speed and complexity, I would prefer it return a list of integers in exact mode, as long as the level 2 and level 3 arguments (ratio and starting value) are integers.
This is not a big deal, as the GoferLists command Iterate provides this functionality.

Thanks again,
John

[DavidM]

(02-06-2018 09:04 PM)John Keith Wrote:  1). Reverse the order of the level 1 and level 2 arguments (index and object to be inserted) of LINSR. This would make it consistent with built-in commands such as REPL, as well as INSERT on the Prime.

That's a good point, John. And it is in keeping with the spirit of some of the other commands which have been set up to expect similar arguments (and output) to built-in commands.

@Gilles: this one was really your suggestion. How do you feel about rearranging the arguments as John suggests?

(02-06-2018 09:04 PM)John Keith Wrote:  2). LMSEQ always returns a list of reals, even in exact mode. If it can be done without undue penalties in speed and complexity [my emphasis], I would prefer it return a list of integers in exact mode, as long as the level 2 and level 3 arguments (ratio and starting value) are integers.
This is not a big deal, as the GoferLists command Iterate provides this functionality.

Yeah, I would like that too.

After an initial set of checks for arg types and special cases (mostly 0/1 list size), LASEQ/LMSEQ/LDSEQ all use the same Saturn code engine with a flag that designates which operation to perform with the constant. This was fairly easy to set up due to the existence of add, multiply, and divide Saturn subroutines built into ROM that all expect their arguments as reals and in the same place/format. Doing those same operations with exact integers would be much more problematic (for me anyway) since the only way I know of to safely access the built-in integer math routines is at the SysRPL level. This would definitely mean a sacrifice in performance, and probably bring them more in line with Iterate. So their value vs. the library bloat decreases.

I ran into a similar situation when creating the engine behind LSEQ/LSEQR, but ended up deciding to build the output list from scratch instead of using built-in routines. This was a bit more complex, but still not too bad because in both cases I only needed to add/subtract 1 for each number in the result list. And I still limit the arguments in those routines to +/- 1E12 to keep the implementation fairly straightforward. Refactoring that same method to LMSEQ isn't as easy because the individual output elements can quickly grow beyond register-sized fields.

Bottom line: I'd like to be able to have the intuitive integer results, but the implementation seems like it would be more complex than it may be worth in comparison to simply doing it as a SysRPL code object, which then has questionable value when compared to existing alternatives. I may still play around with this some more, though.

[John Keith]

I was afraid it would not be easy. Also, I had not noticed when I posted that LASEQ also returns reals. This is more problematic for me because there are many number theory problems where a list of odd or even numbers is needed. In those cases I can make do with existing ListExt and GoferLists commands.

OTOH, I will say that LASEQ and LMSEQ are wicked fast!

John

[DavidM]

(02-07-2018 04:59 PM)John Keith Wrote:  OTOH, I will say that LASEQ and LMSEQ are wicked fast!

To be honest, that was the main thing I had in mind when I first thought of those commands. I knew that directly accessing the built-in routines (and building the list in a Saturn loop) would be much faster than a SysRPL implementation, so I thought they might be worthwhile to have.

Another thought I've had is to create my own customized R→I function, which could potentially be faster than the built-in one if used with certain assumptions. As an example, the built-in R→I function on a list of 2000 reals takes almost 14 seconds on my 50g. I'm speculating that I could possibly speed that up if I assume the following (as examples):
- reals are truncated to integers instead of being checked for fractional values
- numbers > some limit (+/-1E12?) are "capped" to a constant (999999999999? ∞? something else?)

While those assumptions wouldn't be good for general purpose computing, they might be acceptable for this kind of situation.

[John Keith]

Truncation sounds fine to me, especially since I\->R requires (real) integers and will error out if given a number with a fractional part.

Capping at 999999999999 would probably be OK. It would be ideal if LMSEQ could return large integers but that would run into the aforementioned speed-and-complexity problem.

Actually, I have always thought of I\->R and R\->I as being reasonably fast. There are, however, several commands that are very slow for exact integers. Comparison operators ( <, >, ==, etc.), and MOD are much slower for exact integers than for reals. IDIV2, IQUOT, and IREMAINDER, which are CAS functions are even slower. The Prime versions of those 3 functions are also slow, and I expect that is because they are complicated programs that also work on symbolics, rationals, etc.
If someone could come up with faster, simpler versions of those commands, it would give a HUGE speed boost to many number theory programs.

Sorry to go off-topic but I have been frustrated lately by slow integer commands and I was reminded of the problem by the discussion of reals vs. integers.

John

[DavidM]

(02-07-2018 09:10 PM)John Keith Wrote:  Capping at 999999999999 would probably be OK. It would be ideal if LMSEQ could return large integers but that would run into the aforementioned speed-and-complexity problem.

I've got a working version of the library with an altered sequence generator for LASEQ/LMSEQ/LDSEQ. The new engine still does all of its internal operations with reals so that I can keep it in the Saturn code realm (to optimize performance). In the case where both the first element and the "change value" arguments are exact integers for LASEQ and LMSEQ, the engine will convert individual real results into an exact integer before storing in the result list. LDSEQ always has real values in its result.

Examples:

Code:

1. 2. 5 LASEQ => { 1. 3. 5. 7. 9. }
1 2 5 LASEQ => { 1 3 5 7 9 }

Code:

1. 2. 10 LMSEQ => { 1. 2. 4. 8. 16. 32. 64. 128. 256. 512. }
1 2 10 LMSEQ => { 1 2 4 8 16 32 64 128 256 512 }

Intermediate real values greater than +/-999999999999.0 are "capped" at +/-999999999999 during this conversion process. This means that LMSEQ's usefulness for integers is limited to small result lists, as geometric progressions with integer factors hit the cap very quickly. LASEQ is more likely to be useful with integers, however, since arithmetic progressions won't run into the cap as easily. If either argument is real, the result list will contain all real values.

So why bother? Well, the impetus for creating those commands in the ListExt library was performance. Here's some examples of similar GoferLists/ListExt commands that provide the same results:

Code:

1 « 2 + » 2000 Iterate

Time: 6.208s

Code:

1 2 2000 LASEQ

Time: 0.706s

Code:

1. « 2. + » 2000. Iterate

Time: 4.636s

Code:

1. 2. 2000. LASEQ

Time: 0.443s

Code:

1 « 2 * » 30 Iterate

Time: 0.211s

Code:

1 2 30 LMSEQ

Time: 0.068s

Code:

1. « 2. * » 30. Iterate

Time: 0.153s

Code:

1. 2. 30. LMSEQ

Time: 0.063s

I need to do some further testing with this before releasing another beta. But the preliminary results make it appear to be a good alternative to the previous version.

[John Keith]

Looks good! Too bad LMSEQ can't work with large integers but I understand the reasoning behind the issue. Besides, using LSEQ / LASEQ with Iterate or Scanl1 is fast enough for most purposes.

John

[DavidM]

(02-14-2018 06:14 PM)John Keith Wrote:  Looks good! Too bad LMSEQ can't work with large integers but I understand the reasoning behind the issue. Besides, using LSEQ / LASEQ with Iterate or Scanl1 is fast enough for most purposes.

John

The first post in this thread has been updated with the 1.1.3b2 release.

The LASEQ/LMSEQ/LDSEQ commands all now provide reasonable results with the complete range of approximate numbers and exact integers. When needed, the sequence generators fall back to a SysRPL loop for processing exact integers that are larger than can be computed with approximate numbers. This method is slower than processing reals, but still faster than using Iterate to achieve the same outcome. It seemed reasonable to include that functionality due to the performance boost.

I also went ahead and changed the order of arguments for LINSR as John Keith suggested. If anyone has a reason not to leave it that way, please let me know!

[DavidM]

Version 1.1.3b3 has now been added to the first post in this thread. Several updates have occurred, most notably a couple of new commands and an important bug fix that addresses a potentially nasty crash that will definitely cause loss of data if you run into it. More on that below. First, the new commands: I→BL and BL→I. Although the most obvious use of these is in doing base conversions, they are also quite useful in other contexts. Especially when combined with some of the other ListExt commands:

______________________________________________________________________________

I→BL (Integer to Base List)

Input
2: number
1: base (number)

Output
1: { sequence of remainders }

Converts the number given in stack level 2 into a reverse-order sequence of remainders after division by the base given in stack level 1). The base will be rounded to an integer before evaluation, and the result after rounding must be greater than 1. The source argument in stack level 2 must be greater than or equal to 0.

Examples:
15 2 I→BL => { 1 1 1 1 }
1234. 16. I→BL => { 4. 13. 2. }
12345678901234567890 64. I→BL => { 10 45 20 42 24 51 43 7 48 43 18 }
342391 8 I→BL NL→I => 1234567
11806310474565 16 I→BL NL→S { 0 9 48 } CHR+ { 10 15 55 } CHR+ => "ABCDEF12345"
12345678901234567890 92 I→BL NL→S 35 CHR+ => "=0TW&V[UFA"


______________________________________________________________________________

BL→I (Base List to Integer)

Input
2: { sequence of remainders }
1: base (number)

Output
1: integer

Performs repeated multiplication by the base in stack level 1 and addition of remainders in the argument given as a list in stack level 2. This is the reverse of the operation performed by I→BL. All numbers in the remainder list are rounded to the nearest integer before evaluation, and the result of that rounding must be in the range 0..<base-1>. The final result is always an exact integer, regardless of the type of the remainder values. The rounded base number must be greater than 1. An empty list as the source argument in stack level 2 will generate a value of 0 for the result.

Examples:
{ 1 1 1 1 } 2 BL→I => 15
{ 4. 13. 2. } 16. BL→I => 1234
{ 10 45 20 42 24 51 43 7 48 43 18 } 64. BL→I => 12345678901234567890
{ } 16 BL→I => 0
1234567 I→NL 8 BL→I=> 342391
"ABCDEF12345" { 48 57 -48 } CHR+ { 65 70 -55 } CHR+ S→NL 16 BL→I => 11806310474565
"=0TW&V[UFA" -35 CHR+ S→NL 92 BL→I => 12345678901234567890

______________________________________________________________________________


Overflow bug in sequence creation commands

Versions 1.1.2 through 1.1.3b2 of the library all have a cringe-worthy bug that can wipe out the contents of your calculator. I'm not aware of anyone having run into it yet (besides me in testing ), but it can come up when passing arguments to the commands that would attempt to create much larger lists than would normally fit in the available memory of your calculator. Element counts greater than approximately 45589 (varies slightly by command) will trigger an undetected overflow which will cause the commands to blithely wipe out memory addresses well beyond their limits. Please just take my word for it and don't try this on your own unless you simply want to reset your calculator for some reason. It will crash, and data loss will occur on those versions. The 1.1.3b3 release no longer has this issue.

Other changes

A couple other minor changes were put in place, including the ListExt menu now being available from the APPS list. See the release notes for more details on those changes.

[pier4r]

awesome new commands and bug fixing

Not yet used the listExt with those large lists... not yet.

[John Keith]

The new I\->BL and BL\->I commands are strange but neat! Were they by chance inspired by Pier's data project in this thread ?

[DavidM]

(03-02-2018 10:02 PM)John Keith Wrote:  The new I\->BL and BL\->I commands are strange but neat! Were they by chance inspired by Pier's data project in this thread ?

I've actually thought about something along those lines ever since putting NL→I in the library. I remember thinking "it sure would be easy to convert to single-digit bases now". The straw that broke the camel's back for me was Pier's post, or more specifically playing around with his data.

There's been several times in work contexts that I've used base transformations for things like serial numbers, coded IDs, and density packing. This just seemed like a nice fit for the list library, even if the uses aren't always intuitively obvious.

[John Keith]

There are number theory uses as well. I\->BL works like the Mathematica command IntegerDigits, which is very useful. I just used I\->BL in a "slow and dirty" program for A000966 based on the first Mathematica program in the linked article.

Edit: shorter and faster thanks to the 2nd formula in A027868

Code:


\<< LSEQ 1.
   \<<  DUP 5 I\->BL LSUM - 4 / 
   \>> DOLIST LGRP DUP 0 SWAP Last LSEQR SWAP Diff
\>>

Given an integer N as input, this program returns a list of all the missing numbers up to N!. For an input of 1000, it returns a list of the first 49 terms in 53s (approx. mode) or 72s (exact mode). Requires both ListExt and GoferLists.

[pier4r]

(03-02-2018 10:02 PM)John Keith Wrote:  are strange but neat

I would say their use may appear not of common use, but they could be very useful (IIRC there is also a processing list challenge that they can help to solve).

Also this let me think that I may push for a collective library of userRPL commands (alongside with hpcalc.org , the general software library and so), in particular commands that people found useful there and there. I'll open a topic shortly.

[DavidM]

(03-03-2018 02:07 PM)John Keith Wrote:  

Code:


\<< LSEQ 1.
   \<<  DUP 5 I\->BL LSUM - 4 / 
   \>> DOLIST LGRP DUP 0 SWAP Last LSEQR SWAP Diff
\>>

Neat indeed, John! Nice to see these ListExt/GL commands being put to good use.