Почему rand () повторяет числа гораздо чаще на Linux, чем Ma c?

Question

Я реализовал хэш-карту в C как часть проекта, над которым я работаю, и использовал случайные вставки для проверки его, когда заметил, что rand() на Linux, кажется, повторяет числа гораздо чаще, чем на Ма c. RAND_MAX равно 2147483647 / 0x7FFFFFFF на обеих платформах. Я сократил его до этой тестовой программы, которая создает байтовый массив RAND_MAX+1 -long, генерирует RAND_MAX случайные числа, отмечает, если каждое из них является дубликатом, и проверяет его из списка, как видно.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int main() {
    size_t size = ((size_t)RAND_MAX) + 1;
    char *randoms = calloc(size, sizeof(char));
    int dups = 0;
    srand(time(0));
    for (int i = 0; i < RAND_MAX; i++) {
        int r = rand();
        if (randoms[r]) {
            // printf("duplicate at %d\n", r);
            dups++;
        }
        randoms[r] = 1;
    }
    printf("duplicates: %d\n", dups);
}

Linux последовательно генерирует около 790 миллионов дубликатов. Ма c последовательно только генерирует единицу, поэтому он перебирает каждое случайное число, которое может генерировать почти без повторения. Может кто-нибудь объяснить мне, как это работает? Я не могу сказать ничего отличного от man-страниц, не могу сказать, какой RNG использует каждый, и не могу найти что-либо в Интернете. Спасибо!

Answer 1

Хотя на первый взгляд может показаться, что macOS rand() лучше не повторять никаких чисел, следует отметить, что при таком количестве сгенерированных чисел ожидается , чтобы увидеть множество дубликатов (в Фактически, около 790 миллионов или (2 ³¹ -1) / е ). Аналогичным образом, повторение чисел в последовательности также не приведет к дублированию, но не будет считаться очень случайным. Таким образом, реализация Linux rand() в этом тесте неотличима от истинного случайного источника, тогда как macOS rand() - нет.

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

/*
 * Compute x = (7^5 * x) mod (2^31 - 1)
 * without overflowing 31 bits:
 *      (2^31 - 1) = 127773 * (7^5) + 2836
 * From "Random number generators: good ones are hard to find",
 * Park and Miller, Communications of the ACM, vol. 31, no. 10,
 * October 1988, p. 1195.
 */
    long hi, lo, x;

    /* Can't be initialized with 0, so use another value. */
    if (*ctx == 0)
        *ctx = 123459876;
    hi = *ctx / 127773;
    lo = *ctx % 127773;
    x = 16807 * lo - 2836 * hi;
    if (x < 0)
        x += 0x7fffffff;
    return ((*ctx = x) % ((unsigned long) RAND_MAX + 1));

Это действительно приводит ко всем числам от 1 до RAND_MAX включительно, ровно один раз, до последовательность повторяется снова. Поскольку следующее состояние основано на умножении, состояние никогда не может быть нулевым (или все будущие состояния также будут равны нулю). Таким образом, повторное число, которое вы видите, является первым, а ноль - тем, которое никогда не возвращается.

Apple продвигает использование лучших генераторов случайных чисел в своей документации и примерах, по крайней мере, до тех пор, пока macOS (или OS X) существует, поэтому качество rand(), вероятно, не считается важным, и они только что остановились на одном из простейших доступных генераторов псевдослучайных данных. (Как вы заметили, их rand() даже комментируют с рекомендацией использовать вместо него arc4random().)

В связанной заметке самый простой генератор псевдослучайных чисел, который я мог найти, который дает приличные результаты в этом (и многие другие) тесты на случайность - это xorshift *:

uint64_t x = *ctx;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
*ctx = x;
return (x * 0x2545F4914F6CDD1DUL) >> 33;

Эта реализация дает почти ровно 790 миллионов дубликатов в вашем тесте.

Answer 2

