Hi,

That implementation consumes one or more generator calls per returned uniformly distributed integer. In this sense it's wasteful for low n, as a single generator call could be used for multiple independent uniform ints.

There is also an optimization opportunity for using up the 'partial bits' you throw away in the while loop.

But there is no one good solution. For a cheap underlying generator these efforts are somewhat wasted and might even degrade performance, but for an expensive one it's probably worth it.

Cheers,
Lénárd

From: Arthur O'Dwyer via Std-Proposals <std-proposals@lists.isocpp.org>
Sent: May 13, 2021 3:14:59 PM GMT+01:00
To: Std-Proposals <std-proposals@lists.isocpp.org>
Cc: Arthur O'Dwyer <arthur.j.odwyer@gmail.com>
Subject: Re: [std-proposals] Distributed random number ordering

On Thu, May 13, 2021 at 2:56 AM Lénárd Szolnoki via Std-Proposals <std-proposals@lists.isocpp.org> wrote:
Hi,

Is uniform_int_distribution really trivial?

It's relatively trivial. ;)
When I'm writing code that needs both speed and cross-platform behavior, I just do `g() % n`; for most applications the bias of "%" is lost in the noise.
If you need absolute fairness, it'd be like

    int mask = std::bit_ceil(n)  - 1;
    while (true) {
        int r = g() & mask;
        if (r < n) return r;
    }

And if you want your code to work with URBG types `G` where `G::min() != 0` and/or `G::max()+1 < n`, then it'd be like
    std::independent_bits_engine<G, 64, uint64_t> realg(g);
and then work with `realg`.
I'm like 90% sure std::independent_bits_engine's behavior is cross-platform, so you wouldn't have to reimplement it.
Actually, if your `G::max()` is too small, it's certainly a better idea to reimplement your `G`, instead of trying to adapt a bad `G` via standard tools.
(I realized at this point that I didn't know where to point people for a good `G`, so I went and created https://github.com/Quuxplusone/Xoshiro256ss/blob/main/xoshiro256ss.h so now I can point people there. ;))

–Arthur