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

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.

• I feel "randomness extraction" is a more suitable name for what's being done here (i.e., convert a distribution that is not uniform into uniform). – Occams_Trimmer Jun 26 '20 at 12:11

## 2 Answers

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)$$.

• @bey: good_RNG does NOT implement von Neumann's debiasing method. Von Neumann's would take pairs of outputs of bad_RNG, loop until the values in a pair are different, and return the first in the pair. – fgrieu Jun 28 '20 at 8:55

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$$.