Re: [Tarantool-patches] [PATCH] core: introduce evenly distributed int64 random in range

[Vladislav Shpilevoy <v.shpilevoy@tarantool.org>]

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.