Понимание алгоритма функции Visual С++ rand()

В C/С++ rand() и srand() обычно используются нами, когда мы хотим получить случайное целое число. Но когда я попытался переписать его сам, мне было трудно понять алгоритм. Функция очень легко записывается только в нескольких строках, но формула является непониманием.

Основная формула:

ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L;

Исходный код:

void __cdecl srand (unsigned int seed)
{
    _getptd()->_holdrand = (unsigned long)seed;
}

int __cdecl rand (void)
{
    _ptiddata ptd = _getptd();
    return ( ((ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L) >> 16) & 0x7fff );
}

Ответы

Ответ 1

Это просто модульная арифметика. Вы умножаетесь и добавляете число, которое принимается по модулю 2 ^ 32 (например) и возвращающее верхний 16 бит как ваш "случайный" номер. Поскольку вы умножаете и добавляете числа, которые являются взаимно простыми по отношению к модулю, это создает вид равномерно распределенных чисел.

Тщательный выбор двух чисел очень важен. Например, если вы использовали "* 4" и "+ 8", вы, вероятно, не испытали бы много случайности.

Эта схема называется линейной конгруэнтной.

Ответ 3

Вы можете найти объяснение линейного конгруэнтного генератора (LCG) и других подобных семейств или псевдослучайных генераторов и о выборе этих конкретных констант в превосходной статье, опубликованной в этом месяце (7-2011) в журнале Dr. Dobb Journal (DDJ): Быстрые, высококачественные, параллельные генераторы случайных чисел: сравнение реализации.

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

Ответ 4

До вызова rand, поскольку man-страница для srand указывает, что "Если не задано начальное значение, функция rand() автоматически высевается со значением 1", тогда лучший подход к вызову rand - это сначала вызвать srand, который "установит свой аргумент как семя для новой последовательности псевдослучайных целых чисел, возвращаемых rand()".

В качестве примера рассмотрим следующий код awk, nawk, gawk, который используется в оболочке bash script для создания нового (случайного) MAC-адреса - например,.genmacaddr, указанного в фрагменте кода:

enter code here
BEGIN {
     n0 = "00"
     srand()
     n1 = sprintf("%02x", int(255 * rand()))
     n2 = sprintf("%02x", int(255 * rand()))
     n3 = sprintf("%02x", int(255 * rand()))
     n4 = sprintf("%02x", int(255 * rand()))
     n5 = sprintf("%02x", int(255 * rand()))
     print n0":"n1":"n2":"n3":"n4":"n5
}

где фрагмент кода в bash shell script:

enter code here
ifconfig eth0 down
newmacaddr=`nawk -f .genmacaddr -`
ifconfig eth0 hw ether $newmacaddr
ifconfig eth0 up

Если я не ошибаюсь, начальное значение для srand выводится из системных часов.

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

Ответ 5

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

семя хранится в _getptd() → _ holdrand (далее - holdrand)

Этот код "работает", выполняя обычный шаг умножения и добавления, но затем переполняя holdrand получить подразумеваемый "модуль" 0x100000000.

Я упоминаю об этом, потому что это не сразу очевидно, и вообще не считается хорошим стилем.

Технически переполнение целочисленной переменной isnvokes поведение undefined, но на большинстве платформ это вполне предсказуемо, поэтому инженеры Microsoft игнорируют эту проблему.