Почему люди говорят, что при использовании генератора случайных чисел наблюдается смещение по модулю?

Я видел, как этот вопрос задавали много, но никогда не видел истинного конкретного ответа на него. Итак, я собираюсь опубликовать один здесь, который, надеюсь, поможет людям понять, почему именно есть «смещение по модулю» при использовании генератора случайных чисел, напримерrand() в C ++.

Ответы на вопрос(9)

@ user1413793 правильно о проблеме. да, для небольших значенийn и большие значенияRAND_MAXСмещение по модулю может быть очень маленьким. Но использование шаблона смещения означает, что вы должны учитывать смещение каждый раз, когда вычисляете случайное число и выбираете разные шаблоны для разных случаев. И если вы сделаете неправильный выбор, ошибки, которые он вносит, неуловимы и почти невозможны для модульного тестирования. По сравнению с использованием только соответствующего инструмента (например,arc4random_uniform), это дополнительная работа, а не меньшая. Выполнение большей работы и получение худшего решения - это ужасная разработка, особенно если делать это правильно каждый раз на большинстве платформ легко.

К сожалению, реализации решения все неверны или менее эффективны, чем должны быть. (Каждое решение имеет различные комментарии, объясняющие проблемы, но ни одно из решений не было исправлено для их решения.) Это может сбить с толку случайного ищущего ответа, поэтому я предоставляю здесь заведомо хорошую реализацию.

Опять же, лучшее решение просто использоватьarc4random_uniform на платформах, которые предоставляют его, или аналогичное решение для вашей платформы (например,Random.nextInt на Java). Он будет делать правильные вещи без затрат на код. Это почти всегда правильный вызов ма, ке.

Если у вас нетarc4random_uniform, тогда вы можете использовать возможности с открытым исходным кодом, чтобы увидеть, как именно это реализовано поверх более широкого диапазона ГСЧ (ar4random в этом случае, но аналогичный подход может также работать поверх других ГСЧ).

ЗдесьРеализация OpenBSD:

/*
 * Calculate a uniformly distributed random number less than upper_bound
 * avoiding "modulo bias".
 *
 * Uniformity is achieved by generating new random numbers until the one
 * returned is outside the range [0, 2**32 % upper_bound).  This
 * guarantees the selected random number will be inside
 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
 * after reduction modulo upper_bound.
 */
u_int32_t
arc4random_uniform(u_int32_t upper_bound)
{
    u_int32_t r, min;

    if (upper_bound < 2)
        return 0;

    /* 2**32 % x == (2**32 - x) % x */
    min = -upper_bound % upper_bound;

    /*
     * This could theoretically loop forever but each retry has
     * p > 0.5 (worst case, usually far better) of selecting a
     * number inside the range we need, so it should rarely need
     * to re-roll.
     */
    for (;;) {
        r = arc4random();
        if (r >= min)
            break;
    }

    return r % upper_bound;
}

Стоит отметить последний комментарий коммита по этому коду для тех, кому необходимо реализовать похожие вещи:

Change arc4random_uniform() to calculate 2**32 % upper_bound'' as -upper_bound % upper_bound''. Simplifies the code and makes it the same on both ILP32 and LP64 architectures, and also slightly faster on LP64 architectures by using a 32-bit remainder instead of a 64-bit remainder.

Pointed out by Jorden Verwer on [email protected] ok deraadt; no objections from djm or otto

Реализация Java также легко доступна (см. Предыдущую ссылку):

public int nextInt(int n) {
   if (n <= 0)
     throw new IllegalArgumentException("n must be positive");

   if ((n & -n) == n)  // i.e., n is a power of 2
     return (int)((n * (long)next(31)) >> 31);

   int bits, val;
   do {
      , bits = next(31);
       val = bits % n;
   } while (bits - val + (n-1) < 0);
   return val;
 }
 08 мар. 2019 г., 22:01
Я в замешательстве. Isn & APOS; т-upper_bound % upper_bound == 0??
 09 авг. 2016 г., 03:51
@rmalayter В iOS и OS X arc4random читает из / dev / random, что является энтропией высшего качества в системе. (Название «arc4» в названии является историческим и сохранено для совместимости.)
 08 мар. 2019 г., 22:46
