Re: Distributed random number ordering

From: Lénárd Szolnoki <cpp_at_[hidden]>
Date: Thu, 13 May 2021 19:26:47 +0100
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

-------- Original Message --------
From: Arthur O'Dwyer via Std-Proposals <std-proposals_at_[hidden]>
Sent: May 13, 2021 3:14:59 PM GMT+01:00
To: Std-Proposals <std-proposals_at_[hidden]>
Cc: Arthur O'Dwyer <arthur.j.odwyer_at_[hidden]>
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_at_[hidden]> 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