List Commands Library for 50g
01-07-2018, 07:30 PM
Post: #241
 John Keith Senior Member Posts: 492 Joined: Dec 2013
RE: List Commands Library for 50g
(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
02-03-2018, 08:55 PM
Post: #242
 DavidM Senior Member Posts: 757 Joined: Dec 2013
RE: List Commands Library for 50g
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!
02-03-2018, 10:59 PM
Post: #243
 brickviking Senior Member Posts: 332 Joined: Dec 2014
RE: List Commands Library for 50g
Attached? Where? Apologies if I've missed it. That new LST-INSRT could be pretty useful.

(Post 166)

Regards, BrickViking
HP-50g |Casio fx-9750G+ |Casio fx-9750GII (SH4a)
02-03-2018, 11:03 PM
Post: #244
 DavidM Senior Member Posts: 757 Joined: Dec 2013
RE: List Commands Library for 50g
(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
02-05-2018, 12:55 PM
Post: #245
 pier4r Senior Member Posts: 2,019 Joined: Nov 2014
RE: List Commands Library for 50g
awesome DavidM.

Wikis are great, Contribute :)
02-06-2018, 09:04 PM
Post: #246
 John Keith Senior Member Posts: 492 Joined: Dec 2013
RE: List Commands Library for 50g
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
02-07-2018, 06:47 AM
Post: #247
 DavidM Senior Member Posts: 757 Joined: Dec 2013
RE: List Commands Library for 50g
(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.
02-07-2018, 04:59 PM
Post: #248
 John Keith Senior Member Posts: 492 Joined: Dec 2013
RE: List Commands Library for 50g
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
02-07-2018, 06:24 PM
Post: #249
 DavidM Senior Member Posts: 757 Joined: Dec 2013
RE: List Commands Library for 50g
(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.
02-07-2018, 09:10 PM
Post: #250
 John Keith Senior Member Posts: 492 Joined: Dec 2013
RE: List Commands Library for 50g
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
02-14-2018, 01:47 AM
Post: #251
 DavidM Senior Member Posts: 757 Joined: Dec 2013
RE: List Commands Library for 50g
(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.
02-14-2018, 06:14 PM
Post: #252
 John Keith Senior Member Posts: 492 Joined: Dec 2013
RE: List Commands Library for 50g
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
02-19-2018, 05:25 PM
Post: #253
 DavidM Senior Member Posts: 757 Joined: Dec 2013
RE: List Commands Library for 50g
(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!
03-01-2018, 02:33 AM
Post: #254
 DavidM Senior Member Posts: 757 Joined: Dec 2013
RE: List Commands Library for 50g
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.
03-01-2018, 01:58 PM (This post was last modified: 03-03-2018 08:58 AM by pier4r.)
Post: #255
 pier4r Senior Member Posts: 2,019 Joined: Nov 2014
RE: List Commands Library for 50g
awesome new commands and bug fixing

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

Wikis are great, Contribute :)
03-02-2018, 10:02 PM
Post: #256
 John Keith Senior Member Posts: 492 Joined: Dec 2013
RE: List Commands Library for 50g
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 ?
03-02-2018, 10:28 PM
Post: #257
 DavidM Senior Member Posts: 757 Joined: Dec 2013
RE: List Commands Library for 50g
(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.
03-03-2018, 02:07 PM (This post was last modified: 03-03-2018 06:12 PM by John Keith.)
Post: #258
 John Keith Senior Member Posts: 492 Joined: Dec 2013
RE: List Commands Library for 50g
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.
03-03-2018, 02:13 PM (This post was last modified: 03-03-2018 02:14 PM by pier4r.)
Post: #259
 pier4r Senior Member Posts: 2,019 Joined: Nov 2014
RE: List Commands Library for 50g
(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.

Wikis are great, Contribute :)
03-03-2018, 08:22 PM
Post: #260
 DavidM Senior Member Posts: 757 Joined: Dec 2013
RE: List Commands Library for 50g
(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.
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)