As I have some interest in using RNGs in Rust, I'd like to chime in on this.
The extra traits like "RandomDistribution" would be a good thing, especially if it would be possible to "plug" a different, custom generator than the one provided and use the custom generator with code that simply calls rand(). For example for normal generation I might not want to use Ziggurat, or maybe I want a quasi-random uniform generator instead of a PRNG. (For normal generation I've been using Box Muller but it is a bit slow, Ziggurat may be slower when generating samples on the tails of the distribution, so maybe the ideal would be to use the inversion method over a good algorithm for generating quantiles, like R does, but this takes a bit more work). Also, if you're not already doing so I'd recommend running some statistical tests on the PRNG you're implementing, just to have a greater degree of confidence about them. The Diehard and Dieharder test suites are popular for testing the output of a PRNG. I may help with this if needed. 2013/4/26 Huon Wilson <[email protected]> > Hi all, > > Recently I've been doing quite a bit of experimentation with random > number generation in Rust, and I've got a few > ideas/suggestions/experiments that I'd like feedback on before I clean > them up and open pull requests (or not). (I know that random numbers > are spectacularly easy to screw up, and can have bad consequences, so > I'm trying to be as careful and as explicit as possible with any > changes.) > > Some background: the main RNG that Rust currently uses is ISAAC > (http://burtleburtle.net/bob/**rand/isaacafa.html<http://burtleburtle.net/bob/rand/isaacafa.html>), > and is implemented > in the runtime, which core::rand calls into. The runtime calls are > quite slow, so I opened #6073 which is a pure Rust implementation of > it, which gives speeds comparable to the pure C version (yay for > performance!). > > However, the ISAAC algorithm is a 32 bit one (and the original > implementation from the inventor meant that it was incorrect on 64-bit > platforms; the fix is #6058 and is in bors' queue), which means that > 64-bit computers are running at half capacity. I'm proposing to > implement the ISAAC-64 algorithm (specified on the page above) which > generates a random 64 bit number in the same time that ISAAC generates > a 32 bit one (although, not surprisingly, the sequence of random > numbers is different), and apparently has the same cryptographic > properties, but I haven't been able to find any papers about it > explicitly. > > Rust would default to using the 64 bit algorithm on 64 bit computers, > but would provide a clear way to get a "consistent" RNG that gives the > same sequence on both 32 and 64-bit platforms for a given initial seed > (but not on different endiannesses, if I understand how the seeding > works; but this is probably fixable, if it is deemed desirable). To > get the full power of ISAAC-64, this would require adding a `next64() > -> u64` method to the Rng trait. > > This change would double or triple throughput of random f64 generation > on 64-bit platforms compared to using the 32-bit algorithm (and > increase it 10-20x compared to calling the rng in the runtime, as is > done now). On this note, f64s are generated by `a/max_u32 + > b/max_u32^2 + c/max_u32^3`, where a, b, and c are random u32s, Many > other languages just generate a single u64 and multiply by `1/max_u64` > (e.g. > http://hg.python.org/cpython/**file/2.7/Lib/random.py#l809<http://hg.python.org/cpython/file/2.7/Lib/random.py#l809>, > this > even uses 7 bytes, not 8), would this be an acceptable change? > > > Lastly, I experimented with generating (so far) normal and exponential > distributed random numbers using the Ziggurat algorithm > (https://en.wikipedia.org/**wiki/Ziggurat_algorithm<https://en.wikipedia.org/wiki/Ziggurat_algorithm>). > This works quite > well, and can be extended to other distributions (with certain > restrictions). Are these wanted in core/std? > > I'm proposing creating std::rand with these, possibly with a few extra > traits e.g. "RandomDistribution". For reference the C++ stdlib > contains a whole pile of distributions > (http://www.cplusplus.com/**reference/random/<http://www.cplusplus.com/reference/random/>), > as does the Python > stdlib. (Is this wiki-bikeshed worthy?) > > If this is going to be added to the libraries, then there is a script > that generates a file containing the tables required for the Ziggurat > algorithm. Should this go in src/etc? > > > Huon > ______________________________**_________________ > Rust-dev mailing list > [email protected] > https://mail.mozilla.org/**listinfo/rust-dev<https://mail.mozilla.org/listinfo/rust-dev> >
_______________________________________________ Rust-dev mailing list [email protected] https://mail.mozilla.org/listinfo/rust-dev
