Fast, unbiased, integer pseudo-random generator with arbitrary limits

You can expand yours histogram

to "high" power by two by using it by filling in trailing spaces with some dummy value (guaranteed to never appear in real data). For example. with histogram

[10, 5, 6]

      

        
        
        
      

    

stretch it up to 16 as suggested (assumed to be -1

a valid sentinel signal):

[10, 5, 6, 10, 5, 6, 10, 5, 6, 10, 5, 6, 10, 5, 6, -1]

      

        
        
        
      

    

The sampling can then be done through a binary mask histogram[prng() & mask]

, where mask = (1 << new_length) - 1

, with a check that the sentinel value is repeated, i.e.

int value;
do {
    value = histogram[prng() & mask];
} while (value == SENTINEL);

// use `value` here

      

        
        
        
      

    

The expansion is longer than necessary to make retries unlikely, ensuring that the vast majority of items are valid (for example, in the example above, only 1/16 of the lookups will "fail" and this rate can be reduced further, such as 64) ... You can even use the "branch prediction" hint (eg __builtin_expect

in GCC ) on the check to make the compiler code optimal for the case value != SENTINEL

, which is hopefully the general case.

It is rather a trade-off between memory and speed.

Just a few ideas to complement other good answers:

• What percentage of the time is spent on modulo and how do you know what that percentage is? I'm only asking because sometimes people say that something is terribly slow when in fact it's less than 10% of the time, and they only think it's big because they only use the silly profiler for their own time. (I find it hard to imagine that modulo operation is time consuming compared to a random number generator.)

• When is the number of buckets known? If it doesn't change too often, you can write a generator program. When the number of buckets changes, automatically print a new program, compile, link and use it for bulk execution. This way the compiler will know the number of buckets.

• Have you considered using a quasi-random number generator as opposed to a pseudo-random generator? This can give you better integration fidelity across multiple samples.

• Could the number of buckets be reduced without compromising integration accuracy too much?

Dbaupp jaggedness warnings that can be side-stepped by deviating scaling values ​​at least M*(2^64/M)

(before the module is accepted).
If M

no more than 32 bits can be represented, you can get more than one value less M

by re-multiplying (see David Eisenstat's answer) or divmod; alternatively, you can use bitwise operations to extract bit patterns long enough for M

, again rejecting values ​​no less than M

.
(I would be surprised that the module is not dwarfed in time / cycle / power consumption by generating random numbers.)

To feed the bucket, you can use std::

binomial_distribution to feed each bucket directly, rather than feeding the bucket one sample per sample:

The following might help:

int nrolls = 60; // number of experiments
const std::size_t N = 6;
unsigned int bucket[N] = {};

std::mt19937 generator(time(nullptr));

for (int i = 0; i != N; ++i) {
    double proba = 1. / static_cast<double>(N - i);
    std::binomial_distribution<int> distribution (nrolls, proba);
    bucket[i] = distribution(generator);
    nrolls -= bucket[i];
}

      

        
        
        
      

    

Live example

Instead of integer division, you can use fixed point math, i.e. integer multiplication and bitrate. Let's say if your prng () returns values ​​in the range 0-65535 and you want this quantized range to be in the range 0-99, then you do (prng () * 100) -> 16. Just make sure the multiplication does not overflow your integer type, so you may need to change the result of prng () to the right. Note that this map is better than modulo because it preserves a uniform distribution.