@JonMcClung Это очень хороший вопрос, но ответ (на удивление) - нет. Это uint32_t, так что еслиx больше 2 ^ 31,-x фактически положительный (поскольку в этом контексте он оценивается как целое число со знаком). О, слава неподписанным & # x2026; Например, -2147483650, оцененный как UInt32, равен 2147483646, и -4294967290 равен 6.
 09 авг. 2016 г., 03:38
Обратите внимание, что еслиarcfour_random()  фактически использует в своей реализации настоящий алгоритм RC4, вывод определенно будет иметь некоторую предвзятость. Надеемся, что авторы вашей библиотеки переключились на использование лучшего CSPRNG за тем же интерфейсом. Я помню, что одна из BSD теперь фактически использует алгоритм ChaCha20 для реализацииarcfour_random(), Подробнее о смещениях на выходе RC4, которые делают его бесполезным для безопасности или других важных приложений, таких как видеопокер:blog.cryptographyengineering.com/2013/03/…
 09 авг. 2016 г., 04:36
@Rob_Napier приятно знать, но/dev/random также использовал RC4 на некоторых платформах в прошлом (Linux использует SHA-1 в режиме счетчика). К сожалению, man-страницы, которые я нашел с помощью поиска, показывают, что RC4 все еще используется на различных платформах, которые предлагаютarc4random (хотя фактический код может отличаться).

ет фон Неймана, который теоретически должен устранить любые смещения в процессе генерации случайных чисел. Более подробную информацию можно найти на (http://en.wikipedia.org/wiki/Fair_coin)

int unbiased_random_bit() {    
    int x1, x2, prev;
    prev = 2;
    x1 = rand() % 2;
    x2 = rand() % 2;

    for (;; x1 = rand() % 2, x2 = rand() % 2)
    {
        if (x1 ^ x2)      // 01 -> 1, or 10 -> 0.
        {
            return x2;        
        }
        else if (x1 & x2)
        {
            if (!prev)    // 0011
                return 1;
            else
                prev = 1; // 1111 -> continue, bias unresolved
        }
        else
        {
            if (prev == 1)// 1100
                return 0;
            else          // 0000 -> continue, bias unresolved
                prev = 0;
        }
    }
}
 27 мар. 2016 г., 13:25
@ Рик хм. Логическим продолжением метода фон Неймана для устранения смещения по модулю при генерации случайного числа, скажем, от 1 до 100, будет: A) вызовrand() % 100 100 раз. Б) если все результаты разные, возьмите первый. C) в противном случае, GOTO A. Это будет работать, но с ожидаемым числом итераций около 10 ^ 42, вам придется быть довольно терпеливым. И бессмертный.
 28 мар. 2016 г., 14:58
@MarkAmery Действительно, это должно работать. Просматривая этот алгоритм, хотя он неправильно реализован. Первое еще должно быть:else if(prev==2) prev= x1; else { if(prev!=x1) return prev; prev=2;}
 05 авг. 2015 г., 15:06
Это не относится к смещению по модулю. Этот процесс может быть использован для устранения смещения в битовом потоке. Однако для перехода от потока битов к равномерному распределению от 0 до n, где n не меньше, чем степень двух, требуется адресация по модулю смещения. Таким образом, это решение не может устранитьany bias in the random number generation process.
Решение Вопроса

rand() является генератором псевдослучайных чисел, который выбирает натуральное число от 0 доRAND_MAX, которая является константой, определенной вcstdlib (видеть этостатья для общего обзораrand()).

Что произойдет, если вы захотите сгенерировать случайное число, скажем, между 0 и 2? Для объяснения, скажемRAND_MAX 10, и я решил сгенерировать случайное число от 0 до 2, позвонивrand()%3, Тем не мение,rand()%3 не производит числа между 0 и 2 с равной вероятностью!

When rand() returns 0, 3, 6, or 9, rand()%3 == 0, Следовательно, P (0) = 4/11

When rand() returns 1, 4, 7, or 10, rand()%3 == 1, Следовательно, P (1) = 4/11

When rand() returns 2, 5, or 8, rand()%3 == 2, Следовательно, P (2) =3/11

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

когда жеrand()%n вернуть диапазон чисел от 0 до n-1 с равной вероятностью? когдаRAND_MAX%n == n - 1, В этом случае наряду с нашим более ранним предположениемrand() возвращает число от 0 доRAND_MAX с равной вероятностью классы по модулю n также будут равномерно распределены.

