Генерация случайных целых чисел с определенным максимумом

Question

Я хочу сгенерировать однородные целые числа, которые удовлетворяют 0 <= result <= maxValue.

У меня уже есть генератор, который возвращает однородные значения во всем диапазоне встроенных целочисленных типов без знака.Давайте назовем методы для этого byte Byte(), ushort UInt16(), uint UInt32() и ulong UInt64().Предположим, что результат этих методов идеально равномерно.

Подпись методов, которые я хочу, это uint UniformUInt(uint maxValue) и ulong UniformUInt(ulong maxValue).

То, что я ищудля:

1. Корректность Я бы предпочел, чтобы возвращаемые значения были распределены в заданном интервале.Но допустимо небольшое смещение , если оно значительно повышает производительность.Под этим я подразумеваю смещение порядка, позволяющего различать с вероятностью 2/3 при 2 ^ 64 значениях.Он должен работать правильно для любого maxValue.
2. Производительность Метод должен быть быстрым.
3. Эффективность Метод действительно использует небольшую необработанную случайность, поскольку в зависимости от базового генератора генерация необработанных байтов может быть дорогостоящей.Потеря нескольких битов - это хорошо, но, скажем, использование 128 битов для генерации одного числа, вероятно, чрезмерно.

Также возможно кэшировать некоторую оставшуюся случайность из предыдущего вызова в некоторых переменных-членах.

Будьте осторожны с переполнением int и поведением обёртывания.

У меня уже есть решение (я опубликую его как ответ), но оно немного уродливо для моих вкусов.Так что я хотел бы получить идеи для лучших решений.

Было бы неплохо также посоветовать, как выполнить модульное тестирование с большими maxValue s, поскольку я не могу сгенерировать гистограмму с 2 ^ 64 сегментами и 2^ 74 случайных значений.Другое осложнение заключается в том, что с некоторыми ошибками только некоторые дистрибутивы maxValue сильно смещены, а другие лишь незначительно.

Answer 1

Как насчет этого как универсального решения? Алгоритм основан на алгоритме Java nextInt , отклоняющем любые значения, которые могут привести к неравномерному распределению. До тех пор, пока выходные данные вашего UInt32 метода абсолютно одинаковы, это тоже должно быть.

uint UniformUInt(uint inclusiveMaxValue)
{
    unchecked
    {
        uint exclusiveMaxValue = inclusiveMaxValue + 1;

        // if exclusiveMaxValue is a power of two then we can just use a mask
        // also handles the edge case where inclusiveMaxValue is uint.MaxValue
        if ((exclusiveMaxValue & (~exclusiveMaxValue + 1)) == exclusiveMaxValue)
            return UInt32() & inclusiveMaxValue;

        uint bits, val;
        do
        {
            bits = UInt32();
            val = bits % exclusiveMaxValue;

            // if (bits - val + inclusiveMaxValue) overflows then val has been
            // taken from an incomplete chunk at the end of the range of bits
            // in that case we reject it and loop again
        } while (bits - val + inclusiveMaxValue < inclusiveMaxValue);

        return val;
    }
}

Теоретически процесс отклонения может продолжаться бесконечно; на практике производительность должна быть довольно хорошей. Трудно предложить какие-либо общеприменимые оптимизации, не зная (a) ожидаемых моделей использования и (b) характеристик производительности вашего базового ГСЧ.

Например, если большинство вызывающих абонентов будут указывать максимальное значение <= 255, тогда может не иметь смысла каждый раз запрашивать четыре байта случайности. С другой стороны, выигрыш в производительности, связанный с запросом меньшего количества байтов, может быть перевешен дополнительными затратами на проверку того, сколько на самом деле вам нужно. (И, конечно, как только вы <em>действительно получите конкретную информацию, вы можете продолжать оптимизировать и тестировать, пока ваши результаты не станут достаточно хорошими.)

Answer 2

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

Из OQ я получаю, что

1. Биты энтропии очень дороги
2. Все остальное следует считать дорогим, но не так, как энтропия.

Моя идея состоит в том, чтобы использовать двоичные цифры наполовину, четверть ... пространство maxValue, пока оно не уменьшится до числа. Что-то вроде

Я буду использовать maxValue = 333 (десятичное число) в качестве примера и приму функцию getBit(), которая случайным образом возвращает 0 или 1

offset:=0
space:=maxValue

while (space>0)

  //Right-shift the value, keeping the rightmost bit this should be 
  //efficient on x86 and x64, if coded in real code, not pseudocode
  remains:=space & 1
  part:=floor(space/2)
  space:=part

  //In the 333 example, part is now 166, but 2*166=332 If we were to simply chose one
  //half of the space, we would be heavily biased towards the upper half, so in case
  //we have a remains, we consume a bit of entropy to decide which half is bigger

  if (remains)
    if(getBit())
      part++;

  //Now we decide which half to chose, consuming a bit of entropy
  if (getBit())
    offset+=part;

  //Exit condition: The remeinind number space=0 is guaranteed to be met
  //In the 333 example, offset will be 0, 166 or 167, remaining space will be 166
}

randomResult:=offset

getBit() может либо исходить из вашего источника энтропии, если он основан на битах, либо потреблять n бит энтропии сразу при первом вызове (очевидно, что n является оптимальным для вашего источника энтропии), и сдвигать его до пустой.

Answer 3

Мое текущее решение. Немного некрасиво на мой вкус. Он также имеет два деления на сгенерированное число, что может отрицательно повлиять на производительность (я еще не профилировал эту часть).

uint UniformUInt(uint maxResult)
{
    uint rand;
    uint count = maxResult + 1;

    if (maxResult < 0x100)
    {
        uint usefulCount = (0x100 / count) * count;
        do
        {
            rand = Byte();
        } while (rand >= usefulCount);
        return rand % count;
    }
    else if (maxResult < 0x10000)
    {
        uint usefulCount = (0x10000 / count) * count;
        do
        {
            rand = UInt16();
        } while (rand >= usefulCount);
        return rand % count;
    }
    else if (maxResult != uint.MaxValue)
    {
        uint usefulCount = (uint.MaxValue / count) * count;//reduces upper bound by 1, to avoid long division
        do
        {
            rand = UInt32();
        } while (rand >= usefulCount);
        return rand % count;
    }
    else
    {
        return UInt32();
    }
}

ulong UniformUInt(ulong maxResult)
{
    if (maxResult < 0x100000000)
        return InternalUniformUInt((uint)maxResult);
    else if (maxResult < ulong.MaxValue)
    {
        ulong rand;
        ulong count = maxResult + 1;
        ulong usefulCount = (ulong.MaxValue / count) * count;//reduces upper bound by 1, since ulong can't represent any more
        do
        {
            rand = UInt64();
        } while (rand >= usefulCount);
        return rand % count;
    }
    else
        return UInt64();
}