Страница 3 из 3 ПерваяПервая 123
Показано с 21 по 29 из 29

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

  1. #21

    По умолчанию

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

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

  2. #22

    По умолчанию

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

  3. #23

    По умолчанию

    Цитата Сообщение от Николаев Андрей Посмотреть сообщение
    Но не забывайте, что правды всегда две. А признавать свою неправоту не любит никто.
    В чём сложность? Отрицать математические факты это уж совсем странно. Можно, конечно, вспомнить теорему Гёделя о неполноте, но тут же более приземлённые вещи обсуждаются.
    Я соглашусь, что люди гораздо более склонны оправдываться, чем признавать неправоту, но один этот факт не должен сразу создавать факт "правды две".

    Цитата Сообщение от Николаев Андрей Посмотреть сообщение
    Правда 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 и просто пользоваться общепринятыми методиками.
    Последний раз редактировалось Владимир Ситников; 26.07.2016 в 13:36.

  4. #24

    По умолчанию

    Цитата Сообщение от vladimirisitnikov Посмотреть сообщение
    Код:
      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?

  5. #25

    По умолчанию

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

  6. #26

    По умолчанию

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

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

  7. #27

    По умолчанию

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

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

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

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

    Синдром неприятия чужой разработки?


    И, да, я вполне соглашусь, что даже качества xorshift128 "вполне достаточно для АСУТП" (хотя, xorshift128+ или xoroshiro128+ получше будет).
    Вот Вихрь Мерсенна это уже да, перебор (см. конец пункта 4). Но если выбор между "умножу на 42 и меняустраивает" и xorshift128, то выбор, очевидно, должен быть в сторону xorshift128.
    Последний раз редактировалось Владимир Ситников; 26.07.2016 в 13:26.

  8. #28
    Пользователь Аватар для capzap
    Регистрация
    25.02.2011
    Адрес
    Киров
    Сообщений
    10,425

    По умолчанию

    Цитата Сообщение от vladimirisitnikov Посмотреть сообщение
    ну вот как тут не встрянешь, Вы сами то читали: например, через получение её исходного кода
    Вы предоставляли изначально исходник? Нет, Вы предложили самому копаться, я попробовал, увидел что получить реал от 0 до 1, деля на максимум 32-битных чисел в плк не возможно, на какой странице флуда выяснилось из скольки бит нужно получать реал?
    Bad programmers worry about the code. Good programmers worry about data structures and their relationships

  9. #29

    По умолчанию

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

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

    Исправляюсь. Владимир создал макрос для OL.
    Последний раз редактировалось Николаев Андрей; 27.07.2016 в 08:51.

Страница 3 из 3 ПерваяПервая 123

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •