??? 10/29/09 13:33 Read: times |
#170181 - Watch out for distribution problems for small ranges Responding to: ???'s previous message |
One issue with having a random number generator that produces values between 0 to 255 is that you get a broken distribution if you need values of a smaller range, and makes use of modulo.
The following shows the number of matches from modulo 2 and up to modulo 25. 2: 128 128 3: 86 85 85 4: 64 64 64 64 5: 52 51 51 51 51 6: 43 43 43 43 42 42 7: 37 37 37 37 36 36 36 8: 32 32 32 32 32 32 32 32 9: 29 29 29 29 28 28 28 28 28 10: 26 26 26 26 26 26 25 25 25 25 11: 24 24 24 23 23 23 23 23 23 23 23 12: 22 22 22 22 21 21 21 21 21 21 21 21 13: 20 20 20 20 20 20 20 20 20 19 19 19 19 14: 19 19 19 19 18 18 18 18 18 18 18 18 18 18 15: 18 17 17 17 17 17 17 17 17 17 17 17 17 17 17 16: 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 17: 16 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 18: 15 15 15 15 14 14 14 14 14 14 14 14 14 14 14 14 14 14 19: 14 14 14 14 14 14 14 14 14 13 13 13 13 13 13 13 13 13 13 20: 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 12 12 12 12 21: 13 13 13 13 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 22: 12 12 12 12 12 12 12 12 12 12 12 12 12 12 11 11 11 11 11 11 11 11 23: 12 12 12 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 24: 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 10 10 10 10 10 10 10 10 25: 11 11 11 11 11 11 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 Simulating a 6-sided dice, there would be a 2.4% greater chance to get 1, 2, 3 or 4 in relation to 5 or 6. Simulating a 20-sided dice, there would be a 10% greater chance to get 1..16 compared to 17..20. So pseudo-random or not, the code must make sure that the max range of the random generator works well for the specific requirements, or perform a correction. In the example of a 6-sided dice with a random number generator that produces values 0..255, the values 252 to 255 should be ignored. The problem is the same when using the timer directly. Having a larger range for the generator will just reduce the percentage error in distribution. |