Сообщение от
Николаев Андрей
Но не забывайте, что правды всегда две. А признавать свою неправоту не любит никто.
В чём сложность? Отрицать математические факты это уж совсем странно. Можно, конечно, вспомнить теорему Гёделя о неполноте, но тут же более приземлённые вещи обсуждаются.
Я соглашусь, что люди гораздо более склонны оправдываться, чем признавать неправоту, но один этот факт не должен сразу создавать факт "правды две".
Сообщение от
Николаев Андрей
Правда 1. Есть прикладные задачи в АСУ ТП. С 99% вероятности для них хватит существующих генераторов в Oscat или приведенной Игорем Петровым
Вот тут не соглашусь. См пункт 2 ниже. Да, у меня два вторых пункта (чтобы хотя бы один прочитали).
В тексте ниже могут содержаться ошибки. Если считаете, что они есть -- пишите, поправлю текст.
Всё нижесказанное относится к простым ГСЧ. Ни о какой криптографии речи не идёт. Ни о какой "сертификации ГСЧ для гослото" речи тоже не идёт. Речь о простых случаях использования ГСЧ: создание тестовых данных, детские игры <<КНС -- "закачаешься">> и т.п.
Предлагаю следующее обобщение:
1) Если нужен ГСЧ, то стоит брать проверенные ГСЧ. Изобретать велосипед НЕ стоит.
2) Даже если нужен "просто ГСЧ, без заявок на криптографию", всё равно нужно брать проверенные решения, а не надеяться на авось, что
"умножу на 100500 и уж точно случайное число получится" или "возьму текущее время, и уж точно случайное число получится".
Есть простые ГСЧ (см п.4) с хорошими свойствами, поэтому "упрощать" смысла нет.
2) Ещё раз повторю второй пункт. Надо брать нормальный генератор, а не "абы какой". Отмазки вида "в АСУТП криптография не нужна" не имеют ничего общего с ГСЧ.
Алгоритм xorshift128 требует всего 4 DWORD переменных и около 10-и операций (сдвиги, xor, присваивания).
Лучше просто взять проверенный генератор и закрыть тему, а не утверждать (голословно), что "в АСУТП это не нужно".
3) Стоит аккуратно относиться к генераторам: какие-то генерируют дробное число, какие-то N-битные целые. Это не одно и то же.
Например, 232-1 не представимо в float'е, поэтому вариация next32bitRandom()/232 будет давать НЕравномерные значения.
Если нужно получить дробное 0..1 на основе ГСЧ, генерирующего целые, то можно пользоваться next24bit()/224 == and(next32bit(), 224-1)/224.
Деление на 224 используется в java, в том числе, и для SecureRandom#nextFloat().
4) Примеры хороших ГСЧ
integer:
xoroshiro128+ (см. статью-сравнение xorshift/xoroshiro)
xorshift128+ (см. статью про ГСЧ в Chrome)
xorshift128 (см. wikipedia)
float:
Wichmann-Hill (см. статью-сравнение xorshift/xoroshiro)
По тестам nist, из генератора float r = (a/30269.0 + b/30307.0 + c/30323.0); r = r - trunc(r); получается не более 22 значащих бит.
Иными словами, если умножать результат больше чем на 1<<21 == 2097152, то равномерность бит становится "вообще никакая".
Про W-H генератор есть забавная история, что в Microsoft Excel 2 раза пытались реализовать W-H, оба раза не получилось,
и в конце концов они перешли на Вихрь Мерсенна
Для ПЛК Вихрь Мерсенна вряд ли имеет смысл, т.к. ему требуется 624 DWORD'ов для состояния (пламенный привет тем, кто попробует реализовать это в ОЛ без массивов!),
да и тот же xoroshiro128+ показывает сравнимые (лучшие) характеристики, уступая, разве что в "периоде генерируемой последовательности".
5) Примеры плохих ГСЧ: OSCAT RDM, RDM2, RDMDW. Вроде, эти генераторы не проходят frequency тест. Про остальные тесты неизвестно.
В OSCAT используются константы e и pi, там нет ссылок на описание алгоритма, потому ГСЧ OSCAT крайне похож на "кулибинство".
Осознанным выбором там не пахнет.
Вот тема про RDM на форуме oscat. Полагаю, на OSCAT всем пофиг, т.к. на форуме
6) Вышеупомянутые генераторы легко реализуются на ПЛК и даже ПР (Wichman-Hill сложно на тех ПР, где нет дробной арифметики).
В xorshift128 используются только сдвиги и операции xor -- т.е. вообще реализуется в виде "что вижу, то пою".
Вот макрос для ПР
В xorshift128+ и xoroshiro128+ для "более лучшей случайности" используется операция сложения (она реально помогает, доказано стат. тестами) 8-и байтных чисел.
В КДС/ОЛ 8-и байтных чисел нет (LWORD не всегда работает), есть только 4-х байтные, но сложить 2 unsigned 8-byte integer'а крайне просто:
Код:
x1, x0 : DWORD; (* X -- первое 8-и байтное число *)
y1, y0 : DWORD; (* Y -- второе 8-и байтное число *)
z1, z0 : DWORD; (* тут будет сумма X+Y *)
z0 := x0 + y0;
z1 := x1 + y1;
IF z0 < x0 OR z0 < y0 THEN (* если был перенос при сложении младших разрядов, добавим единичку к старшим *)
z1 := z1 + 1;
END_IF;
7) Если нужно случайное целое число "от 0 до N включительно", то можно пользоваться next32bit() % (N+1) -- остатком от деления (где next32bit, разумеется, "случайное
целое в диапазоне 0..232-1). Но следует помнить, что при больших N начнёт возникать неравномерность.
Например, если генератор генерирует числа 0, 1, 2, 3 (ну, для примера берём двубитный генератор), а по факту нам нужны 0..2, то при попытке использовать
"остаток от деления на 3" будут получаться ответы: 0, 1, 2, 0 -- т.е. ноль будет выпадать "в два раза чаще, чем должно быть".
Если нужны большие числа (например, случайные в диапазоне 232), и перекос нежелателен, то нужны приплясывания. Пример приплясываний можно посмотреть в java nextInt
8) Для проверки ГСЧ есть общепринятые методики: nist randomness test, TestU01, diehard.
По факту, diehard считается "устаревшей" библиотекой. В nist плохо сделан интерфейс (чтобы добавить генератор нужно где-то в 5-7 местах что-то подправить).
TestU01 не пробовал, но обещают, что там проще.
9) Если ГСЧ завязан на "системное время" (которое на ПЛК, разумеется своей жизнью живёт) и всё равно хочется его проверить, то можно сохранить генерируемую
последовательность в файл и проанализировать уже инструментами п.7 на ПК.
10) Методика тестирования ГСЧ не даёт (и не может) однозначного ответа "тест прошёл/тест не прошёл". Даже абсолютно случайный генератор может выдать 100500 нулей подряд
(но, конечно, такое будет происходить крайне редко), поэтому нужно запускать тест много-много раз и смотреть какой % проходит успешно. Это к тому, что не достаточно "запустить 1 тест 1 раз", чтобы проверить "проходит ли ГСЧ статистический тест".
Так же, вариация "смотреть сколько тестов выдержит ГСЧ, и на каком по счёту завалится" не имеет ничего общего с научным подходом. Вернее, она может иметь, но нужно уметь обрабатывать результаты такого эксперимента. Тут лучше посмотреть п.8 и просто пользоваться общепринятыми методиками.
, а жаль, много там полезного по ГСЧ строительству можно было почерпнуть.
