ISAAC Random Number Generator

Iowa includes a class, Iowa::ISAAC, which is a pure ruby implementation of
the ISAAC random number generator.

Here’s the page that describes the algorithm:

http://burtleburtle.net/bob/rand/isaac.html

Basically, ISAAC is a very good random number generator, with no cycles
shorter than 2^40, with a very, very long expected cycle, and with an
unbiased and uniform distribution.

Is there any interest in this existing in a package of its own? If so, I
could repackage it and release it seperately.

Kirk Haines

Kirk Haines wrote:

Iowa includes a class, Iowa::ISAAC, which is a pure ruby implementation of
the ISAAC random number generator.

Here’s the page that describes the algorithm:

ISAAC and RC4

Basically, ISAAC is a very good random number generator, with no cycles
shorter than 2^40, with a very, very long expected cycle, and with an
unbiased and uniform distribution.

Is there any interest in this existing in a package of its own? If so, I
could repackage it and release it seperately.

Kirk Haines

How does ISAAC hold up under Marsaglia’s “Die-Hard” test suite? I
believe Ruby is currently providing an implementation of the Mersenne
Twister, which has aced the Die-Hard tests and has a cycle length on the
order of 10^600, so I don’t see a compelling reason to go with something
else in terms of the quality of the random numbers.

The thing I WOULD like to see is Ruby’s generator wrapped up as a class
which provides separate, independent random stream objects. That would
enable Ruby to be used for serious simulation work.[**]

–paul

[**] - I’ve separated the following because most people probably aren’t
interested in the gory details. Read on at your own peril of being bored.

To obtain greater statistical “leverage” from a simulation study, it’s
sometimes helpful to make multiple runs of your model in which you
induce positive or negative correlation between pairs of models. To get
the desired correlation, you need to keep the random numbers
synchronized between the two systems, so that the same value is used in
the same place and same simulated time. If everybody is drawing from
the same source of randomness, and there are different numbers of
objects in the two systems being compared, it’s nearly impossible to
maintain synchronization. The most common solution is to give each
object its own personal stream of random numbers, seeded independently
of all the others. Synchronization is still non-trivial, but at least
it’s possible if you can have multiple separately seeded generators.

How does ISAAC hold up under Marsaglia's "Die-Hard" test suite? I
believe Ruby is currently providing an implementation of the Mersenne
Twister, which has aced the Die-Hard tests and has a cycle length on the
order of 10^600, so I don't see a compelling reason to go with something
else in terms of the quality of the random numbers.

ISAAC was designed to be cryptographic secure, this is not the case for
Mersenne Twister, which is more appropriate for Monte Carlo.

Guy Decoux

How does ISAAC hold up under Marsaglia’s “Die-Hard” test suite? I
believe Ruby is currently providing an implementation of the
Mersenne Twister, which has aced the Die-Hard tests and has a cycle
length on the order of 10^600, so I don’t see a compelling reason to
go with something else in terms of the quality of the random numbers.

I don’t know. I just downloaded diehard and am running a few tests.
The expected cycle length of ISAAC is 2^8287. It is intended to be
cryptographically secure.

in the same place and same simulated time. If everybody is drawing
from the same source of randomness, and there are different numbers
of objects in the two systems being compared, it’s nearly impossible
to maintain synchronization. The most common solution is to give
each object its own personal stream of random numbers, seeded
independently of all the others. Synchronization is still non-
trivial, but at least it’s possible if you can have multiple
separately seeded generators.

You could do that with Crypt::ISAAC. Seed each instance from the hardware
random number generator or something, and then each will be an independent
source of random numbers.

Kirk Haines

···

On Sat, 22 May 2004 00:43:52 +0900, Paul Sanchez wrote

Paul Sanchez wrote:

The thing I WOULD like to see is Ruby’s generator wrapped up as a class
which provides separate, independent random stream objects. That would
enable Ruby to be used for serious simulation work.[**]

I’ll second that. Independent PRNG streams are very important in the
simulation work I do. I am currently using the PRNG from Numerical
Recipes, but it’s not as good as MT19937 (Mersenne Twister), which is
what Ruby uses for #rand(). Also, you can’t distribute the NR source to
people who don’t have the NR license, whereas MT has a BS-style license,
now.

The drawback of MT might be the memory requirements of the generator
state, which is 624+ bytes.

One of these days, I’ll wrap up an extension for multiple MT19937 streams.

ts wrote:

“P” == Paul Sanchez paul@NOargelSPAMfraster.org writes:

How does ISAAC hold up under Marsaglia’s “Die-Hard” test suite? I
believe Ruby is currently providing an implementation of the Mersenne
Twister, which has aced the Die-Hard tests and has a cycle length on the
order of 10^600, so I don’t see a compelling reason to go with something
else in terms of the quality of the random numbers.

ISAAC was designed to be cryptographic secure, this is not the case for
Mersenne Twister, which is more appropriate for Monte Carlo.

Thanks for the clarification. Now you’ve got me curious - what makes a
generator cryptographically secure, as opposed to being statistically
indistinguishable from true randomness (which is what you want for Monte
Carlo)?

–paul

Thanks for the clarification. Now you've got me curious - what makes a
generator cryptographically secure, as opposed to being statistically
indistinguishable from true randomness (which is what you want for Monte
Carlo)?

Well a prng is said cryptographic when
   * it's difficult to predict the output from examining the previous
     output

   * it's difficult to extract internal state from examining the output

  http://encyclopedia.thefreedictionary.com/Cryptographically%20secure%20pseudo-random%20number%20generator

Guy Decoux