Randomize a List problem

[DavidM]

(10-13-2020 07:13 PM)pier4r Wrote:  ...This because I was making a solver of a little game, where numbers and operators needed to be combined to get a certain number. The search was random and sometimes it took extremely long. Checking the frequencies, there were some permutations that were very rare or some elements weren't shuffled at all. At the moment I do not remember exactly were the discussion was.

I recall that you discovered a problem in an earlier version of the LSHUF command that resulted from its use of the SplitMix64 algorithm for shuffling. I'm pretty sure the issue resulted from the trailing low-order bits of the SplitMix64 result having a cycle of some sort. Since most implementations convert the result into a real number by dividing it by 2^64, the influence of those bits is very low in common use. In the case of LSHUF, the SplitMix64 result is instead treated as an integer for a MOD operation. Those last bits were creating a very noticeable bias and the fix was simply to discard the last 4 bits by shifting the 60 high-order bits to the right.

There's probably something in that very long thread about it. Or perhaps in an email discussion? I no longer remember where the discussion took place. Nor did a quick search find any mention of SplitMix64 having this issue, so my memory could be totally wrong. But I did make a specific change to the LSHUF code to shift out the last 4 bits of the SplitMix64 output, and I wouldn't have done that arbitrarily. Wish I had put the specific reason in the comments.