I'm looking for the name of an RNG method or algorithm, described below. Combining multiple results of a non-uniform random number generator can produce a more uniform result. It seems like this would be a common method employed by RNG algorithms, and especially HRNGs, to produce more statistically random results.
It would be awesome if someone could help identify the math/stat/crypto name for this method
The code below demonstrates a simple implementation of this method, with the 'bad' RNG producing non-uniform results, and the 'good' RNG producing about 50/50 results.
import random # Function representing a non-uniform random number generator def bad_RNG(): result = 0 if (random.random() > .99): result = 1 return result # Function that repeatedly applies an RNG function to create a more uniform result def good_RNG(): result = 0 for i in range(100): if (bad_RNG() != bad_RNG()): result = 1 - result return result # Tests RNG functions by running them 100 times, and printing the distribution of their results def test_RNG(RNG_func): zeros = 0 ones = 0 for i in range(100): result = RNG_func() if (0 == result): zeros = zeros + 1 else: ones = ones + 1 print(zeros, end="|") print(ones) print("bad_RNG result:") test_RNG(bad_RNG) print("\ngood_RNG result:") test_RNG(good_RNG)
Alternative English Explanation
Assume an RNG function F() that returns either 0 or 1. F() results are non-uniform, as it usually returns a 0. By summing several F() results, and applying modulus 2, the result approaches a 50/50 uniform distribution.