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) 11 years 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)