Is it conceivable that this is a library that people would like to use outside of Rust itself? In other words, would it make sense to package this library in runtimeless/standalone format, and have Rust depend on it via submodule?
On Fri, Apr 26, 2013 at 9:47 PM, Huon Wilson <[email protected]> wrote: > 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
