Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tree: bf7ab27d47
Fetching contributors…

Cannot retrieve contributors at this time

141 lines (118 sloc) 5.045 kb
"""
Created: 11.1.2012
Version: 0.1
Author: Dolkar
License: None
Cryptografically safe pseudo-random generator using os.urandom.
Standard random module already has one such generator, SystemRandom, which is
pretty inefficient because of large os.urandom overhead. This one minimizes
the loss by loading random data in large chunks (10KiB by default). It also uses
struct for unpacking the raw binary randomness, which is faster than
binascii.hexlify.
Run the file for speed comparisons. If you find anything that can be implemented
more efficiently... let me know.
"""
import random as _random
from os import urandom as _urandom
from binascii import hexlify as _hexlify
from struct import unpack_from as _unpack_from
BPF = 53 # Number of bits in a float
FLOAT_CONV_CONSTANT = 2 ** -(BPF + 11) # For 8-byte int to [0, 1) float range
_CACHE_SIZE = 10240
__all__ = ["CachedSystemRandom", "random", "uniform", "randint", "choice",
"sample", "randrange", "shuffle", "normalvariate", "lognormvariate",
"expovariate", "vonmisesvariate", "gammavariate", "triangular",
"betavariate", "paretovariate", "weibullvariate", "getrandbits"]
class CachedSystemRandom(_random.Random):
def __init__(self, cache_size = _CACHE_SIZE):
"""
CachedSystemRandom(cache_size = 10240): Creates a random number
generator with given cache size in bytes.
"""
self._source = _urandom
self._cache_size = cache_size
self.refresh()
def getrandbits(self, k):
"""
getrandbits(k) -> x. Generates a long int with k random bits.
Used for covering very large ranges"""
if k <= 0:
raise ValueError('number of bits must be greater than zero')
if k != int(k):
raise TypeError('number of bits should be an integer')
bytes = (k + 7) // 8 # bits / 8 and rounded up
data = self._cache[self._pos:self._pos + bytes]
bytes_left = self._cache_size - self._pos
if bytes >= bytes_left:
if bytes > self._cache_size:
data = ''.join((data, self._source(bytes - bytes_left)))
self.refresh()
else:
self.refresh()
self._pos = bytes - bytes_left
data = ''.join((data, self._cache[:self._pos]))
else:
self._pos += bytes
return long(_hexlify(data), 16) >> (bytes * 8 - k) # trim excess bits
def refresh(self):
"""Drops all current catched data and fetches some new."""
# 8 extra bytes to ensure enough space for a random call
self._cache = self._source(self._cache_size + 8)
self._pos = 0
def random(self):
"""Get the next random number in the range [0.0, 1.0)."""
value = _unpack_from('Q', self._cache, self._pos)[0] * FLOAT_CONV_CONSTANT
self._pos += 8
if self._pos >= self._cache_size:
self.refresh()
return value
def _stub(self, *args, **kwds):
"Stub method. Not used for a system random number generator."
return None
seed = jumpahead = _stub
def _notimplemented(self, *args, **kwds):
"Method should not be called for a system random number generator."
raise NotImplementedError('System entropy source does not have state.')
getstate = setstate = _notimplemented
_inst = CachedSystemRandom()
random = _inst.random
uniform = _inst.uniform
triangular = _inst.triangular
randint = _inst.randint
choice = _inst.choice
randrange = _inst.randrange
sample = _inst.sample
shuffle = _inst.shuffle
normalvariate = _inst.normalvariate
lognormvariate = _inst.lognormvariate
expovariate = _inst.expovariate
vonmisesvariate = _inst.vonmisesvariate
gammavariate = _inst.gammavariate
betavariate = _inst.betavariate
paretovariate = _inst.paretovariate
weibullvariate = _inst.weibullvariate
getrandbits = _inst.getrandbits
if __name__ == '__main__':
from timeit import timeit
R = _random.Random()
SR = _random.SystemRandom()
CSR = CachedSystemRandom()
setup = 'from __main__ import CSR, SR, R'
def testMethod(name, number):
a = timeit('R.%s' % name, setup, number = number) * 1000
b = timeit('SR.%s' % name, setup, number = number) * 1000
c = timeit('CSR.%s' % name, setup, number = number) * 1000
print "%25s %8.3f ms %12.3f ms %14.3f ms" % (name, a, b, c)
print " call Random SystemRandom C.SystemRandom"
print
testMethod('random()', 100000)
testMethod('randrange(100000)', 10000)
testMethod('randrange(2**100)', 10000)
testMethod('uniform(0, 2**100)', 10000)
testMethod('choice(range(1000))', 10000)
testMethod('shuffle(range(1000))', 100)
testMethod('gammavariate(1.0,1.0)', 10000)
print
testMethod('getrandbits(2)', 100000)
testMethod('getrandbits(2**10)', 10000)
testMethod('getrandbits(2**20)', 100)
Jump to Line
Something went wrong with that request. Please try again.