From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtpng1.m.smailru.net (smtpng1.m.smailru.net [94.100.181.251]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id A30DC469719 for ; Thu, 17 Sep 2020 16:56:54 +0300 (MSK) References: <20200904135149.2756-1-i.kosarev@tarantool.org> <67586d6e-46aa-e4f4-1ee7-3fb733bd80db@tarantool.org> <1599398398.275563907@f169.i.mail.ru> From: Vladislav Shpilevoy Message-ID: <15e267cf-2d00-4ec7-f568-639d6285ffeb@tarantool.org> Date: Thu, 17 Sep 2020 15:56:52 +0200 MIME-Version: 1.0 In-Reply-To: <1599398398.275563907@f169.i.mail.ru> Content-Type: text/plain; charset="utf-8" Content-Language: en-US Content-Transfer-Encoding: 8bit Subject: Re: [Tarantool-patches] [PATCH] core: introduce evenly distributed int64 random in range List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Ilya Kosarev Cc: tarantool-patches@dev.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 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.