4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Occams_Trimmer Jun 26 at 12:11
2
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ @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. $\endgroup$ – fgrieu Jun 28 at 8:55
2
$\begingroup$

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

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.