Итак, как мы решаем эту проблему? Грубый способ состоит в том, чтобы генерировать случайные числа, пока вы не получите число в нужном диапазоне:

int x; 
do {
    x = rand();
} while (x >= n);

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

Более эффективный подход на основе формул состоит в том, чтобы взять некоторый большой диапазон с длиной, кратнойn, лайкRAND_MAX - RAND_MAX % nпродолжайте генерировать случайные числа, пока не получите одно из лежащих в диапазоне, а затем возьмите модуль:

int x;

do {
    x = rand();
} while (x >= (RAND_MAX - RAND_MAX % n));

x %= n;

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

Работы цитируются и читаем дальше:

CPlusPlus Reference

Eternally Confuzzled

 28 окт. 2017 г., 16:58
X & gt; = RM - (((RM% N) + 1)% N)
 31 окт. 2017 г., 13:08
Я разместил дополнительный ответ, подробно объясняя проблему и предоставив пример решения кода.
 19 июл. 2016 г., 10:04
Еще один способ мышления о_RAND_MAX%n == n - 1_ является(RAND_MAX + 1) % n == 0, При чтении кода я склонен понимать% something == 0 как & # x201C; равномерно делится & # x201D; более легко, чем другие способы его расчета.Of course, if your C++ stdlib has RAND_MAX as the same value as INT_MAX, (RAND_MAX + 1) surely wouldn't work; so Mark's calculation remains the safest implementation.
 28 окт. 2017 г., 16:56
Я могу быть придирчив, но если цель состоит в том, чтобы уменьшить потерянные биты, мы могли бы немного улучшить это для граничного условия, где RAND_MAX (RM) только на 1 меньше, чем равное делению на N. В этом сценарии нет необходимости тратить биты на выполнение X & gt; = (RM - RM% N)), которое имеет небольшое значение для малых значений N, но становится более значительным для больших значений N. Как упомянуто Слиппом Д. Томпсоном, существует решение, которое будет работать только когда INT_MAX (IM) & gt; RAND_MAX но ломается, когда они равны. Однако для этого существует простое решение: мы можем изменить расчет X & gt; = (RM - RM% N) следующим образом:
 30 авг. 2017 г., 14:13
очень хороший ответ!

ние.

Update

Мы могли бы сделать код быстрым, если бы мы искали x в диапазоне, кратномn.

// Assumptions
// rand() in [0, RAND_MAX]
// n in (0, RAND_MAX]

int x; 

// Keep searching for an x in a range divisible by n 
do {
    x = rand();
} while (x >= RAND_MAX - (RAND_MAX % n)) 

x %= n;

Вышеуказанный цикл должен быть очень быстрым, скажем, в среднем за 1 итерацию.

 13 июн. 2012 г., 09:59
Тьфу :-P конвертирование в двойное, затем умножение на MAX_UPPER_LIMIT / RAND_MAX намного чище и работает лучше.
 17 июн. 2012 г., 13:31
@boycy: ты упустил суть. Если количество значений, которыеrand() может вернуться не кратноnто, что бы вы ни делали, вы неизбежно получите «смещение по модулю», если только вы не отбросите некоторые из этих значений. user1413793 объясняет это приятно (хотя решение, предложенное в этом ответе, действительно отвратительно).
 13 окт. 2012 г., 07:07
Оператор приоритет делаетRAND_MAX+1 - (RAND_MAX+1) % n работать правильно, но я все еще думаю, что это должно быть написано какRAND_MAX+1 - ((RAND_MAX+1) % n) для ясности.
 18 июн. 2012 г., 14:26
@TonyK мои извинения, я упустил момент. Не думал достаточно усердно и думал, что смещение будет применяться только к методам, использующим явную операцию модуля. Спасибо за исправление :-)
 06 нояб. 2012 г., 23:04
Это не сработает, еслиRAND_MAX == INT_MAX (as it does on most systems), Смотрите мой второй комментарий к @ user1413793 выше.
Definition

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

Этого смещения особенно трудно избежать в вычислениях, где числа представлены в виде цепочек битов: 0 и 1. Найти действительно случайные источники случайности также чрезвычайно сложно, но это выходит за рамки этого обсуждения.For the remainder of this answer, assume that there exists an unlimited source of truly random bits.

