`On Sun, 24 Mar 2019 at 21:47:50 +0100, Jason A. Donenfeld wrote:> I generally use a slightly simpler algorithm in various different projects:> > //[0, bound)> static unsigned long random_bounded(unsigned long bound)> {>        unsigned long ret;>        const unsigned long max_mod_bound = (1 + ~bound) % bound;> >        if (bound < 2)>                return 0;>        do>                ret = random_integer();>        while (ret < max_mod_bound);>        return ret % bound;> }>> Is the motivation behind using Lemire that you avoid the division (via> the modulo) in favor of a multiplication?Yes.  If we define eps = max_mod_bound * ldexp(1.0, -BITS_PER_LONG) asthe probability of one retry, and retries = eps / (1 - eps) as theexpected number of retries, then both algorithms take 1+retriesrandom_integer()s.The above agorithm takes 2 divisions, always.  Divides are slow, andusually not pipelined, so two in short succession gets a latency penalty.Lemire's mutiplicative algorithm takes 1 multiplication on the fastpath (probability 1 - 2*eps on average), 1 additional division on the slowpath (probability 2*eps), and 1 multiplication per retry.In the common case when bound is much less than ULONG_MAX, eps istiny and the fast path is taken almost all the time, and it'sa huge win.Even in the absolute worst case of bound = ULONG_MAX/2 + 2 wheneps ~ 0.5 (2 multiplies, 0.5 divide; there's no 2*eps penalty inthis case), it's faster as long as 2 mutiplies cost less than 1.5divides.I you want simpler code, we could omit the fast path and stil geta speedup.  But a predictable branch for a divide seemed likea worthwhile trade.(FYI, this all came about as a side project of a kernel-janitor projectto replace "prandom_u32() % range" by "prandom_u32() * range >> 32".I'm also annoyed that get_random_u32() and get_random_u64() haveseparate buffers, even if EFFICIENT_UNALIGNED_ACCESS, but that'sa separate complaint.)`