List Commands Library for 50g

04132018, 05:20 PM
Post: #332




RE: List Commands Library for 50g
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 FisherYates 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 builtin SysRPL versions of those commands, but the randomization happens in a custom Saturn assembly language subroutine. The heart of this Saturn subroutine uses a FisherYates 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 pseudorandom 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 FisherYates loop generates a new seed which is then shifted right by 4 bits, rangechecked 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 Chisquared analysis) and KendallTau 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 targetmatching 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. 

« Next Oldest  Next Newest »

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