Problem Example

Рассмотрим моделирование броска кубика (от 0 до 5) с использованием этих случайных битов. Есть 6 возможностей, поэтому нам нужно достаточно бит для представления числа 6, которое составляет 3 бита. К сожалению, 3 случайных бита дают 8 возможных результатов:

000 = 0, 001 = 1, 010 = 2, 011 = 3
100 = 4, 101 = 5, 110 = 6, 111 = 7

Мы можем уменьшить размер набора результатов ровно до 6, взяв значение по модулю 6, однако это представляетmodulo bias проблема:110 дает 0, и111 дает 1.This die is loaded.

Potential Solutions Approach 0:

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

Approach 1:

Вместо использования модуля, наивное, но математически правильное решение - отбросить результаты, которые дают110 а также111 и просто попробуйте еще раз с 3 новыми битами. К сожалению, это означает, что есть25% chance on each roll that a re-roll will be required, including each of the re-rolls самих себя. Это явно непрактично для всех, кроме самого тривиального использования.

Approach 2:

Используйте больше битов: вместо 3 битов используйте 4. Это даст 16 возможных результатов. Конечно, перекатывание в любое время, когда результат больше 5, ухудшает ситуацию (10/16 = 62,5%), так что само по себе это не поможет.

Обратите внимание, что 2 * 6 = 12 & lt; 16, так что мы можем безопасно принять любой результат, меньший 12, и уменьшить его по модулю 6, чтобы равномерно распределить результаты. Остальные 4 результата должны быть отброшены, а затем повторно свернуты, как в предыдущем подходе.

Сначала звучит хорошо, но давайте проверим математику:

4 discarded results / 16 possibilities = 25%

In this case, 1 extra bit didn't help at all!

Этот результат вызывает сожаление, но давайте попробуем еще раз с 5 битами:

32 % 6 = 2 discarded results; and
2 discarded results / 32 possibilities = 6.25%

Определенное улучшение, но не достаточно хорошее во многих практических случаях. Хорошая новость в том,adding more bits will never increase the chances of needing to discard and re-roll, Это верно не только для игры в кости, но и во всех случаях.

Как продемонстрированоhowever, adding an 1 extra bit may not change anything. Фактически, если мы увеличим наш бросок до 6 битов, вероятность останется 6,25%.

Это вызывает 2 дополнительных вопроса:

If we add enough bits, is there a guarantee that the probability of a discard will diminish? How many bits are enough in the general case? General Solution

К счастью, ответ на первый вопрос - да. Проблема с 6 состоит в том, что 2 ^ x mod 6 переворачивается между 2 и 4, которые по совпадению кратны 2 друг от друга, так что для четного x & gt; 1,

[2^x mod 6] / 2^x == [2^(x+1) mod 6] / 2^(x+1)

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

Without offering further proof, in general using double the number of bits required will provide a smaller, usually insignificant, chance of a discard.

Proof of Concept

Вот пример программы, которая использует libcrypo OpenSSL для предоставления случайных байтов. При компиляции обязательно указывайте ссылку на библиотеку с помощью-lcrypto который большинство должно иметь в наличии.

#include <iostream>
#include <assert.h>
#include <limits>
#include <openssl/rand.h>

volatile uint32_t dummy;
uint64_t discardCount;

uint32_t uniformRandomUint32(uint32_t upperBound)
{
    assert(RAND_status() == 1);
    uint64_t discard = (std::numeric_limits<uint64_t>::max() - upperBound) % upperBound;
    uint64_t randomPool = RAND_bytes((uint8_t*)(&randomPool), sizeof(randomPool));

    while(randomPool > (std::numeric_limits<uint64_t>::max() - discard)) {
        RAND_bytes((uint8_t*)(&randomPool), sizeof(randomPool));
        ++discardCount;
    }

    return randomPool % upperBound;
}

int main() {
    discardCount = 0;

    const uint32_t MODULUS = (1ul << 31)-1;
    const uint32_t ROLLS = 10000000;

    for(uint32_t i = 0; i < ROLLS; ++i) {
        dummy = uniformRandomUint32(MODULUS);
    }
    std::cout << "Discard count = " << discardCount << std::endl;
}

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

 22 дек. 2017 г., 04:31
