from warnings import warn as _warn
from types import MethodType as _MethodType, BuiltinMethodType as _BuiltinMethodType
from math import log as _log, exp as _exp, pi as _pi, e as _e, ceil as _ceil
from math import sqrt as _sqrt, acos as _acos, cos as _cos, sin as _sin

BPF = 53        # Number of bits in a float

class Random:
    def __init__(self, x=None):
        """Initialize an instance.

        Optional argument x controls seeding, as for Random.seed().
        """

        self.seed(x)
        self.gauss_next = None

    def randrange(self, start, stop=None, step=1, int=int, default=None,
                      maxwidth=1L<<BPF):
            """Choose a random item from range(start, stop[, step]).

            This fixes the problem with randint() which includes the
            endpoint; in Python this is usually not what you want.
            Do not supply the 'int', 'default', and 'maxwidth' arguments.
            """

            # This code is a bit messy to make it fast for the
            # common case while still doing adequate error checking.
            istart = int(start)
            if istart != start:
                raise ValueError, "non-integer arg 1 for randrange()"
            if stop is default:
                if istart > 0:
                    if istart >= maxwidth:
                        return self._randbelow(istart)
                    return int(self.random() * istart)
                raise ValueError, "empty range for randrange()"

            # stop argument supplied.
            istop = int(stop)
            if istop != stop:
                raise ValueError, "non-integer stop for randrange()"
            width = istop - istart
            if step == 1 and width > 0:
                # Note that
                #     int(istart + self.random()*width)
                # instead would be incorrect.  For example, consider istart
                # = -2 and istop = 0.  Then the guts would be in
                # -2.0 to 0.0 exclusive on both ends (ignoring that random()
                # might return 0.0), and because int() truncates toward 0, the
                # final result would be -1 or 0 (instead of -2 or -1).
                #     istart + int(self.random()*width)
                # would also be incorrect, for a subtler reason:  the RHS
                # can return a long, and then randrange() would also return
                # a long, but we're supposed to return an int (for backward
                # compatibility).

                if width >= maxwidth:
                    return int(istart + self._randbelow(width))
                return int(istart + int(self.random()*width))
            if step == 1:
                raise ValueError, "empty range for randrange() (%d,%d, %d)" % (istart, istop, width)

            # Non-unit step argument supplied.
            istep = int(step)
            if istep != step:
                raise ValueError, "non-integer step for randrange()"
            if istep > 0:
                n = (width + istep - 1) // istep
            elif istep < 0:
                n = (width + istep + 1) // istep
            else:
                raise ValueError, "zero step for randrange()"

            if n <= 0:
                raise ValueError, "empty range for randrange()"

            if n >= maxwidth:
                return istart + istep*self._randbelow(n)
            return istart + istep*int(self.random() * n)

    def random(self):
        """Get the next random number in the range [0.0, 1.0)."""

        # Wichman-Hill random number generator.
        #
        # Wichmann, B. A. & Hill, I. D. (1982)
        # Algorithm AS 183:
        # An efficient and portable pseudo-random number generator
        # Applied Statistics 31 (1982) 188-190
        #
        # see also:
        #        Correction to Algorithm AS 183
        #        Applied Statistics 33 (1984) 123
        #
        #        McLeod, A. I. (1985)
        #        A remark on Algorithm AS 183
        #        Applied Statistics 34 (1985),198-200

        # This part is thread-unsafe:
        # BEGIN CRITICAL SECTION
        x, y, z = self._seed
        x = (171 * x) % 30269
        y = (172 * y) % 30307
        z = (170 * z) % 30323
        self._seed = x, y, z
        # END CRITICAL SECTION

        # Note:  on a platform using IEEE-754 double arithmetic, this can
        # never return 0.0 (asserted by Tim; proof too long for a comment).
        return (x/30269.0 + y/30307.0 + z/30323.0) % 1.0

    def _randbelow(self, n, _log=_log, int=int, _maxwidth=1L<<BPF,
                   _Method=_MethodType, _BuiltinMethod=_BuiltinMethodType):
        """Return a random int in the range [0,n)

        Handles the case where n has more bits than returned
        by a single call to the underlying generator.
        """

        try:
            getrandbits = self.getrandbits
        except AttributeError:
            pass
        else:
            # Only call self.getrandbits if the original random() builtin method
            # has not been overridden or if a new getrandbits() was supplied.
            # This assures that the two methods correspond.
            if type(self.random) is _BuiltinMethod or type(getrandbits) is _Method:
                k = int(1.00001 + _log(n-1, 2.0))   # 2**k > n-1 > 2**(k-2)
                r = getrandbits(k)
                while r >= n:
                    r = getrandbits(k)
                return r
        if n >= _maxwidth:
            _warn("Underlying random() generator does not supply \n"
                "enough bits to choose from a population range this large")
        return int(self.random() * n)

    def seed(self, a=None):
        """Initialize internal state from hashable object.

        None or no argument seeds from current time or from an operating
        system specific randomness source if available.

        If a is not None or an int or long, hash(a) is used instead.
        """

        if a is None:
            import time
            a = long(time.time() * 256) # use fractional seconds

        if not isinstance(a, (int, long)):
            a = hash(a)

        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

        self.gauss_next = None

_inst = Random()
seed = _inst.seed
random = _inst.random
randrange = _inst.randrange