Генерация случайного числа

[Gans]

Подсакажите как правильно генерить случайное число в ПЛК1хх?

[Филоненко Владислав]

Вот основа алгоритма:
uint NextUInt()
{
uint t= (x^(x<<11));
x=y;
y=z;
z=w;
return (w= (w^(w>>19))^(t^(t>>8)));
}

перед использованием необходимо инициализировать переменные t,x,y,z,w. Это можно сделать по часам, анализируя данные в файлах - к примеру Log.txt и debug.txt или просто храня посл. значения в retain.

Алгоритм считается достаточно хорошим с периодом повторяемости 2^50 и высокой скоростью.

[Gans]

uint NextUInt()
{
uint t= (x^(x<<11));
x=y;
y=z;
z=w;
return (w= (w^(w>>19))^(t^(t>>8)));
} - это на сях? а можно в следующие разы листинк из кодесиса как бы раздел форума носит название "Среда программирования CoDeSys" (хотя меня лично устроит и на паскале :-)

^ - это пoбитoвoе исключеннoе OR?
<< - это пoбитoвый сдвиг влевo?
>> - это пoбитoвый сдвиг вправo?

И какие типы переменных t, w, x, y?
P. S. а так хотелось что нибудь по проще :-( но влюбом случае разберёмся :-)

[Филоненко Владислав]

На С.
^ - это пoбитoвoе исключеннoе OR?
<< - это пoбитoвый сдвиг влевo?
>> - это пoбитoвый сдвиг вправo?
Именно так. Число после побитового сдвига - на сколько бит.

Тип всех переменных - DWORD.
Проще - сразу падает качество генерируемых случ. чисел :(

Забыл сказать - реализуйте не виде функции, а в виде функционального блока, чтобы значения переменных t,x,y,z,w сохранялись!

[Gans]

Большое спасибо за помощь. Пошёл сдвигать биты :-) и тд. и тп.

[Василий Куц]

если у кого-то возникли проблемы - держите.

Значения инициализируются из внутренних часов => работать будет только в ПЛК и с подключенной syslibtime

[Игорь Петров]

Еще один простенький генератор случайных чисел в CoDeSys.

[Crazy]

Еще один простенький генератор случайных чисел в CoDeSys.
Чегой-то не работает.
Может смысл его работы подскажете?
Там единственная строка ответственная за генерацию

(*собст-но генератор*)
x := x*170 - 251 *(x * 170/251);
Чисто математически при любом х ответ 0

______
Хм. Сорри. Работает. (Сначала неправильно скопировал)
Особенности целочисленного округления чтоль...

[Kotenko]

Игорь, спасибо большое. очень помогло.

[вут]

Игорь , ваш генератор работает прикольно , но каждые секунд 20 повторение идет - хорошо видно если передавать выход в панель и строить график ....

[Вольд]

Игорь , ваш генератор работает прикольно , но каждые секунд 20 повторение идет - хорошо видно если передавать выход в панель и строить график ....

Все ГСЧ так работают. Вся разница в длине цикла.

[Владимир Ситников]

Все ГСЧ так работают. Вся разница в длине цикла.

Вот например к чему приводил плохой ГСЧ в Google Chrome: https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d