Я действительно надеюсь, что никто не слепо скопировал вашу единую случайную реализацию.randomPool = RAND_bytes(...) линия всегда приведет кrandomPool == 1 из-за утверждения. этоalways приводит к сбросу и повторному броску. Я думаю, что вы хотели объявить в отдельной строке. Следовательно, это заставило ГСЧ вернуться с1 за каждую итерацию.
 22 дек. 2017 г., 04:37
Чтобы быть ясным,randomPool всегда буду оценивать1 в соответствии с OpenSSLdocumentation for RAND_bytes() так как он всегда будет успешным благодаряRAND_status() утверждение.

RAND_MAX ценность3 (в действительности это должно быть намного выше, чем это, но смещение все еще существует) из этих вычислений имеет смысл, что есть смещение:

1 % 2 = 1 2 % 2 = 0 3 % 2 = 1 random_between(1, 3) % 2 = more likely a 1

В этом случае% 2 это то, что вы не должны делать, когда вы хотите случайное число между0 а также1, Вы можете получить случайное число между0 а также2 при выполнении% 3 хотя, потому что в этом случае:RAND_MAX это кратное3.

Another method

уществует гораздо проще, но, чтобы добавить к другим ответам, вот мое решение, чтобы получить случайное число между0 а такжеn - 1, такn разные возможности, без предвзятости.

the number of bits (not bytes) needed to encode the number of possibilities is the number of bits of random data you'll need encode the number from random bits if this number is >= n, restart (no modulo).

На самом деле случайные данные получить нелегко, поэтому зачем использовать больше битов, чем нужно.

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

next: n

    | bitSize r from to |
    n < 0 ifTrue: [^0 - (self next: 0 - n)].
    n = 0 ifTrue: [^nil].
    n = 1 ifTrue: [^0].
    cache isNil ifTrue: [cache := OrderedCollection new].
    cache size < (self randmax highBit) ifTrue: [
        Security.DSSRandom default next asByteArray do: [ :byte |
            (1 to: 8) do: [ :i |    cache add: (byte bitAt: i)]
        ]
    ].
    r := 0.
    bitSize := n highBit.
    to := cache size.
    from := to - bitSize + 1.
    (from to: to) do: [ :i |
        r := r bitAt: i - from + 1 put: (cache at: i)
    ].
    cache removeFrom: from to: to.
    r >= n ifTrue: [^self next: n].
    ^r

принятый ответ указывает «модуль смещения»; коренится в низкой стоимостиRAND_MAX, Он использует чрезвычайно маленькое значениеRAND_MAX (10), чтобы показать, что если RAND_MAX было 10, то вы пытались сгенерировать число от 0 до 2, используя%, следующие результаты будут:

rand() % 3   // if RAND_MAX were only 10, gives
output of rand()   |   rand()%3
0                  |   0
1                  |   1
2                  |   2
3                  |   0
4                  |   1
5                  |   2
6                  |   0
7                  |   1
8                  |   2
9                  |   0

Таким образом, имеется 4 выхода по 0 '(шанс 4/10) и только 3 выхода по 1 и 2 (шансы 3/10 каждый).

Так что это предвзято. Меньшие числа имеют больше шансов выйти.

But that only shows up so obviously when RAND_MAX is small, Или, более конкретно, когда число, на которое вы модифицируете, велико по сравнению сRAND_MAX.

Гораздо лучшее решение, чемlooping (что является безумно неэффективным и даже не следует предлагать) заключается в использовании PRNG с гораздо большим выходным диапазоном.Мерсенн Твистер алгоритм имеет максимальный выход 4 294 967 295. такое делатьMersenneTwister::genrand_int32() % 10 для всех намерений и целей, будут равномерно распределены, и эффект смещения по модулю почти исчезнет.

 08 апр. 2015 г., 03:08
ЕслиRAND_MAX достаточно больше, чем число, которое вы модифицируете, количество раз, которое вам нужно для восстановления случайного числа, исчезающе мало и не влияет на эффективность. Я говорю, продолжайте цикл, пока вы тестируете по наибольшему кратномуn а не простоn как предложено принятым ответом.
 16 апр. 2013 г., 06:08
