On Wed, 9 May 2001, katkittty wrote:
>the random number generator in my Java sure takes a long time. It makes the
>randomly rotating 3D face I am working on move kinda slow. Is there a fast
>way to make fake random numbers?
Heh. In crypto we spend a lot of effort on getting really *good* random
numbers, but for a simple graphic hack or an interactive simulation, you
don't need excellent randomness.
Knuth spent a whole chapter in the God Book on getting pseudorandom
numbers fast and testing the quality of their pseudorandomness. I
think the best really fast generator is the "Lagged-fibonacci"
generator. Basically it's a circular vector of numbers and three
indexes into it. Each time you want a "random number", you add
one to each of the three indexes (modulo the length of the vector),
then add the two numbers found at the first two indexes, take the
result mod whatever your range is, and this number is your output.
Write the output back into the vector at the position indicated by
the third index, and you're done.
Initialization is simple, but requires some knowledge you can look
up. Basically the initial values of the three indexes have to define
a primitive polynomial relative to each other, and the numbers in
the vector can't all be even.
Bear
