A project I'm working on requires generating a random number of \$N\$ length to a very high degree of fair distribution between digits \$[0, 9]\$.
That said, I used the RNGCryptoServiceProvider
in the .NET framework, and built my own window restriction / clamping.
First, we have the clamping. This clamps the values to the range from \$[lower, upper)\$, allowing the user to specify what range of values they want. For me, it's \$[0, 9]\$.
Mathematically speaking, using a cryptographically secure random number generator should yield a truly random set. The problem is clamping: if we simply take val % 10
to reduce it to our desired \$[0, 9]\$ range, we'll find that we have a slight favoritism / bias towards numbers at the lower end of the set. In fact, we should have the most bias towards the set \$[0, 5]\$.
To reduce, or even eliminate, this bias I took a previously working algorithm and modified it slightly to create a bounded number of loops. The idea is simple: to generate a random value in the domain \$[0, 9]\$ take the random value from the set \$[0, 255]\$ and test that it is within the range \$[0, 249]\$. If it is within that range, take \$value \mod 10\$ as the result. If it is in the range \$[250, 255]\$ then we draw a new number. This can be expanded to define the following general-purpose formula:
$$upperLimit = 256 - (256 \mod modulo)$$
We can then define the number to take the modulo by as:
$$modulo = upper - lower$$
We set the loop up to bound to a specific value, in this case I'm creating the loop
So far, my results have yielded almost perfect distribution of the values \$[0, 9]\$, when generating \$1,000,000\$ values.
I have run this several times, and each time I get a slightly different distribution, by a very small margin. That is perfect, as it demonstrates that the RNG is not predictable by any manner.
Value 0: 100090 occurrences (10.009%) Value 1: 100298 occurrences (10.0298%) Value 2: 100034 occurrences (10.0034%) Value 3: 99996 occurrences (9.9996%) Value 4: 100042 occurrences (10.0042%) Value 5: 99912 occurrences (9.9912%) Value 6: 99506 occurrences (9.9506%) Value 7: 99971 occurrences (9.9971%) Value 8: 99801 occurrences (9.9801%) Value 9: 100350 occurrences (10.035%)
The code to clamp values is as follows:
int ModuloLimit(int modulo) => 256 - (256 % modulo);
int ClampDigit(byte[] bytes, int lower, int upper)
{
var result = -1;
var modulo = upper - lower;
var upperLimit = ModuloLimit(modulo);
for (int i = 0; i < bytes.Length; i++)
{
if (bytes[i] < upperLimit)
{
result = bytes[i] % modulo + lower;
}
}
if (result == -1)
{
result = bytes[bytes[0] % bytes.Length] % modulo + lower;
}
return result;
}
Next we have our function which gets a random digit within \$[0, 9]\$ using the RNGCryptoServiceProvider
. It creates a new instance each time, since the RNGCryptoServiceProvider
is supposed to be unpredictable, this should suffice.
int RandomDigit(int tries = 10, int lower = 0, int upper = 10)
{
var bytes = new byte[tries];
using (var csp = new RNGCryptoServiceProvider())
{
csp.GetBytes(bytes);
}
return ClampDigit(bytes, lower, upper);
}
Finally, I have the RandomNumber
method which generates the series of digits with length \$N\$.
string RandomNumber(int numDigits)
{
var sb = new StringBuilder(numDigits);
for (int i = 0; i < numDigits; i++)
{
sb.Append(RandomDigit());
}
return sb.ToString();
}
The only public members would be RandomNumber(int)
and RandomDigit(int, int, int)
.
Finally, I have a TestDistribution
method which I use to test the distribution of our randomly generated values in \$[0, 9]\$.
void TestDistribution(int generatedValues, int upperLimit = 10)
{
var value = generatedValues;
var results = new int[upperLimit];
while (value > 0)
{
value--;
results[RandomDigit(upper: upperLimit)]++;
}
Console.WriteLine("Expect " + Math.Round(100.0 / upperLimit, 2) + "% for each value");
for (int i = 0; i < upperLimit; i++)
{
Console.WriteLine("Value " + i + ": " + results[i] + " occurrences (" + ((double)results[i] / (double)generatedValues * 100) + "%)");
}
}
The distribution has been consistently variant in my testing, and has been predictable within \$[9.93\%, 10.08\%]\$ for \$1,000,000\$ generated numbers.
When testing with \$10,000,000\$ numbers, the distribution consistently falls within \$[9.975\%, 10.025\%]\$, furthering the demonstration that no number is favored consistently. (When testing across multiple runs, the favored and unfavored digits varied entirely.)
Just for comparison, if the entire ClampDigit
method is replaced with a simple return bytes[0] % (upper - lower) + lower;
the result distribution is roughly as follows:
Value 0: 101535 occurrences (10.1535%) Value 1: 101851 occurrences (10.1851%) Value 2: 101675 occurrences (10.1675%) Value 3: 101262 occurrences (10.1262%) Value 4: 101426 occurrences (10.1426%) Value 5: 101295 occurrences (10.1295%) Value 6: 97704 occurrences (9.7704%) Value 7: 97501 occurrences (9.7501%) Value 8: 97988 occurrences (9.7988%) Value 9: 97763 occurrences (9.7763%)
This is entirely consistent for the general distribution: every tested run had digits in the range \$[0, 5]\$ appear more than 10% of the time, and digits \$[6, 9]\$ appeared less than 10% of the time.
When testing the edge case (if the iteration count exceeds tries
value) it was hit 0 times across \$1,000,000\$ runs when tries
was in the interval \$[4, 10]\$. For a tries
value of 3, there were 13 occurrences on average across multiple runs that it was hit, meaning \$0.0013\%\$ of the time. For a tries
value of 2 it was roughly \$0.0521\%\$, a tries
value of 1 was roughly \$2.3223\%\$. (The final value makes complete sense, \$2.34375\%\$ of the values from \$[0, 255]\$ are within the edge case.)
Mathematically speaking, the code should hit the edge case once every
$$\frac 1 {0.0234375^N}$$
Where \$N\$ is the tries
or number of bytes to test before the loop terminates. For a tries
of 1
, that's \$42.\bar6\$, for tries
of 5, that's \$141,398,100.2798\$.