генераторы случайных чисел

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

Но настолько широко, что очень и очень многие применения вызывают многие сомнения!

Примеры того (независимо от языков программирования):

1. Встречаю на нескольких сайтах / форумах код, моделирующий примитивную игру в кости - выбрасывают 2 кубика, и результат формируют как:

Код: Выделить всё

int n1 = rand() % 12 + 1;

Я сначала даже не понял... Ужас! Решили сэкономить

Ребята, сумма 2-х равномерно распределённых случайных величин не имеет равномерного распределения!
Можно только отдельно моделировать выпадание каждого из кубиков 1...6 и складывать эти значения.

Более того:
1А. Известен способ Хеминга (основанный на центральной предельной теореме) генерации нормально распределённых случайных величин: сумма 12-ти последовательно сгенерированных равномерно распределённыхв диапазоне [0...1) чисел даёт нормально расределённую случайную величину с средним значением 6 и дисперсией (и средне-квадратичным отклонением, сигма) = 1. Дальше это число можно центрировать (вычесть 6) и получить желаемую нормальную случайную величину.

2. Но страшнее всего, что я вижу повсеместно - это когда хотят сгенерировать величину в диапазоне [0...N) (вместо [0...RAND_MAX)) записывают это так:

Код: Выделить всё

int n2 = rand() % N

Этого делать нельзя!
Потому что мы используем при этом остатки случайной величины, младшие разряды.
Но, если относительно rand() (и аналогов в разных языках) известно и как-то доказано: а). что значение имеет равномерное распределение + б). этот генератор имеет достаточно хорошее "качество" - то относительно остатков нельзя гарантировано утверждать ни 1-е ни 2-е!

Как можно сделать нормирование к [0...N) диапазону?
Могу предложить (как черновые, на вскидку) такие способы:

Код: Выделить всё

int n2 = ( (unsigned long long)rand() * N ) / RAND_MAX;

Или так:

Код: Выделить всё

int n2 = floor( (double)rand() * N / RAND_MAX );

Как-то так...

Оценивание качества ГСЧ - это мудрёная штука (см. 2-й том Кнутта) - далеко не всё, что кажется случайным, можно использовать с качестве случайных чисел.
Пока соберу только некоторые ссылки на этот предмет ... оценивания качества и нормализации к диапазону:
Генераторы случайных чисел
Тестирование псевдослучайных последовательностей

Очень интересная фишка в связи с этими вопросами - это то, что в достаточно новых процессорах Intel (и AMD, нужно думать, потому что x86_64 - это лицензия, которую Intel купила на использование у AMD!):
- есть аппаратный генератор шума ...на каком-то особо легированном транзисторе

- и есть инструкция процессора RDRAND для считывания очередного случайного числа
- при чём, этой инструкции можно заказать при вызове возвращать 16, 32 или 64 бит значение.

RdRand

RdRand (также RDRAND) это инструкция для генерации случайного числа при помощи встроенного генератора случайных чисел.[1] RdRand доступен для архитектуры процессоров Ivy Bridge и является опциональным расширением набора инструкций Intel 64 и IA-32. Данный генератор случайных чисел соответствует стандартам безопасности и криптографическим стандартам, таким как NIST SP800-90, FIPS 140-2, и ANSI X9.82.[1]

По некоторым мнениям, может представлять собой пример клептографии (англ.)русск. (умышленного внедрения криптографически слабого элемента)[2]. Внедрение уязвимости гипотетически возможно, к примеру, путем изменения типа допирования в одном из транзисторов (требуется модификация как минимум двух литографических масок)

Для проверки поддержки процессором RDRAND можно использовать инструкцию CPUID. При наличии поддержки бит 30 регистра ECX оказывается установлен после вызова функции 01H инструкции CPUID. Опкод RDRAND 0x0F 0xC7.

Компилятор С++, входящий в MS Visual Studio 2013, поддерживает RDRAND посредством функций _rdrand16_step(unsigned short *random_val) и _rdrand32_step(unsigned int *random_val). Если удалось сгенерировать случайное число, используя аппаратный генератор процессора, функция возвращает 1, в противном случае возвращается 0. Само сгенерированное случайное число передается в память по указателю.

Как работает новый генератор случайных чисел Intel

Торвальдс защищает сомнительный ГСЧ в Linux

Генератор псевдослучайных чисел RDRAND, созданный компанией Intel, использует встроенный в процессор Ivy Bridge источник энтропии — тепловой шум процессора. По крайней мере, так заявляют разработчики из Intel. Но этот аппаратный ГСЧ подозревают в наличии скрытой предсказуемости, запрограммированной изначально. В свете недавнего скандала с внедрением бэкдора АНБ в другой стандартный ГСЧ, у некоторых разработчиков возникли подозрения, что в случае с RDRAND тоже могут быть следы работы этой организации.

Бывший мейнтейнер ГСЧ ядра Linux говорит, что даже ушел с работы из-за того, что Линус самовольно включил в модуль ГСЧ этот сомнительный патч от Intel два года назад.

Linux-ru