Поскольку самое высокое значение нечетно,MT::genrand_int32()%2 выбирает 0 (50 + 2.3e-8)% времени и 1 (50 - 2.3e-8)% времени. Если вы не строите RGN в казино (для которого вы, вероятно, будете использовать RGN с гораздо большим диапазоном), любой пользователь не будет замечать дополнительных 2,3–8% времени. Вы говорите о числах, слишком малых, чтобы иметь значение здесь.
 user141379316 апр. 2013 г., 05:09
Ваш более эффективен, и, вероятно, это правда, что если RAND_MAX значительно больше, чем число, на которое вы модифицируете, то ваше все равно будет смещено. Конечно, это все генераторы псевдослучайных чисел, и это само по себе - отдельная тема, но если вы предполагаете, что генератор случайных чисел полностью, ваш путь все еще смещает более низкие значения.
 03 июл. 2013 г., 18:22
Цикл является лучшим решением. Это не «безумно неэффективно»; требуя менее двух итераций в худшем среднем случае. Используя высокийRAND_MAX значение уменьшит смещение по модулю, но не устранит его. Циклы будут.

int x;

do {
    x = rand();
} while (x >= (RAND_MAX - RAND_MAX % n));

x %= n;

edited Mar 25 '16 at 23:16

Mark Amery 39k21170211

Тем не менее, он имеет оговорку, которая отбрасывает 1 действительный набор результатов в любом сценарии, где RAND_MAX (RM) на 1 меньше, чем кратное N (где N = количество возможных действительных результатов).

то есть, когда «количество отклоненных значений»; (D) равно N, тогда они на самом деле являются действительным набором (V), а не недействительным набором (I).

Используя решение Mark, значения отбрасываются, когда: X = & gt; RM - RM% N

EG: 

Ran Max Value (RM) = 255
Valid Outcome (N) = 4

When X => 252, Discarded values for X are: 252, 253, 254, 255

So, if Random Value Selected (X) = {252, 253, 254, 255}

Number of discarded Values (I) = RM % N + 1 == N

 IE:

 I = RM % N + 1
 I = 255 % 4 + 1
 I = 3 + 1
 I = 4

   X => ( RM - RM % N )
 255 => (255 - 255 % 4) 
 255 => (255 - 3)
 255 => (252)

 Discard Returns $True

Как вы можете видеть в приведенном выше примере, когда значение X (случайное число, которое мы получаем из начальной функции) равно 252, 253, 254 или 255, мы отбрасываем его, даже если эти четыре значения составляют действительный набор возвращаемых значений ,

IE: When the count of the values Discarded (I) = N (The number of valid outcomes) then a Valid set of return values will be discarded by the original function.

Если мы опишем разницу между значениями N и RM как D, то есть:

D = (RM - N)

Затем, когда значение D становится меньше, Процент ненужных повторных бросков из-за этого метода увеличивается при каждом естественном мультипликате. (Когда RAND_MAX НЕ равен простому числу, это имеет значение)

НАПРИМЕР:

RM=255 , N=2 Then: D = 253, Lost percentage = 0.78125%

RM=255 , N=4 Then: D = 251, Lost percentage = 1.5625%
RM=255 , N=8 Then: D = 247, Lost percentage = 3.125%
RM=255 , N=16 Then: D = 239, Lost percentage = 6.25%
RM=255 , N=32 Then: D = 223, Lost percentage = 12.5%
RM=255 , N=64 Then: D = 191, Lost percentage = 25%
RM=255 , N= 128 Then D = 127, Lost percentage = 50%

Поскольку процент необходимых Rerolls увеличивается по мере приближения N к RM, это может иметь значение для многих различных значений в зависимости от ограничений системы, выполняющей код, и искомых значений.

To negate this we can make a simple amendment As shown here:

 int x;

 do {
     x = rand();
 } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );

 x %= n;

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

Examples of using a small value for RAND_MAX which is a multiplicative of N.

Mark'original Version:

RAND_MAX = 3, n = 2, Values in RAND_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3.
When X >= (RAND_MAX - ( RAND_MAX % n ) )
When X >= 2 the value will be discarded, even though the set is valid.

Generalized Version 1:

RAND_MAX = 3, n = 2, Values in RAND_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3.
When X > (RAND_MAX - ( ( RAND_MAX % n  ) + 1 ) % n )
When X > 3 the value would be discarded, but this is not a vlue in the set RAND_MAX so there will be no discard.