Кто-нибудь пробовал реализовывать xorshift128plus?
У xorshift128plus (https://en.wikipedia.org/wiki/Xorshift#xorshift.2B) период 2128-1, и этого должно хватить с запасом.

К слову, xorshift128plus используется в большинстве браузеров (в Chrome, Safari, FireFox точно) для Math.random().

Собственно, код:

/* The state must be seeded so that it is not everywhere zero. */
uint64_t s[2];

uint64_t xorshift128plus(void) {
uint64_t x = s[0];
uint64_t const y = s[1];
s[0] = y;
x ^= x << 23; // a
s[1] = x ^ y ^ (x >> 17) ^ (y >> 26); // b, c
return s[1] + y;
}

[capzap]

в оскат есть рандомная функция, а тему подняли аж из 2007 года, к ней у кого то есть претензии?

[Владимир Ситников]

в оскат есть рандомная функция, а тему подняли аж из 2007 года, к ней у кого то есть претензии?
В оскат практически наверняка палёная рандомная функция.
Использование неправильных рандомных функций запросто может приводить к неправильным вычислениям и т.п.

Вот одна: https://github.com/simsum/oscat/blob/master/RDM.EXP, вот вторая: https://github.com/simsum/oscat/blob/master/RDMDW.EXP
Ни там, ни там нет ссылок на алгоритм.
А факт того, что они используют "умножение на e и на pi" намекает на то, что это "наколеночная реализация" и, что вообще никто никогда не тестировал результат этих функций на случайность.

В этом плане, xorshift128plus выглядит гораздо лучше. Проверенный алгоритм, много где используется, без привлечения float математики.

[Николаев Андрей]

Снимаю шляпу перед Вольдом - наступил тот момент, когда я с ним согласен - нужен рефери.
Знаете что в этой ситуации более всего огорчает? Столько времени и ресурсов грамотных и нужных людей потрачено не конструктивно. Это очень жаль.
К сути.
1. Сообщения удалил. По понятным причинам. Если они для кого то ценны - могу вынести их в отдельную тему - там можно будет продолжить соревнования.
2. В любом случае призываю общаться без перехода на личности. В ЛЮБОМ СЛУЧАЕ. Я понимаю, что все участвовавшие пытались доказать свою правоту, и заставить аппонента признать ее из лучших побуждений. Но не забывайте, что правды всегда две. А признавать свою неправоту не любит никто.

Правда 1. Есть прикладные задачи в АСУ ТП. С 99% вероятности для них хватит существующих генераторов в Oscat или приведенной Игорем Петровым (очень сильный и грамотный специалист с огромным опытом реальных внедрений). С этим невозможно спорить. С определенной вероятностью они не проходят специфические тесты. С определенной вероятностью повторяют значения. Но если этого достаточно - значит так тому и быть. Напоминаю первое правило автоматизации: работает - не лезь :)
Правда 2. Любые прикладные задачи все-равно строятся на математике. И хорошо, что у нас есть люди, которые готовы нам эту "математику" предоставлять. Хорошо, когда они указывают на слабые места наших алгоритмов. Плюс данное указание могут увидеть спецы, в чьих задачах это действительно критично.
Но при этом никто не говорит, что надо все бросить и переделать. Посчитал AI данные аргументы полезными для улучшения своего алгоритма - улучшил. Не посчитали так в OSCAT - не будут улучшать :)
Давайте попробуем синергитически использовать энергию и ресурсы друг друга.

И еще раз прошу перестать скатываться на личности. Мы все тут специалисты. Кто-то сильней в одном, кто-то в другом. Кто-то слабее. Но все достойны уважительного отношения.

[Вольд]

Остались от темы рожки да ножки ;), а жаль, много там полезного по ГСЧ строительству можно было почерпнуть.

[Николаев Андрей]

Если кто-то возьмется собрать из 24 страниц полезную информацию - я перенесу все удаленные сообщения в отдельную тему. Специально для этого удалил сообщения "не окончательно".

[energvk]

Перенесите пожалуйста

[capzap]

тема все равно была не в профильных разделах, а в курилке

[Павел Братковский]

тема все равно была не в профильных разделах, а в курилке

вот с этим не поспоришь, зачем тему менять закрывать это же КУРИЛКА

[Николаев Андрей]

Объясняю:
1. Тема не удалялась.
2. Удалены 22 страницы неконструктивного диалога, с переходом на личности. За этим диалогом пропала сама суть темы. За эмоциями и обсуждениями "кто дурак" - пожалуйста в телевизор, с первой по 10 кнопку.
3. Если аппоненты готовы продолжать диалог в конструктивном русле - большая просьба собрать выдержку из 22 страниц в нескольких сообщениях, к каким выводам кто пришел. Если для этого нужно (чтобы вспомнить) восстановить часть переписки - я и предложил это сделать в отдельной теме.

Еще раз, настойчиво, призываю к конструктивному общению. Без перехода на личное. Если видите провокации - лучше просто не реагировать.
И еще раз напоминаю, что форум имеет практическое применение для всех остальных участников сообщества. И читать 25 страниц разборок - точно не про это.

[Николаев Андрей]

По просьбам форумчан временно вернул сообщения в тему:
http://www.owen.ru/forum/showthread.php?t=24859
Тема закрытая. Большая просьба конструктивную часть перенести в эту тему - остальное будет удалено.

[Владимир Ситников]

Но не забывайте, что правды всегда две. А признавать свою неправоту не любит никто.
В чём сложность? Отрицать математические факты это уж совсем странно. Можно, конечно, вспомнить теорему Гёделя о неполноте (https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%93% D1%91%D0%B4%D0%B5%D0%BB%D1%8F_%D0%BE_%D0%BD%D0%B5% D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D1%82%D0%B5), но тут же более приземлённые вещи обсуждаются.
Я соглашусь, что люди гораздо более склонны оправдываться, чем признавать неправоту, но один этот факт не должен сразу создавать факт "правды две".


