List Commands Library for 50g
01-07-2018, 07:30 PM
Post: #241
 John Keith Member Posts: 130 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: 504 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 Member Posts: 182 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: 504 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: 1,240 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 Member Posts: 130 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: 504 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 Member Posts: 130 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: 504 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 Member Posts: 130 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: 504 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 Member Posts: 130 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: 504 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!
 « Next Oldest | Next Newest »

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