Feature #18463: Random number generation with xoshiro

• Status: Open
• Assignee: -
• Target version: -

[bbrklm (Benson Muite)]

Xoshiro https://prng.di.unimi.it/ random number generation is typically faster than Mersenne Twister currently used in Ruby in https://github.com/ruby/ruby/blob/master/random.c It would be good to allow use of xoshiro either as an option or as default. Xoshiro is the default for Fortran https://gcc.gnu.org/onlinedocs/gfortran/RANDOM_005fNUMBER.html and Julia https://github.com/JuliaLang/julia/tree/master/stdlib/Random/src Happy to implement this.

[shyouhei (Shyouhei Urabe)]

I guess you can start implementing xoshiro as a separate gem now. I remember @mrkn (Kenta Murata) once wanted to implement xorshift, and include/ruby/random.h was introduced (mainly) for that purpose. Not sure his current status though.

[bbrklm (Benson Muite)]

Thanks for the feedback. Another good algorithm is pcg https://rubygems.org/gems/pcg_random

[mame (Yusuke Endoh)]

• Related to Feature #16827: C API for writing custom random number generator that can be used as Random objects added

[nobu (Nobuyoshi Nakada)]

That gem seems pretty old, before include/ruby/random.h was introduced.
You can see a skeleton at ext/-test-/random/loop.c too.

[bbrklm (Benson Muite)]

A work in progress Gem can be found at https://gitlab.com/bkmgit/xoshiro256plusplus

The default in https://github.com/ruby/ruby/blob/master/random.c is to use uint32_t type in C. Will uint64_t also be supported when it is available?

It is also possible to just use xoshiro128++ which generates uint32_t type, which has portability and maintenance advantage, but also a speed disadvantage.

[bbrklm (Benson Muite)]

Work in progress gem for xoshiro128++ [0]

Python continues to use Mersenne twister as default[1], but Numpy has been recently extended to include other options[2].

Some considerations for C++ are discussed in [3].

Randen [4] calls hardware implemented functions, but these may not be available on all architectures.

If there is need for backwards compatibility, Mersenne twister can be kept as default, for example the Go community has chosen to keep an unusual random number generator as default[5][6][7][8]. My expectation is that xoshiro128++ is a reasonable general purpose replacement for Mersenne twister for core language. Java also chains together random sequences of bytes to generate random big integers[9], so this is probably ok for portability of the base language, though tests and other quality assurances would be nice as well. More specialized random number generators might be better in a separate gem.

One further issue might be using the random number generator with Ractors. Some of the random number generators provide a jump function to ensure that random sequences generated at in parallel do not overlap for a large fixed set of invocations. This is not in the interfaces available in include/ruby/random.h. GPU libraries also often make several independent streams of random numbers.

[0] https://gitlab.com/bkmgit/xoshiro128plusplus
[1] https://docs.python.org/3/library/random.html
[2] https://github.com/bashtage/randomgen/
[3] http://open-std.org/JTC1/SC22/WG21/docs/papers/2019/p1932r0.pdf
[4] https://github.com/google/randen
[5] https://cs.opensource.google/go/go/+/963753d3f95a79d2826de2837e6296f7b8117dc6
[6] https://github.com/golang/go/blob/master/src/math/rand/rng.go
[7] https://github.com/golang/go/issues/26263
[8] https://github.com/golang/go/issues/21835
[9] https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/math/BigInteger.java#L713
[10] https://github.com/clMathLibraries/clRNG
[11] https://github.com/ROCmSoftwarePlatform/rocRAND

[mrkn (Kenta Murata)]

@bbrklm (Benson Muite) I want the Xoshiro256 generator for Ruby, too. In addition to it, I want the dSFMT generator.

I think it is good to create a semi-standard gem library for providing such random number generators. The existence of the semi-standard library can prevent confusion by emerging many different libraries. I'm working on creating such a semi-standard gem library in a private repository under the ruby organization. Currently, I'm implementing SFMT and dSFMT in the repository. I want to include xoshiro-family and PCG generators in the repository before releasing it.

Would you please help to implement generators in the repository?

[bbrklm (Benson Muite)]

@mrkn (Kenta Murata) Happy to add Xoshiro and PCG generators. Probably also good to add
MRG32k3a [1]
Philox [2]
MixMax [3][4]
Squares [5]

The Rust library has good documentation[6], as well as speed comparisons. Would be good to have something similar for Ruby.

Related issues on SIMD #16487 and #14328. SIMDJson[8] only has Ruby bindings, but Go and Rust ports because these languages have SIMD libraries. Maybe it would be good to have a SIMD gem for Ruby? Portability is also required, so while the approach in [9] gives some idea of performance improvements, using approaches similar to PeachPy [10] or Portable SIMD [11] might be better. SFMT implementation may give suggestions on how to make SIMD capabilities available for other native Gems.

[1] https://github.com/vigna/MRG32k3a
[2] https://github.com/DEShawResearch/random123
[3] https://mixmax.hepforge.org/
[4] http://www.iro.umontreal.ca/~lecuyer/myftp/papers/mixmax-lattice.pdf
[5] https://squaresrng.wixsite.com/rand
[6] https://rust-random.github.io/book/intro.html
[7] https://bugs.ruby-lang.org/issues/16487
[8] https://github.com/Martin-Nyaga/ruby-ffi-simd
[9] https://simdjson.org/software/
[10] https://github.com/Maratyszcza/PeachPy
[11] https://github.com/stoklund/portable-simd