A not so Random Random

Jesse Welton jwelton at pacific.mps.ohio-state.edu
Fri Jun 11 19:08:22 UTC 1999


John.Maloney at disney.com wrote:
> 
> >It seems to me the correct solution is to take out all the asFloat
> >stuff, and apply it instead to the return value of Random>>next.  That
> >way, all calculations are performed internally with integers, which
> >shouldn't cause the problem described above, and would be more
> >amenable to producing various random integer distributions.
> 
> Indeed, this random number generator is based on a veru well-known
> 32-bit integer random number generator. However, since Squeak's
> integers have two fewer bits than an unsigned C ints (one for the
> "integer" bit, one for the sign bit), the first version of this
> 32-bit generator frequently overflowed into LargePositiveIntegers.
> It got the right answer, but it was quite slow. Thus, someone
> (either David N. Smith or Dan Ingalls, I think) re-wrote it using
> Squeak's Floats, which are 64 bit double precision Floats with
> more than enough bits of mantissa. This was much faster, since
> all the arithmetic used the float primitives.

Yes, experimenting with changing the generator to use integers, I
found it to be much slower, and figured that must be why it was
changed to use floats.  If I recall correctly, it was almost 50 times
as slow, which puzzled me.  That it runs into LargePositiveIntegers
helps explain that, but I'm still not sure why it should be so *much*
slower.

Here's a question: If the algorithm were changed to use a modulus
which fits into Squeak's 30-bit integers, would the resulting code run
any faster than the float version, or still slower?

> I wonder if this problem of getting stuck in a cycle is a side
> effect of floating point roundoff and/or normalization? I would
> expect the integer version of the algorithm to be free of this
> problem; it was a well-tested and studied choice of parameters,
> which is  why we chose it.

I did try some long runs of the generator with both integer and float
computations, both seeded identically, and they were in complete
agreement after a million or so iterations.  The kinds of calculations
involved look like they would tend to avoid roundoff errors, too, so
my guess is the float calculations are probably exact.

-Jesse Welton





More information about the Squeak-dev mailing list