What's the name of this random number generation algorithm?

Question

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.

Answer 1

The algorithm described is an unbiasing algorithm, which is a type of randomness extraction algorithm.

Another method is von Neumann unbiasing where you can take 2 bits $(X_n,X_{n+1})$ and output $Z=0$ if $(X_n,X_{n+1})=(0,1),$ output $Z=1,$ if $(X_n,X_{n+1})=(1,0),$ and discard the two bits otherwise. This gives exactly uniform output bits, if the sequence $X_n$ is independent and identically distributed since both the above $(0,1),(1,0)$ have probability exactly $p(1-p)$.

Answer 2

good_RNG could be described as: an implementation of an unbiasing (or randomness extraction, or post-processing) algorithm performing the eXclusive-OR of 200 consecutive outputs of bad_RNG, using a loop unrolled by a factor of two, likely with an accidental data-dependent timing dependency beyond that in bad_RNG.

This is because

• when $\mathtt{foo}\in\{0,1\}$ and $\mathtt{bar}\in\{0,1\}$, the expression
  foo != bar
  boils down to $\mathtt{foo}\oplus\mathtt{bar}$ where $\oplus$ is eXclusive-OR aka XOR, possibly with a data timing dependency.
• when $\mathtt{zoo}\in\{0,1\}$ and $\mathtt{result}\in\{0,1\}$, the code
  if (zoo):
result = 1 - result
  boils down to $\mathtt{result}\gets\mathtt{result}\oplus\mathtt{zoo}$, likely with a data timing dependency.
• $\oplus$ is associative.

The lack of comment about these facts would be a punishable offense in professional practice.

---

I doubt there is a specific name for this elementary method. If there is one, it is not given in Markus Dichtl's Bad and Good Ways of Post-Processing Biased Physical Random Numbers, in proceedings of FSE 2007, which states (about good ones):

Probably the simplest method is to XOR $n$ bits from the generator in order to get one bit of output where $n$ is a fixed integer greater than $1$.

That's what good_RNG does for $n=200$.