"""fourmirandom.py --- A random number generator that returns truly
random numbers.

Danny Yoo (dyoo@hkn.eecs.berkeley.edu), with help from the kind folks
at Python-tutor:

    http://mail.python.org/mailman/listinfo/tutor


See the thread started here:

    http://mail.python.org/pipermail/tutor/2002-July/015581.html

for more details on how this got started.


This module should have the same interface as the 'random' module in
the standard library:

    http://www.python.org/doc/lib/module-random.html

Just replace the word "pseudo" with "real".  *grin*


Our source of random bits comes from:

    http://www.fourmilab.ch/cgi-bin/uncgi/Hotbits


We shouldn't abuse this module too much, as Fourmilab does have a
quota on the number of bits one is allows to pull from it."""



## We import these, but put underscores in front of the names, just to
## prevent name confusion between the module '_random' and the
## function 'random'.

import random as _random
import urllib as _urllib
import math as _math


MAX_BITS_GIVEN_BY_FOURMI = 2048 * 8
def random_bits(n=MAX_BITS_GIVEN_BY_FOURMI):
    """Returns a list of n random bits."""
    assert n <= MAX_BITS_GIVEN_BY_FOURMI, "Maximum of 2048 bytes exceeded"
    urlstr = "http://www.fourmilab.ch/cgi-bin/uncgi/Hotbits?"+\
             "nbytes=%d&fmt=bin" % _math.ceil(n / 8.0)
    bytes = _urllib.urlopen(urlstr).read()
    bits = []
    for b in bytes: bits.extend(byte_to_binary(ord(b)))
    return bits[:n]


def _pseudorandom_bits(n):
    """Similar to random_bits, but for offline testing.  We don't want
    to hammer Fourmilab while testing this module."""
    bits = []
    for i in range(n): bits.append(_random.randrange(2))
    return bits


def clump_by_n(sequence, n):
    """Given a sequence, returns a list of grouped chunks of that
    sequence, each of length n (except, possibly, the last chunk)."""
    collection = []
    for i in range(0, len(sequence), n):
        collection.append(sequence[i : i+n])
    return collection


def byte_to_binary(byte):
    """Converts a byte into a binary list of bits."""
    assert 0 <= byte < 256, "byte not within range 0 <= byte < 256"
    bits = []
    for i in range(8):
        bits.append(byte % 2)
        byte = int(byte / 2)
    bits.reverse()
    return bits


def binary_list_to_long(bits):
    """Converts a list of bits to a long."""
    value = 0L
    for b in bits: value = (value * 2) + b
    return value


######################################################################


class FourmiRandom(_random.Random):
    """A subclass of _random.Random that supplies truly random numbers."""
    BITS_USED = 53
    SOURCE_CAPACITY = int(MAX_BITS_GIVEN_BY_FOURMI / BITS_USED)
    def __init__(self):
        self._source = []


    def random(self):
        if not self._source: self._refill_source()
        return self._source.pop()

    def _refill_source(self):
##        bits = _pseudorandom_bits(self.SOURCE_CAPACITY * self.BITS_USED)
        bits = random_bits(self.SOURCE_CAPACITY * self.BITS_USED)
        clumps = clump_by_n(bits, self.BITS_USED)
        for c in clumps:
            self._source.append(_math.ldexp(binary_list_to_long(c),
                                            -self.BITS_USED))


    ## The rest of these functions won't be useful, since our source
    ## is truly random and can't be seeded.
    def seed(self, a=None): pass
    def getstate(self): return None
    def setstate(self, state): pass
    def jumpahead(self, n): pass


######################################################################


## A little trick to make fourmirandom look much like the random module.
_inst = FourmiRandom()
seed = _inst.seed
random = _inst.random
uniform = _inst.uniform
randint = _inst.randint
choice = _inst.choice
randrange = _inst.randrange
shuffle = _inst.shuffle
normalvariate = _inst.normalvariate
lognormvariate = _inst.lognormvariate
cunifvariate = _inst.cunifvariate
expovariate = _inst.expovariate
vonmisesvariate = _inst.vonmisesvariate
gammavariate = _inst.gammavariate
stdgamma = _inst.stdgamma
gauss = _inst.gauss
betavariate = _inst.betavariate
paretovariate = _inst.paretovariate
weibullvariate = _inst.weibullvariate
getstate = _inst.getstate
setstate = _inst.setstate
jumpahead = _inst.jumpahead
whseed = _inst.whseed