Кроме того, в случае, когда N должно быть количеством значений в RAND_MAX; в этом случае вы можете установить N = RAND_MAX +1, если только RAND_MAX = INT_MAX.

По циклу вы можете просто использовать N = 1, и любое значение X будет принято, однако, и добавьте оператор IF для вашего окончательного множителя. Но, возможно, у вас есть код, который может иметь вескую причину для возврата 1, когда функция вызывается с n = 1 ...

Поэтому может быть лучше использовать 0, что обычно дает ошибку Div 0, когда вы хотите иметь n = RAND_MAX + 1

Generalized Version 2:

int x;

if n != 0 {
    do {
        x = rand();
    } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );

    x %= n;
} else {
    x = rand();
}

Оба эти решения решают проблему с ненужными отклоненными действительными результатами, которые произойдут, когда RM + 1 является произведением n.

Вторая версия также охватывает сценарий крайнего случая, когда необходимо, чтобы n равнялся общему возможному набору значений, содержащихся в RAND_MAX.

Модифицированный подход в обоих случаях одинаков и позволяет найти более общее решение необходимости предоставления действительных случайных чисел и минимизации отбрасываемых значений.

Повторить:

The Basic General Solution which extends mark's example:

 int x;

 do {
     x = rand();
 } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );

 x %= n;

The Extended General Solution which Allows one additional scenario of RAND_MAX+1 = n:

int x;

if n != 0 {
    do {
        x = rand();
    } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) );

    x %= n;
} else {
    x = rand();
}

one is valid for all generators. It is easier to see in a limit case. If your generator has a RAND_MAX which is 2 (that isn't compliant with the C standard) and you want only 0 or 1 as value, using modulo will generate 0 twice as often (when the generator generates 0 and 2) as it will generate 1 (when the generator generates 1). Note that this is true as soon as you don't drop values, whatever the mapping you are using from the generator values to the wanted one, one will occurs twice as often as the other.

some kind of generator have their less significant bits less random than the other, at least for some of their parameters, but sadly those parameter have other interesting characteristic (such has being able to have RAND_MAX one less than a power of 2). The problem is well known and for a long time library implementation probably avoid the problem (for instance the sample rand() implementation in the C standard use this kind of generator, but drop the 16 less significant bits), but some like to complain about that and you may have bad luck

Используя что-то вроде

int alea(int n){ 
 assert (0 < n && n <= RAND_MAX); 
 int partSize = 
      n == RAND_MAX ? 1 : 1 + (RAND_MAX-n)/(n+1); 
 int maxUsefull = partSize * n + (partSize-1); 
 int draw; 
 do { 
   draw = rand(); 
 } while (draw > maxUsefull); 
 return draw/partSize; 
}

генерация случайного числа от 0 до n позволит избежать обеих проблем (и избежать переполнения с помощью RAND_MAX == INT_MAX)

Кстати, в C ++ 11 введены стандартные способы редукции и другие генераторы, кроме rand ().

 15 июн. 2012 г., 11:10
Взятие по модулю и деление имеют одинаковую стоимость. Некоторые ISA даже предоставляют только одну инструкцию, которая всегда предоставляет обе. Стоимость восстановления номеров будет зависеть от n и RAND_MAX. Если n мало по отношению к RAND_MAX, это может стоить дорого. И, очевидно, вы можете решить, что отклонения не важны для вашего приложения; Я просто даю способ их избежать.
 15 июн. 2012 г., 08:42
Наивная версия должна быть (RAND_MAX + 1) / (n + 1), так как есть значения RAND_MAX + 1, которые нужно разделить на n + 1 сегментов. Чтобы избежать переполнения при вычислении RAND_MAX + 1, его можно преобразовать в 1+ (RAND_MAX-n) / (n + 1). Чтобы избежать переполнения при вычислении n + 1, сначала проверяется случай n == RAND_MAX.
 15 июн. 2012 г., 05:18
n == RAND_MAX? 1: (RAND_MAX-1) / (n + 1): Я понимаю, что идея состоит в том, чтобы сначала разделить RAND_MAX на равный размер страницы N, а затем вернуть отклонение в пределах N, но я не могу точно сопоставить код с этим.
 15 июн. 2012 г., 10:56
+ плюс, деление кажется более затратным, даже по сравнению с числами регенерации.

Ваш ответ на вопрос