ISAAC Random Number Generator

[Kirk Haines]

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

 

[ts]

P> How does ISAAC hold up under Marsaglia's "Die-Hard" test suite? I
P> believe Ruby is currently providing an implementation of the Mersenne
P> Twister, which has aced the Die-Hard tests and has a cycle length on the
P> order of 10^600, so I don't see a compelling reason to go with something
P> 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

 

[ts]

P> Thanks for the clarification. Now you've got me curious - what makes a
P> generator cryptographically secure, as opposed to being statistically
P> indistinguishable from true randomness (which is what you want for Monte
P> 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 secure pseudo-random number generator



Guy Decoux

 

[Kirk Haines]

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

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

 

[Joel VanderWerf]

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.