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), 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, 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). 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/), 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
