Случайные числа от 1 до 15

Question

Я генерирую много случайных чисел, которые должны быть в диапазоне от 1 до 15 (включены) в C ++.Конечно, я могу генерировать zillons std::uniform_int_distribution<std::mt19937::result_type> random(1, 15);, но это пустая трата, так как этот твистер mersenn генерирует 32 бита (или даже 64 с использованием mt19937_64) случайных значений, и я бы оставил только 4 бита и выбросил бы все остальные, и вВ моем случае производительность является проблемой, и генерация случайных чисел вносит существенный вклад.

Таким образом, моя идея заключалась в том, чтобы сгенерировать, например, одно 64-битное случайное значение в диапазоне от 0 до 2 ^ 64-1 и выбрать 4 бита.среди них.Проблема в том, что я не могу найти способ сгенерировать значения от 1 до 15. Пример:

unsigned long long int r = uniform(generator); // between 0 and 2^64-1
unsigned int r1 = (r+1)&15;     // first desired random value
unsigned int r2 = ((r>>4)+1)&15; //second desired random value 
unsigned int r3 = ((r>>8)+1)&15; //third desired random value 
...

Здесь эта версия, конечно, не работает: несмотря на +1, сгенерированныйзначения по-прежнему находятся в диапазоне от 0 до 15 (поскольку, если r&15 равно 0xb1111, то добавление 1 приводит к результату 0xb0000).

Кроме того, я хотел бы, чтобы распределение оставалось равномерным (например,Мне бы не хотелось, чтобы смещение младшего значащего бита происходило чаще, что может иметь место с чем-то вроде (r&15+1)|((r&15 +1) >> 4), поскольку значение 0xb0001 встречается дважды чаще).

Answer 1

вместо

std::mt19937 gen(seed);
std::uniform_int_distribution<> dis(1, 15);

auto r1 = dis(gen);
auto r2 = dis(gen);
auto r3 = dis(gen);
auto r4 = dis(gen);

Вы можете сделать:

std::mt19937 gen(seed);
std::uniform_int_distribution<> dis(0, 15 * 15 * 15 * 15 - 1); // Assuming int at least 16 bits

auto r = dis(gen);

auto r1 = r % 15 + 1; r /= 15;
auto r2 = r % 15 + 1; r /= 15;
auto r3 = r % 15 + 1; r /= 15;
auto r4 = r + 1;

Быстрый тест (вторая версия в 2,5 раза быстрее первой)

Answer 2

Как уже упоминалось Дэвид Шварц в разделе комментариев

Вы можете просто выбросить любые нулевые значения.Это даст вам в среднем около 15 случайных значений от каждого 64-битного случайного ввода.

Реализация простой техники выборки отклонения для этого конкретного случая использования вместо использования более общего std::uniform_int_distributionбыть более эффективным (например, см. этот Quick Bench , сравнивающий стандартный класс со следующим).

class uniform_1_to_15_distribution
{
    uint64_t value_{};        // So that one could use std::mt19937_64 too
public:
    uniform_1_to_15_distribution() = default;

    template <class Gen> int operator() (Gen &g)
    {
        for (;;)
        {
            // When all the bits have been used (or only useless zeroes remain)
            if( value_ == uint64_t{} )
            {
                // Get a new value from the generator
                value_ = g();
                continue;
            }

            // Pick the 4 LS bits
            int ret = value_ & 0xF;

            // "Consume" the state
            value_ >>= 4;

            // Reject 0. Only value in range [1, 15] are accepted.
            if ( ret == 0 )
            {
                continue;
            }        
            return ret;
        }
    }
};

Распределение можно протестировать ЗДЕСЬ .