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) 13 years, 4 months ago  # | flag

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)
Python recipes (4591)
FB36's recipes (148)

Required Modules

  • (none specified)

Other Information and Tasks