MacOS предоставляет недокументированную функцию rand () в stdlib. Если оставить его незаполненным, то первые значения, которые он выводит, это 16807, 282475249, 1622650073, 984943658 и 1144108930. быстрый поиск покажет, что эта последовательность соответствует очень простому c генератору случайных чисел LCG, который повторяет следующую формулу:

x _{n + 1} = 7 ⁵ · x _n (мод 2 ³¹ - 1)

Поскольку состояние этого ГСЧ полностью описывается значением одного 32-разрядного целого числа, его период не очень длинный. Чтобы быть точным, он повторяется каждые 2 ³¹ - 2 итерации, выводя каждое значение от 1 до 2 ³¹ - 2.

Я не думаю, что есть стандарт реализация rand () для всех версий Linux, но есть функция glib c rand () , которая часто используется. Вместо одной 32-битной переменной состояния, в ней используется пул из более чем 1000 бит, который, по сути, никогда не будет создавать полностью повторяющуюся последовательность. Опять же, вы, вероятно, можете узнать, какая у вас версия, распечатав первые несколько выводов с этого ГСЧ, не заполнив его сначала. (Функция glib c rand () создает числа 1804289383, 846930886, 1681692777, 1714636915 и 1957747793.)

Так что причина в том, что вы получаете больше коллизий в Linux (и вряд ли в MacOS) заключается в том, что версия rand () Linux в основном более случайная.

Answer 3

rand() определяется стандартом C, а стандарт C не определяет, какой алгоритм использовать. Очевидно, что Apple использует подчиненный алгоритм для вашей реализации GNU / Linux: Linux не отличается от истинного случайного источника в вашем тесте, в то время как реализация Apple просто перемешивает числа вокруг.

Если вам нужны случайные числа любого качества, либо используйте более качественный PRNG, который дает хотя бы некоторые гарантии качества возвращаемых чисел, либо просто читайте из /dev/urandom или аналогичного. Последний дает вам криптографические c качественные числа, но работает медленно. Даже если он слишком медленный, /dev/urandom может обеспечить отличные семена для другого, более быстрого PRNG.

Answer 4

В целом, пара rand / srand долгое время считалась устаревшей из-за того, что биты младшего разряда отображают меньшую случайность, чем биты старшего разряда в результатах. Это может или не может иметь какое-либо отношение к вашим результатам, но я думаю, что это все еще хорошая возможность помнить, что, хотя некоторые реализации rand / srand теперь более современны, более старые реализации сохраняются, и лучше использовать случайные (3 ). На моем поле Arch Linux на man-странице для rand (3) все еще находится следующее примечание:

  The versions of rand() and srand() in the Linux C Library use the  same
   random number generator as random(3) and srandom(3), so the lower-order
   bits should be as random as the higher-order bits.  However,  on  older
   rand()  implementations,  and  on  current implementations on different
   systems, the lower-order bits are much less random than the  higher-or-
   der bits.  Do not use this function in applications intended to be por-
   table when good randomness is needed.  (Use random(3) instead.)

Чуть ниже страница руководства на самом деле очень короткая, очень простые примеры реализаций rand и srand, которые относятся к самым простым L C RNG, которые вы когда-либо видели, и имеют небольшой RAND_MAX. Я не думаю, что они соответствуют тому, что находится в стандартной библиотеке C, если они когда-либо делали. Или, по крайней мере, я надеюсь, что нет.

В общем, если вы собираетесь использовать что-то из стандартной библиотеки, используйте случайное, если можете (страница руководства перечисляет это как стандарт POSIX обратно к POSIX.1-2001 , но ранд является стандартным способом еще до того, как C был даже стандартизирован). Или еще лучше, взломайте Numeric Recipes (или поищите его в Интернете) или Knuth и внедрите один. Они действительно просты, и вам действительно нужно сделать это один раз, чтобы получить универсальный ГСЧ с атрибутами, которые вам наиболее часто нужны и которые имеют известное качество.