Welcome, guest | Sign In | My Account | Store | Cart

This is a pseudo-random number generator test.

(There are many known tests for pseudo-random generators but I came up w/ this one on my own. I don't know if it is an already known method or not.)

Idea is this: Imagine if you generate a 1000-bit binary number using any PRNG (as 1-bit at a time) what is the probability that all bits will be 0 in the number?

If you had a true number generator then there is a real probability (=1/(2**1000)) but if you use a PRNG then I would say the probability is really 0!

If you had generated 2**1000 1000-bit numbers using a hypothetical True-Random Number Generator, assuming perfectly uniform probability distribution, then TRNG would generate 1 number that contains 1000 zeros. That is C(1000, 1000) = 1

Assuming perfectly uniform probability distribution, C(n,k) gives you how many n-digit binary numbers would contain k zeros.

This code generates 2**n n-bit binary numbers (one bit at a time) using the given PRNG and compares the actual distribution to the perfect distribution of a hypothetical True-Random Number Generator.

(I used n=20 in the code because the calculation takes too long.)

Python, 65 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65``` ```# PRNG (Pseudo-Random Number Generator) Test # PRNG info: # http://en.wikipedia.org/wiki/Pseudorandom_number_generator # FB - 201012046 # Compares output distribution of any given PRNG # w/ an hypothetical True-Random Number Generator (TRNG) import math import time global x x = time.clock() # seed for the PRNG # PRNG to test def prng(): global x x = math.fmod((x + math.pi) ** 2.0, 1.0) return x # combination by recursive method def c(n, k): if k == 0: return 1 if n == 0: return 0 return c(n - 1, k - 1) + c(n - 1, k) ### combination by multiplicative method ##def c_(n, k): ## mul = 1.0 ## for i in range(k): ## mul = mul * (n - k + i + 1) / (i + 1) ## return mul # MAIN n = 20 # number of bits in each trial print 'Test in progress...' print cnk = [] # array to hold bit counts for k in range(n + 1): cnk.append(0) # generate 2**n n-bit pseudo-random numbers for j in range(2 ** n): # generate n-bit pseudo-random number and count the 0's in it # num = '' ctr = 0 for i in range(n): b = int(round(prng())) # generate 1 pseudo-random bit # num += str(b) if b == 0: ctr += 1 # print num # increase bit count in the array cnk[ctr] += 1 print 'Number of bits in each pseudo-random number (n) =', n print print 'Comparison of "0" count distributions:' print print ' k', ' c(n,k)', ' actual', '%dif' difSum = 0 for k in range(n + 1): cnk_ = c(n, k) dif = abs(cnk_ - cnk[k]) print '%2d %10d %10d %4d' % (k, cnk_, cnk[k], 100 * dif / cnk_) difSum += dif print print 'Difference percentage between the distributions:' print 100 * difSum / (2 ** n) ```

#### 1 comment FB36 (author) 12 years, 6 months ago

My main point is ALL standard types of PRNG algorithms would produce bad results for this type of test. Because none of them actually closely matches to a hypothetical True-Random Number Generator, even the hardware-based "TRNG"'s! Created by FB36 on Sat, 4 Dec 2010 (MIT)

### Required Modules

• (none specified)