Генерация случайных чисел в диапазонах из 32 байтов случайных данных, без библиотеки bignum

Question

У меня 32 байта случайных данных.

Я хочу генерировать случайные числа в диапазоне переменных от 0-9 до 0-100.

Если бы я использовал арифметическую библиотеку произвольной точности (bignum) и рассматривал 32 байта как большое число, я мог бы просто сделать:

random = random_source % range;
random_source = random_source / range;

так часто, как мне нравилось (с разными диапазонами), пока произведение диапазонов не приблизится к 2 ^ 256.

Есть ли способ сделать это, используя только целочисленную арифметику (фиксированного размера)?

Answer 1

Конечно, вы можете сделать это, выполнив базовое деление на 256 длин (или умножение с повышением). Это похоже на длинное деление, которое вы выучили в начальной школе, но с байтами вместо цифр. Это включает в себя создание каскада делений и остатков для каждого байта по очереди. Обратите внимание, что вам также необходимо знать, как вы потребляете большое число, и что по мере того, как вы его потребляете, и оно становится все меньше, увеличивается смещение относительно больших значений в диапазоне. Например, если у вас осталось только 110, и вы запросили rnd (100), значения 0-9 будут на 10% более вероятными, чем 10-99 каждое.

Но для этого вам не нужны методы bignum, вы можете использовать идеи сжатия арифметического кодирования, где вы строите единственное число, фактически не имея дело со всем этим.

Если вы начнете читать 4 байта в неподписанный буфер uint_32, он будет иметь диапазон 0..4294967295, не включающий максимум 4294967296. Я буду называть это синтезированное значение «переносом вперед», и это исключение Максимальное значение также важно для записи.

[Для простоты вы могли бы начать с чтения 3 байтов в ваш буфер, генерируя максимум 16M. Это позволяет избежать необходимости иметь дело со значением 4G, которое нельзя хранить в 32-разрядном целом числе.]

Есть 2 способа использовать это, оба с последствиями точности:

Поток вниз:

У вашего диапазона по модулю. По модулю ваш случайный ответ. Результат деления - ваш новый перенос и имеет меньший диапазон.
Скажем, вы хотите 0..99, то есть по модулю на 100, ваша верхняя часть имеет максимальный диапазон 42949672 (4294967296/100), который вы переносите для следующего случайного запроса Мы не можем вставить еще один байт ...
Скажем, теперь вы хотите 0,9, то есть по модулю 10, и теперь ваша верхняя часть имеет диапазон 0..4294967 (42949672/100)
Так как max меньше 16M, теперь мы можем ввести следующий байт. Умножьте его на текущий максимум 4294967 и добавьте к переносу. Макс также умножается на 256 -> 1099511552

Этот метод имеет небольшое смещение к небольшим значениям, так как 1 во время «следующего максимума», доступный диапазон значений не будет полным диапазоном, потому что последнее значение усекается, но при выборе сохранения 3-4 хорошие байты в максимуме, это смещение сведено к минимуму. Это будет происходить только при максимуме 1 в 16 миллионов раз.

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

Поток вверх:
Скажи, что хочешь 0..99
Разделите ваш максимум на диапазон, чтобы получить следующий максимум, и разделите перенос на следующий максимум. Теперь ваше случайное число находится в результате деления, а остаток формирует значение, которое вы переносите, чтобы получить следующее случайное число.
Когда nextmax становится меньше 16M, просто умножьте и nextmax, и ваш перенос на 256 и добавьте следующий байт.
Недостатком этого метода является то, что в зависимости от деления, используемого для генерации nextmax, результат с максимальным значением (т. Е. 99 или 9) сильно смещен, ИЛИ иногда вы будете генерировать завышенное значение (100) - это зависит от того, округлите ли вы или вниз, делая первое деление.

Вычислительная стоимость здесь снова составляет 2 деления, при условии, что оптимизатор компилятора смешивает операции div и mod. Умножение на 256 быстро.

В обоих случаях вы можете сказать, что если значение переноса входного сигнала находится в этом «высоком диапазоне смещения», то вы будете выполнять другую технику. Вы могли бы даже колебаться между методами - используйте второй в предпочтении, но если он генерирует завышенное значение, то используйте первый метод, хотя сама по себе вероятность состоит в том, что оба метода будут смещать для одинаковых входных случайных потоков при переносе вперед значение около макс. Это смещение можно уменьшить, заставив второй метод генерировать -1 как выход за пределы допустимого диапазона, но каждое из этих исправлений добавляет дополнительный шаг умножения.

Обратите внимание, что в арифметическом кодировании эта зона переполнения эффективно отбрасывается при извлечении каждого символа. Во время декодирования гарантируется, что значения этих краев не произойдут, и это способствует небольшому субоптимальному сжатию.

Answer 2

/*  The 32 bytes in data are treated as a base-256 numeral following a "." (a
    radix point marking where fractional digits start).  This routine
    multiplies that numeral by range, updates data to contain the fractional
    portion of the product, and returns the integer portion.

    8-bit bytes are assumed, or "t /= 256" could be changed to
    "t >>= CHAR_BIT". But then you have to check the sizes of int
    and unsigned char to consider overflow.
*/
int r(int range, unsigned char *data)
{
    // Start with 0 carried from a lower position.
    int t = 0;

    // Iterate through each byte.
    for (int i = 32; 0 < i;)
    {
        --i;

        // Multiply next byte by our multiplier and add the carried data.
        t = data[i] * range + t;

        // Store the low bits of the result.
        data[i] = t;

        // Carry the high bits of the result to the next position.
        t /= 256;
    }

    // Return the bits that carried out of the multiplication.
    return t;
}