Pseudo Random Number Generator

Question

I recently watched this video about the random number generation in Super Mario World. The technique that is used, as seen in the image below, multiplies one of the seeds by 5 and adds 1, the other seed is multiplied by 2, and then depending on whether the 4th and 7th bits are the same, 1 is added. So as stated in the video, the sequence of numbers will repeat after 27776 successive calls.

In my implementation of a pseudo random number generator, I have used 16 bit values for the two seeds to allow for a greater range of numbers, and my get_rand() function returns the two 16 bit strings joined together, resulting in a 32 bit number. This means that the sequence of numbers repeats after 526838144 successive calls, which is far greater than that achieved with the pseudo random number generator used in Super Mario World.

I have also created a rand_int() and a random() function that allow for better use of the numbers generated, these simply divide the number returned by 2 ** 32 over the difference between the integer range.

The PRNG Test.py is there only so that I can make sure that all the functions work as expected, and it seems to provide evenly split pseudo random numbers. So I am just after a review of the PRNG.py file, as it is that which I would like to optimize and improve.

PRNG.py

#Make sure Seeds.txt exists
try:
    file = open('Seeds.txt')
except FileNotFoundError:
    file = open('Seeds.txt', 'a+')
    file.write('0\n0')

#Gets the values of the seeds from the file
values = file.readlines()
file.close()

S = int(values[0].rstrip('\n'))
T = int(values[1])

def seed(seed_value):
    '''Resets the seed for the PRNG to make values predictable'''
    global S, T

    with open('Seeds.txt', 'w') as file:
        file.write(str(seed) + '\n' + str(seed))
        file.close()

    S = seed
    T = seed

def update_seeds(S, T):
    '''Generates the next two seeds'''
    S = 5 * S + 1

    try: bit_11 = '{0:b}'.format(T)[-11]
    except IndexError: bit_11 = '0'

    try: bit_16 = '{0:b}'.format(T)[-16]
    except IndexError: bit_16 = '0'

    if bit_11 == bit_16: T = 2 * T + 1
    else:                T = 2 * T

    return S, T


def get_rand(): #Has 526838144 Possible numbers
    '''Produces a random number in the range 0 to 2 ** 32'''
    global S, T

    S, T = update_seeds(S, T)
    S = int('{0:b}'.format(S)[-16:], 2)
    T = int('{0:b}'.format(T)[-16:], 2)
    K = '{0:b}'.format(S ^ T)

    S, T = update_seeds(S, T)
    S = int('{0:b}'.format(S)[-16:], 2)
    T = int('{0:b}'.format(T)[-16:], 2)
    J = '{0:b}'.format(S ^ T)

    with open('Seeds.txt', 'w') as file:
        file.write(str(S) + '\n' + str(T))
        file.close()

    for i in range(16 - len(K)): K = '0' + K
    for i in range(16 - len(J)): J = '0' + J

    return int(K + J, 2)

def rand_int(a, b):
    '''Produces in a random integer in the range a to b'''
    difference = (b + 1) - a
    factor = 2 ** 32 / difference
    return a + int(get_rand() / factor)

def random():
    '''Returns a random float between 0 and 1'''
    return get_rand() / 2 ** 32

PRNG Test.py

import PRNG

l = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for i in range(10000):
    number = PRNG.rand_int(0, 9)
    l[number] += 1

for i in l:
    print(str(round(i / 10000 * 100, 2)) + '% :', i)

Answer 1

At the end I present some bit manipulations stuff, but first of some comments to the style of your script:

• Docstrings usually use the double quote, """A docstrings""" – This is the first time I've seen docstrings using single quotes. PEP-0257 uses double-quotes all over.

• Don't collapse try...except statements – It doesn't look good to collapse these statements. For example this one:

  try: bit_16 = '{0:b}'.format(T)[-16]
  except IndexError: bit_16 = '0'
  

  would read a lot better as:

  try:
      bit_16 = '{0:b}'.format(T)[-16]
  except IndexError:
      bit_16 = '0'
  

• Don't collapse if or for blocks, either – These are even worse to read, so please don't do:

  if bit_11 == bit_16: T = 2 * T + 1
  else:                T = 2 * T
  

  Insert the few extra newlines, and make it readable:

  if bit_11 == bit_16:
      T = 2 * T + 1
  else:               
      T = 2 * T
  

  On second looks, when it is readable, this could actually be rewritten to:

   T = 2 * T + (bit_11 == bit_16)
  

• In seed() you could use str.format() with reusable inputs – Your seed writing could become:

   file.write("{0}\n{0}".format(str(seed)))
  

  Not sure if you even need the str() in there... And a neat trick to get leading zeroes in the bit strings: "{:016b}".format(K).

• Is seed() used, and does it work? – Within this method is used the variable seed, but which variable is that? And is this method used at all, or is replaced by the writing of the file within get_rand()?

• Use with(open...) on the module initialization also – At start of module I would also the with() construct. And there exists proper methods to test whether the file exists.

  And if you insist on trying to open it manually, you could just as well complete the file reading and/or writing within it. Do however be aware of the possibility of the file write to also throw an exception if you're not allowed to write the file or similar errors.

Some basic bit manipulations

• Get the final 16 bits of a number: S & 0xffff
• Set a given bit \$n\$ (zero-based): 1 << (n-1)
• Extract a bit, and move to 0th position: (S >> (n-1)) & 1

Using this knowledge the get_rand() could be rewritten to:

def get_rand():
    global S, T
    S, T = update_seeds(S, T)
    S = S & 0xffff
    T = T & 0xffff
    K = S ^ T

    S, T = update_seeds(S, T)
    S = S & 0xffff
    T = T & 0xffff
    J = S ^ T

    with open('Seeds.txt', 'w') as file:
       file.write("{}\n{}".format(S, T))

    return int("{:016b}{:016b}".format(K, J), 2)

And with an extra helper method, the update_seeds could become:

def extract_bit(value, n):
    """Extract the n'th bit, and move back to 0 position."""

    return (value >> (n-1)) & 1 

def update_seeds(S, T):
    '''Generates the next two seeds'''

    return (5 * S + 1), 
           (2 * T + (extract_bit(T, 11) == extract_bit(T, 16))

Answer 2

• The statement bit_11 = '{0:b}'.format(T)[-11] actually extracts bit 10, because the convention is to number bits from zero, while indexing from the end of string starts at [-1].
• Performing bit manipulations in string format is clunky. Use bitwise operators instead. For example, to extract bit 10: T >> 10 & 1
• Opening a file by a with statement ensures it will be closed. You can omit the close calls.
• Strings have a zfill method that does the same as for i in range(16 - len(K)): K = '0' + K