List Commands Library for 50g

[DavidM]

Version 1.1.3b5 is now available in the first post of this thread. There were a few commands added (they have already been discussed in prior messages in this thread), but the biggest change was an overhaul for the randomizing method of LSHUF. My goal was to fix the bias that was found in the previous version, with a quality that is comparable to using a Fisher-Yates shuffle that swaps elements targeted with a "<remaining elements> RAND * CEIL" approach.

Here's the updated command description for LSHUF:

______________________________________________________________________________

LSHUF (List Shuffle)

Input
1: { list of 0 or more objects }

Output
1: { same objects as input, in different order }

Randomizes the order of the elements in the list given as input.

Note: In the examples below, RDZ is used so that the results can be verified. Setting the random seed prior to executing LSHUF is not normally required.

Example:
123456789012. RDZ { 1 2 3 4 5 6 7 8 9 10 } LSHUF => { 7 10 6 2 1 8 3 5 4 9 }
246813579034. RDZ { 1 2 3 4 5 6 7 8 9 10 } LSHUF => { 8 1 4 9 7 2 10 6 5 3 }
135790246865. RDZ { 1 2 3 4 5 6 7 8 9 10 } LSHUF => { 6 8 5 4 3 1 10 2 7 9 }


Technical information about the method LSHUF uses to randomize lists:

Generally speaking, LSHUF explodes the given list, randomizes the resulting stack contents, then implodes the list with the new order. The explosion/implosion steps are simply the built-in SysRPL versions of those commands, but the randomization happens in a custom Saturn assembly language subroutine. The heart of this Saturn subroutine uses a Fisher-Yates algorithm (the "modern algorithm" described in this article: https://en.wikipedia.org/wiki/Fisher%E2%..._algorithm ). The critical part of this method is in selecting a pseudo-random swap target from the available pool of remaining list elements. LSHUF makes use of the SplitMix64 PRNG for this purpose, which is initially seeded by converting the system's default RAND seed to hex notation and performing an initial SplitMix64 cycle. Each iteration of the Fisher-Yates loop generates a new seed which is then shifted right by 4 bits, range-checked for validity (see https://en.wikipedia.org/wiki/Fisher%E2%...odulo_bias ), then reduced to a specific swap target within the current list elements with a simple MOD operation.

LSHUF results have been compared with a similar (but much slower) loop that uses a "<pool size> RAND * CEIL" algorithm for selecting the swap target. Specific tests were performed to check for distribution (using Chi-squared analysis) and Kendall-Tau distance for positional change. LSHUF performed slightly better than "RAND * CEIL" in the distribution tests (250000 samples) and equally in the positional change tests (3000 samples). Additionally, LSHUF was tested using a simple target-matching sequence to see if there were any measurable differences between the two methods for the frequency of random targets being found (2000 samples). No meaningful differences were found.