Правда 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() (https://docs.oracle.com/javase/8/docs/api/java/util/Random.html#nextFloat--).

4) Примеры хороших ГСЧ
integer:
xoroshiro128+ (см. статью-сравнение xorshift/xoroshiro (http://xoroshiro.di.unimi.it/))
xorshift128+ (см. статью про ГСЧ в Chrome (http://v8project.blogspot.ru/2015/12/theres-mathrandom-and-then-theres.html))
xorshift128 (см. wikipedia (https://en.wikipedia.org/wiki/Xorshift#Example_implementation))

float:
Wichmann-Hill (см. статью-сравнение xorshift/xoroshiro (https://en.wikipedia.org/wiki/Wichmann-Hill))
По тестам 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, оба раза не получилось (http://blog.richpollock.com/2014/08/randomness-in-excel/),
и в конце концов они перешли на Вихрь Мерсенна (https://ru.wikipedia.org/wiki/%D0%92%D0%B8%D1%85%D1%80%D1%8C_%D0%9C%D0%B5%D1%80% D1%81%D0%B5%D0%BD%D0%BD%D0%B0)
Для ПЛК Вихрь Мерсенна вряд ли имеет смысл, т.к. ему требуется 624 DWORD'ов для состояния (пламенный привет тем, кто попробует реализовать это в ОЛ без массивов!),
да и тот же xoroshiro128+ показывает сравнимые (лучшие) характеристики, уступая, разве что в "периоде генерируемой последовательности".

5) Примеры плохих ГСЧ: OSCAT RDM, RDM2, RDMDW. Вроде, эти генераторы не проходят frequency тест. Про остальные тесты неизвестно.
В OSCAT используются константы e и pi, там нет ссылок на описание алгоритма, потому ГСЧ OSCAT крайне похож на "кулибинство".
Осознанным выбором там не пахнет.
Вот тема про RDM на форуме oscat (http://www.oscat.de/community/index.php/topic,2553.0.html). Полагаю, на OSCAT всем пофиг, т.к. на форуме

6) Вышеупомянутые генераторы легко реализуются на ПЛК и даже ПР (Wichman-Hill сложно на тех ПР, где нет дробной арифметики).
В xorshift128 используются только сдвиги и операции xor -- т.е. вообще реализуется в виде "что вижу, то пою".
Вот макрос для ПР (http://www.owen.ru/forum/showthread.php?t=24825&p=215270&viewfull=1#post215270)

В 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 (https://docs.oracle.com/javase/8/docs/api/java/util/Random.html#nextInt-int-)

8) Для проверки ГСЧ есть общепринятые методики: nist randomness test (http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html), TestU01 (https://ru.wikipedia.org/wiki/TestU01), diehard (https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82%D1%8B_diehard).

По факту, diehard считается "устаревшей" библиотекой. В nist плохо сделан интерфейс (чтобы добавить генератор нужно где-то в 5-7 местах что-то подправить).
TestU01 не пробовал, но обещают, что там проще.

9) Если ГСЧ завязан на "системное время" (которое на ПЛК, разумеется своей жизнью живёт) и всё равно хочется его проверить, то можно сохранить генерируемую
последовательность в файл и проанализировать уже инструментами п.7 на ПК.

10) Методика тестирования ГСЧ не даёт (и не может) однозначного ответа "тест прошёл/тест не прошёл". Даже абсолютно случайный генератор может выдать 100500 нулей подряд
(но, конечно, такое будет происходить крайне редко), поэтому нужно запускать тест много-много раз и смотреть какой % проходит успешно. Это к тому, что не достаточно "запустить 1 тест 1 раз", чтобы проверить "проходит ли ГСЧ статистический тест".
Так же, вариация "смотреть сколько тестов выдержит ГСЧ, и на каком по счёту завалится" не имеет ничего общего с научным подходом. Вернее, она может иметь, но нужно уметь обрабатывать результаты такого эксперимента. Тут лучше посмотреть п.8 и просто пользоваться общепринятыми методиками.

[kolyan]

x1, x1 : 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;





Объявлены две одинаковые переменные: х1 и х1. Наверное, опечатка? Должно, видимо, быть: х1, х0?

[Владимир Ситников]

Объявлены две одинаковые переменные: х1 и х1. Наверное, опечатка? Должно, видимо, быть: х1, х0?

Спасибо, поправил.

[Николаев Андрей]

Большое спасибо за качественный обзор, Владимир.
Думаю найдутся специалисты, которым это будет востребовано.

Но мою главную мысль Вы упустили. Допустим я простой инженер КИП. У меня задача не убедить гос. комиссию, что мой лототрон не дублирует выдачу цифр, а проверить как поведет себя мой регулятор при подаче на него случайного числа. И нет для меня ничего страшного, если в 100 случаях из 1000 число повторится.
И я, имея задачу создать и проверить свою программу не буду убеждаться в точности и корректности его работы, если МЕНЯ ЭТО УСТРАИВАЕТ.
Если вызывает некоторое сомнение использование для такого генератора термина ГСЧ - давайте называть его ГСЧ' или ГСЧ" или "ГСЧ". Думаю, что создатели "некорректно работающих ГСЧ" и называют их так только с одной целью - именно под таким общепринятым названием этот алгоритм будут искать другие пользователи.
Это и есть вторая правда :)

[Владимир Ситников]

Но мою главную мысль Вы упустили. Допустим я простой инженер КИП. У меня задача не убедить гос. комиссию, что мой лототрон не дублирует выдачу цифр, а проверить как поведет себя мой регулятор при подаче на него случайного числа. И нет для меня ничего страшного, если в 100 случаях из 1000 число повторится
Извольте, сэр, но см. мой пункт №2 выше.


И нет для меня ничего страшного, если в 100 случаях из 1000 число повторится.
Вы неправильно трактуете проблему.
Проблема не только в том, что "число повторится", а в том, что "самопальный ГСЧ" может генерировать завышенные/заниженные числа, и в итоге реальность будет бесконечно далека от модели.
Например, окажется, что в реальности "выбросы" будут гораздо чаще, чем при моделировании, и PID пойдёт в расколбас, хотя в моделировании было всё хорошо.

Попробую аналогию: "вместо использования аппаратного умножения, в PID регулятор заносим таблицу умножения, полученную с помощью логарифмической линейки". Да, может даже и сработает. Но, разумеется, могут быть и ошибки (например, неправильно считали показание с линейки и т.п.)
Так вот: в чём смысл городить эпопею с лог.линейкой и говорить "меня устраивает", если можно просто взять готовый "оператор умножения"?

Так и с ГСЧ. Есть xorshift128. В чём проблема взять и закрыть тему?

Синдром неприятия чужой разработки (https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BD%D0%B4%D1%80%D0%BE%D0%BC_%D0%BD% D0%B5%D0%BF%D1%80%D0%B8%D1%8F%D1%82%D0%B8%D1%8F_%D 1%87%D1%83%D0%B6%D0%BE%D0%B9_%D1%80%D0%B0%D0%B7%D1 %80%D0%B0%D0%B1%D0%BE%D1%82%D0%BA%D0%B8)?


И, да, я вполне соглашусь, что даже качества xorshift128 "вполне достаточно для АСУТП" (хотя, xorshift128+ или xoroshiro128+ получше будет).
Вот Вихрь Мерсенна (https://ru.wikipedia.org/wiki/%D0%92%D0%B8%D1%85%D1%80%D1%8C_%D0%9C%D0%B5%D1%80% D1%81%D0%B5%D0%BD%D0%BD%D0%B0) это уже да, перебор (см. конец пункта 4). Но если выбор между "умножу на 42 и меняустраивает" и xorshift128, то выбор, очевидно, должен быть в сторону xorshift128.

[capzap]

Синдром неприятия чужой разработки (https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BD%D0%B4%D1%80%D0%BE%D0%BC_%D0%BD% D0%B5%D0%BF%D1%80%D0%B8%D1%8F%D1%82%D0%B8%D1%8F_%D 1%87%D1%83%D0%B6%D0%BE%D0%B9_%D1%80%D0%B0%D0%B7%D1 %80%D0%B0%D0%B1%D0%BE%D1%82%D0%BA%D0%B8)?


ну вот как тут не встрянешь, Вы сами то читали: например, через получение её исходного кода
Вы предоставляли изначально исходник? Нет, Вы предложили самому копаться, я попробовал, увидел что получить реал от 0 до 1, деля на максимум 32-битных чисел в плк не возможно, на какой странице флуда выяснилось из скольки бит нужно получать реал?

[Николаев Андрей]

Так как пока не получается конструктивно - тема закрывается.
На правах модератора некоторое реноме:
1. Так и хорошо, что ошибка - проверю как ПИД отрабатывает ошибки. Не устроит взятый генератор - откажусь от него, возьму другой. Не подойдет другой - буду писать свой. Как то так все в жизни и проихсодит.
2. Теоретические выкладки действительно полезны и важны. Но не менее важно для присутствующих здесь специалистов практика. И наличие существующего генератора, который, возможно, и не удовлетворяет всем требованиям к такому типу алгоритмов, для меня сильно полезнее, чем отсыл к описанию алгоритма идеального ГСЧ. Такова специфика моей работы. Такова специфика работы в отрасли - мы не занимаемся лотереями.
3. Всегда стараюсь жить по принципу: критикуешь - предлагай. Я думаю, если бы Владимир не поленился и написал на CODESYS или OL свой блок, согласно приведенным ссылкам, и выложил его, чтобы коллеги могли протестировать - дискуссия могла принять другой поворот. Даже лично мне нет никакого желания тратить время на проверку гепотез - я бы взял генератор Петрова и не сильно задумывался над его идеальностью.

При этом я правда верю, что это вполне посильно Владимиру. В его компетентности я не сомневаюсь.

Исправляюсь. Владимир создал макрос для OL.