4 ms·
This is very practical, but the result is not uniform; in fact it only returns a tiny fraction of the possible combinations. There are "N choose k" combination
by ridiculous_fish 11y ago
This is very practical, but the result is not uniform; in fact it only returns a tiny fraction of the possible combinations.
There are "N choose k" combinations, which in the worst case (k = N/2) grows as ~ 2^N. The number of combinations quickly outstrips the number of possible states of the LCG, and most combinations will never be found. For example, we have a list of length 16 and wish to choose 8. We have a choice of 16 distinct seeds, so there are only 16 different combinations (out of 12870 possible) that we can get for any given LCG.
- deleted 11y ago[deleted]
- vrfcodf 11y agoGood point. You would get different sequences by choosing different constants for the generator though, but you couldn't cover all of them by a longshot.
- mcherm 11y agoAnd this inability to cover all possible sequences has real-world implications. https://www.cigital.com/papers/download/developer_gambling.php https://www.cigital.com/papers/download/developer_gambling.p... http://superuser.com/questions/712551/how-are-pseudorandom-and-truly-random-numbers-different-and-why-does-it-matter/712583#712583 http://superuser.com/questions/712551/how-are-pseudorandom-a...
- mrdrozdov 11y agoBy randomly adding skips, can definitely get to all possible combinations even with only 16 seeds (since skips can be seeded from a much larger space), although there could be a speed implication.