[Tarantool-patches] [PATCH] core: introduce evenly distributed int64 random in range
Vladislav Shpilevoy
v.shpilevoy at tarantool.org
Thu Sep 17 16:56:52 MSK 2020
Hi! Thanks for the investigation!
> 2. Well, yes, scaling doesn’t really seem to work as good as we want to.
> I looked through this page: https://www.pcg-random.org/posts/bounded-rands.html
> on generation in range and found out a bounding method which i think is
> the most suitable for us. It works for int64_t too and can be used both
> for «complete random» and «pseudo-random»:
>
> ```
> uint32_t bounded_rand(rng_t& rng, uint32_t range) {
> uint32_t mask = ~uint32_t(0);
> --range;
> mask >>= __builtin_clz(range|1);
> uint32_t x;
> do {
> x = rng() & mask;
> } while (x > range);
> return x;
> }
> ```
Looks good.
> ```
> std::random_device rd;
> std::mt19937_64 generator(rd());
> std::uniform_int_distribution<int64_t> range(min, max);
> return range(generator);
> ```
>
> However, C++ implementation seems to be overcomplicated.
> I think it is better idea to implement something simple & fast.
>
> For the mersenne_twister the good idea is to adopt this implementation,
> as far as i see it:
> http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt64.html
>
> But what i think might be even better is to take something less classic
> while more relevant, according to this paper: https://arxiv.org/pdf/1910.06437.pdf
>
> I think the best option for us now is xoshiro256++: http://prng.di.unimi.it/
> It seems to be much faster and doesn’t fail any known statistical test as far as i see.
> The implementation to adapt: http://prng.di.unimi.it/xoshiro256plusplus.c
Looks good. Although I wouldn't say it is significantly better than the
twister. You can proceed with xoshiro256++ if you want.
More information about the Tarantool-patches
mailing list