On 26/04/2013 6:47 PM, Huon Wilson wrote:
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?
I'm not expert in this area and I'm not sure if any of us are; you might know better than anyone else here. I certainly don't object to adopting the ISAAC-64 algorithm if it's well understood by experts to be an improvement over the 32bit variant. If you'd be so kind as to survey the state of this sort of thing, document it and make changes to conform to what appears to be the best practice of other libraries (following our library-editing process[1] .. mostly just leave a paper trail for others), I would certainly appreciate it.
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?
Yes. They can go in core::rand presently. We might refactor or move them if they seem too big, esoteric or arduous to maintain.
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?)
Again, this feels like something where the library process of surveying, documenting and distilling might shed some light. I believe the recent work from C++11 is nearly state of the art, but I wouldn't be surprised if other languages have important contributions to the design space to be aware of also.
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?
Yes please. Thanks for getting involved in this! Random numbers are often overlooked. -Graydon [1] https://github.com/mozilla/rust/wiki/Libs _______________________________________________ Rust-dev mailing list [email protected] https://mail.mozilla.org/listinfo/rust-dev
