# 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

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):
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("\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). Jun 26, 2020 at 12:11

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, 2020 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$$.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 20, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://crypto.stackexchange.com/questions/81546/whats-the-name-of-this-random-number-generation-algorithm", "fetch_time": 1716734516000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2024-22/segments/1715971058956.26/warc/CC-MAIN-20240526135546-20240526165546-00240.warc.gz", "warc_record_offset": 156057122, "warc_record_length": 41648, "token_count": 1009, "char_count": 3779, "score": 3.578125, "int_score": 4, "crawl": "CC-MAIN-2024-22", "snapshot_type": "latest", "language": "en", "language_score": 0.8167414665222168, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00031-of-00064.parquet"}