I'm using Python for a competition in which I am creating a bot to play a game. The problem is, it does not have anything of c support installed, so I do not have access to the random, numpy, and scipy modules.
I will have roughly 400mb ram available, and I am looking for a way to produce uniform random numbers between 0 and 1 for simulation purposes during the game.
Note that I have used the clock time before to generate a single number, but the issue is that I will need loads of numbers without the clock changing much, which would result in constantly the same number. In fact, I am limited to a maximum of 1 second for, say, 100k numbers.
I'm considering loading in data, but the problem would then be that the bot would always use the same numbers. Then again, the circumstances for which I need to use the numbers vary slightly.
Using Python 2.7, hoping people have some suggestions.
You can use a Mersenne Twister implementation. I found this one, which is modeled after the pseudocode on Wikipedia.
#!/usr/bin/env python2
# -*- coding: utf-8 -*-
"""
Based on the pseudocode in https://en.wikipedia.org/wiki/Mersenne_Twister. Generates uniformly distributed 32-bit integers in the range [0, 232 − 1] with the MT19937 algorithm
Yaşar Arabacı <yasar11732 et gmail nokta com>
"""
# Create a length 624 list to store the state of the generator
MT = [0 for i in xrange(624)]
index = 0
# To get last 32 bits
bitmask_1 = (2 ** 32) - 1
# To get 32. bit
bitmask_2 = 2 ** 31
# To get last 31 bits
bitmask_3 = (2 ** 31) - 1
def initialize_generator(seed):
"Initialize the generator from a seed"
global MT
global bitmask_1
MT[0] = seed
for i in xrange(1,624):
MT[i] = ((1812433253 * MT[i-1]) ^ ((MT[i-1] >> 30) + i)) & bitmask_1
def extract_number():
"""
Extract a tempered pseudorandom number based on the index-th value,
calling generate_numbers() every 624 numbers
"""
global index
global MT
if index == 0:
generate_numbers()
y = MT[index]
y ^= y >> 11
y ^= (y << 7) & 2636928640
y ^= (y << 15) & 4022730752
y ^= y >> 18
index = (index + 1) % 624
return y
def generate_numbers():
"Generate an array of 624 untempered numbers"
global MT
for i in xrange(624):
y = (MT[i] & bitmask_2) + (MT[(i + 1 ) % 624] & bitmask_3)
MT[i] = MT[(i + 397) % 624] ^ (y >> 1)
if y % 2 != 0:
MT[i] ^= 2567483615
if __name__ == "__main__":
from datetime import datetime
now = datetime.now()
initialize_generator(now.microsecond)
for i in xrange(100):
"Print 100 random numbers as an example"
print extract_number()
FWIW, the random module contains the class Wichman-Hill generator written in pure python (no C required):
>>> import random
>>> rng = random.WichmannHill(8675309)
>>> rng.random()
0.06246664612856567
>>> rng.random()
0.3049888099198217
Here's the cleaned-up source code:
class WichmannHill(Random):
def seed(self, a=None):
a, x = divmod(a, 30268)
a, y = divmod(a, 30306)
a, z = divmod(a, 30322)
self._seed = int(x)+1, int(y)+1, int(z)+1
def random(self):
"""Get the next random number in the range [0.0, 1.0)."""
x, y, z = self._seed
x = (171 * x) % 30269
y = (172 * y) % 30307
z = (170 * z) % 30323
self._seed = x, y, z
return (x/30269.0 + y/30307.0 + z/30323.0) % 1.0
If the script is ran on linux, try using /dev/urandom:
with open('/dev/urandom', 'rb') as f:
random_int = reduce(lambda acc, x: (acc << 8) | x, map(ord, f.read(4)), 0)
f.read(4) reads 4 bytes of entrophymap(ord, f.read(4)) - converts byte-strings into numbersreduce(lambda ..., map(...), 0) - converts the list of numbers into an integer
Maths is your best answer: http://en.m.wikipedia.org/wiki/Linear_congruential_generator
X(n+1) = (aX(n)+c) mod m
x2 = (a*x1+c)%m
