A Random Question
06-11-2017, 12:21 AM
Post: #15
 ttw Member Posts: 273 Joined: Jun 2014
RE: A Random Question
One way to improve problems with pRNGs is to use very long cycle with a large state. The Fischer-Yates shuffle has the additional problem in that one needs to sample from various values of n. If shuffling a deck of cards, the first choice needs to sample from 51 items then from 50 items then from 49, 48,...3,2 items. There are four obvious choices.

First, one could use a big integer generator (Lehmer, shift-register, Fibonacci, etc.) which has a cycle length divisible by LCM(2*3*4*...50*51). This uses lots of big arithmetic.

Second, one could use 51 different RNGs with cycles divisible by a large multiple of the index of the generator. That is, the first is a multiple of a large power of 51, the second divisible by a large power of 50, and the last divisible by a large power of 2. The cycle length of each generator should be a multiple of a large different prime (perhaps 53,59,61,....) to keep each generator (sort of) independent of the others. This is probably the nicest in theory.

Third, one could use a very long cycle generator. The error from lack divisibility does decrease with cycle length. This is probably the most practical solution.

Fourth, one could use a simple RNG and not worry about the error. This I probably the most common solution.
 « Next Oldest | Next Newest »

 Messages In This Thread A Random Question - DavidM - 06-09-2017, 03:15 PM RE: A Random Question - pier4r - 06-09-2017, 03:46 PM RE: A Random Question - Paul Dale - 06-09-2017, 11:37 PM RE: A Random Question - Joe Horn - 06-10-2017, 12:03 AM RE: A Random Question - DavidM - 06-10-2017, 01:45 AM RE: A Random Question - pier4r - 06-10-2017, 08:55 AM RE: A Random Question - DavidM - 06-10-2017, 05:10 PM RE: A Random Question - Paul Dale - 06-10-2017, 05:18 AM RE: A Random Question - John Keith - 06-10-2017, 12:57 PM RE: A Random Question - pier4r - 06-10-2017, 01:20 PM RE: A Random Question - DavidM - 06-10-2017, 03:51 PM RE: A Random Question - Paul Dale - 06-10-2017, 11:49 PM RE: A Random Question - DavidM - 06-11-2017, 01:11 AM RE: A Random Question - Paul Dale - 06-11-2017, 05:04 AM RE: A Random Question - lrdheat - 06-10-2017, 02:28 PM RE: A Random Question - Paul Dale - 06-11-2017, 12:00 AM RE: A Random Question - ttw - 06-11-2017 12:21 AM RE: A Random Question - DavidM - 06-11-2017, 01:39 AM RE: A Random Question - Paul Dale - 06-11-2017, 05:19 AM RE: A Random Question - ttw - 06-13-2017, 06:13 AM RE: A Random Question - Paul Dale - 06-11-2017, 12:38 AM