Integer Overflow

Gareth McCaughan Gareth.McCaughan at pobox.com
Wed Nov 28 17:55:56 EST 2001


"Ursus Horibilis" wrote:

[I said:]
> >   - using a 1-element list is about the nearest equivalent
> >     we have to passing in a pointer as your C code does.
> >     It's not necessarily good style (but then, neither is
> >     the pointer-passing thing).
> 
> Could you expand on that?  It sounds like it has all the
> makings of a religious war (;-)  Would the following be a
> preferred way of doing things:
> 
>  def Lcprng(state):
>    """Pass this a variable containing the seed. Don't forget to
>        update the seed with the returned value each time this
>       function is called."""
>    return int((29L*state+13L) & 0x0FFFFFFFL)
> 
> .......Calling Program......
>  RanNum = 987654321 # Initialize Random Number Seed
> 
> ............................................
> 
>  RanNum = Lcprng(RanNum) # Keep updating seed with value

I'd prefer an approach in which you don't need to pass
the state in explicitly at all. In C, that would usually
mean using a static variable. In Python, more natural
would be to define a class whose instances have the job
of dispensing random numbers:

    class RandomNumberGenerator:
      def __init__(self, seed=1):
        self._seed = seed
      def next(self):
        self._seed = (29L*self._seed+13) & 0xFFFFFFFFL
        return self._seed

and then you'd say

    >>> rng = RandomNumberGenerator()
    >>> x = rng.next()
    >>> print "I got", x
    I got 42L

This way you can, for instance, have more than one instance
of the RNG, updating their states independently. Is this
useful? I'm not sure. :-) If you prefer just to have a function
that spits out a new "random" number every time, you can then
say

    >>> get_random_number = RandomNumberGenerator().next
    >>> get_random_number()
    42L
    >>> get_random_number()
    1231L

If you don't like getting longs back from the RNG, by
the way, it unfortunately won't do to call int() on the
result as you do above, because you'll get an overflow
once the result is 0x80000000 or above. Instead you'd
have to say something like

    return int(self._seed - 2*(self._seed & 0x80000000L))

to convert to a *signed* number before intifying.

> >   - After one iteration, the value in "state" will be a
> >     long integer and there will therefore be no danger
> >     of overflow. But you should make sure you start it
> >     off with a long anyway.
> 
> What will happen if I do this:
> 
>      state[0] = int((29L * state[0] + 13L) & 0x0FFFFFFFFL)
> 
> ?

See above. (But it's sufficient to guarantee that whatever
you pass in you won't get an overflow.)

> > By the way, that's not a very good random number generator.
>
> :-)
> 
> Yes, you're right.  Linear Congruential PRNG's are not very
> good, but they are widely used because of their simplicity.  I
> just whipped an equation off the top of my head that would
> generate maximal-period pseudo random numbers.  I wasn't
> worried much about the quality.

Well, what I actually meant was that even for a LCG that's
a pretty poor one. It fails the spectral test disastrously,
for instance.

> Better is:
> 
>      state = 179418817 + 179419969 * state

Yes, that's better.

By the way, Python does have its own RNG module. It generates
better random numbers than either of the generators mentioned
in this article. :-)

-- 
Gareth McCaughan  Gareth.McCaughan at pobox.com
.sig under construc



More information about the Python-list mailing list