List Commands Library for 50g

[pier4r]

(03-18-2018 04:45 PM)DavidM Wrote:  I've been experimenting with an alternative way to use the RAND seed, and a 20-simulation run that just completed gave the following results:

:AttempsRAND: { 4096. 800. 872. 1280. 2209. 116. 4096. 678. 1978. 4096. 3343. 798. 4096. 4096. 1372. 2945. 4096. 456. 335. 4096. }
:AttempsLSHUF: { 1625. 4096. 1756. 1525. 3452. 2842. 1662. 2474. 1800. 3436. 4096. 3265. 4096. 3699. 4096. 803. 4096. 930. 1481. 4096. }

A previous 10-simulation test (using the same method) gave these results:

:AttempsRAND: { 1748. 4096. 1751. 785. 754. 1933. 1816. 4096. 4096. 4096. }
:AttempsLSHUF: { 3846. 4096. 181. 197. 712. 1484. 33. 727. 864. 796. }

So doing some base stats (that one can use to get a glipse of things, although the result could be biased or meaningless sometimes)

2367.5 RAND avg
2275.4 LSHUF avg

1480 RAND std
1433 LSHUF std

71025 RAND sum
68262 LSHUF sum

233882079 RAND sum^2
216940694 LSHUF sum^2
(sum^2 together with sum is especially neat to see how much the sum distributed itself in "big numbers". One can have a smaller sum than another but a bigger sum^2, for example)

I'd say that - although the stats above are not rigorous - it is better than before.

Quote:I'm not sure what you're referring to in terms of "search" here, at least in terms of how that applies to the program you posted. It seems to me that the program isn't performing a search in the usual context, but rather is simply constructing random permutations of a list and counting how many permutations are tried before a match occurs. The program does nothing to sequence the permutations, so it could be generating duplicates as it progresses.

Ah sorry. I slightly extended the topic. The program that we are using for testing compares a list built with LSHUF or RAND vs a specific goal. This is a test but it can be seen also a "search the goal list". A random search of the goal list (with RAND or the new LSHUF) would need on average X attemps (considering the cutoff limit). See 2367 or 2275 above.
A sequential search (build all the possible lists, and go through the list of all the possible lists) may need more or less attempts.
This spawned the question. Given a goal list, that is "unknown" to the generator program, aside from its elements. Given that one cannot say anything about the elements (so one cannot apply a binary search, or order the elements in a tree, and so on). Which type of search could be better - on average - than backtracking/going through all the possible combinations of elements? That was the topic of my little digression.

Quote:Yes, I continue to learn how little I understand PRNGs and how to measure their effectiveness. But I'm glad you pointed out your observations, because I wouldn't have known there was an issue otherwise.

Indeed, it is like we discover a marginal bug that happens in certain cases that were not used until now. It happens.

Quote:I keep feeling like there must be a way to test the efficacy of the shuffle compared to the "<num> RAND IP 1 +" alternative without porting everything to a different platform and investing huge amounts of time and effort to fine-tune the tests.

Here I cannot follow. Why should you test the things on another platform? For the efficacy, you need to find (or develop) a reasonable metric for the context.

I, for starters, look at the basic things first, listed above. They are not "final" indicators, but they give an idea within the context of the test. Those indicators may fail with another type of test. I do not know if there exists a "quite comprehensive test and related metric" that would rule out problems in most of the possible applications. If someone knows it, please let us know!