OberonCore
https://forum.oberoncore.ru/

Как генерировать случайные числа?
https://forum.oberoncore.ru/viewtopic.php?f=35&t=6142		 Страница 1 из 2
Автор:  Александр К [ Суббота, 21 Октябрь, 2017 13:53 ]
Заголовок сообщения:  Как генерировать случайные числа?
Как генерировать случайные числа?
Автор:  Comdiv [ Суббота, 21 Октябрь, 2017 14:58 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
Генерировать случайные числа нужно специальными физическими устройствами. Псевдослучайные можно алгоритмически. Но в первую очередь нужно знать, зачем эти числа нужны. Тогда ответ может быть точней.
Автор:  Александр К [ Суббота, 21 Октябрь, 2017 15:10 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
Comdiv писал(а):
Генерировать случайные числа нужно специальными физическими устройствами.

А разве такое устройство не встроено в каждый современный компьютер?
Comdiv писал(а):
Но в первую очередь нужно знать, зачем эти числа нужны. Тогда ответ может быть точней.

Я собираюсь написать программу сортировки. Для неё нужно сгенерировать массив чисел.
Автор:  Пётр Кушнир [ Суббота, 21 Октябрь, 2017 15:16 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
Можете воспользоваться модулем ypkMathRandom из компонента ypk http://oberoncore.ru/bbcc/subs/ypk/start
Автор:  Rifat [ Суббота, 21 Октябрь, 2017 15:42 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
Я обычно пользуюсь таким кодом:
Код:
MODULE MathRand;
   
  IMPORT WinApi;

  CONST a = 1664525; c = 1013904223;
   
  VAR seed: INTEGER;

  PROCEDURE Rand*(): INTEGER;
  BEGIN
    seed := a * seed + c;
    RETURN seed
  END Rand;
   
  PROCEDURE Randomize*;
  BEGIN
    seed := WinApi.GetTickCount();
  END Randomize;

BEGIN
  seed := 0;
END MathRand.
Автор:  Comdiv [ Суббота, 21 Октябрь, 2017 15:58 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
Александр К писал(а):
Comdiv писал(а):
Генерировать случайные числа нужно специальными физическими устройствами.
А разве такое устройство не встроено в каждый современный компьютер?
Нет, но персональные компьютеры оснащены устройствами, от которых в качестве побочных эффектов можно получить небольшое количество случайных чисел, комбинируя которые с генераторами псевдослучайных чисел можно получить поток чисел, почти всегда достаточно хороший для задач криптографии. Почти.
Александр К писал(а):
Я собираюсь написать программу сортировки. Для неё нужно сгенерировать массив чисел.
Для этой задачи полностью подходит простейший линейный конгруэнтный метод, который привёл Рифат. Можно и без WinApi. Плохо то, что допускается арифметическое переполнение, но в BlackBox это будет работать.
Автор:  Иван Денисов [ Суббота, 21 Октябрь, 2017 16:22 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
Для простых задач обычно достаточно ObxRandom.

Наиболее разнообразная реализация генераторов опубликована у Хельмута.
http://www.zinnamturm.eu/downloadsOS.htm#Rng
Автор:  Пётр Кушнир [ Суббота, 21 Октябрь, 2017 17:17 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
Obx это же не библиотечные модули, это модули с примерами. Зачем такое рекомендовать?
Автор:  Info21 [ Суббота, 21 Октябрь, 2017 17:30 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
Из лекций:

Цитата:
2 О псевдослучайных числах
Генераторы псевдослуч. числе -- вещь крайне коварная (великий Джон фон Нейман лажанулся в самом первом своем -- не сумел (!) подойти "математически" (!), занимался рукосуйством).
А. Качество "случайности" (главный спец: George Marsaglia; серия тестов "Diehard")
Б. Длина периода.
Касательно того, что выше, из письма (2004):
Цитата:
.........
2 - Very many 'Platform supplied' random number generators are rubbish.

3 - BlackBox does provide one (as an example) in ObxRandom.
It is due to Lewis, Goodman, & Miller, and is widely cited.
It has a small (31 bit) state vector which, in my opinion,
makes it marginal for large simulations, and inadequate for very large simulations.
It is better that many, and among the best of its type.
For performance details refer to Donald Knuth,
The Art of Computer Programming, Volume 2, Table 1, page 106, line 19.
He describes it as 'adeguate but less outstanding', and '... have known defects'.

4 - There are two other random number generators in module LibRandom
(available from CPC). These are recommended by Knuth, have large
state vectors (upto over 6000 bits), some good proven properties
(eg virtually infinite cycle length), have passed many
empirical tests, and are widely available (any platform with
either c or FORTRAN).
...
Robert Campbell
Автор:  Иван Денисов [ Суббота, 21 Октябрь, 2017 17:41 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
Александр К писал(а):
Я собираюсь написать программу сортировки. Для неё нужно сгенерировать массив чисел.

Для такой задачи ObxRandom достаточно.

Только надо инициализировать.
Код:
ObxRandom.InitSeed(SHORT(Kernel.Time()))
Автор:  Иван Денисов [ Суббота, 21 Октябрь, 2017 17:51 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
Пётр Кушнир писал(а):
Obx это же не библиотечные модули, это модули с примерами. Зачем такое рекомендовать?

Так твой модуль и не отличается от ObxRandom алгоритмом.

Вот твой код:
Код:
   VAR
      seed: INTEGER;

   PROCEDURE UniRandReal* (): REAL;
      CONST a = 16807; m = 2147483647; q = m DIV a; r = m MOD a;
   BEGIN
      seed := a * (seed MOD q) - r * (seed DIV q);
      IF seed <= 0 THEN seed := seed + m END;
      RETURN seed * (1.0 / m)
   END UniRandReal;


Вот ObxRandom:
Код:
   VAR z: INTEGER;   (* global variable *)

   PROCEDURE Uniform* (): REAL;
      CONST a = 16807; m = 2147483647; q = m DIV a; r = m MOD a;
      VAR gamma: INTEGER;
   BEGIN
      gamma := a * (z MOD q) - r * (z DIV q);
      IF gamma > 0 THEN
         z := gamma
      ELSE
         z := gamma + m
      END;
      RETURN z * (1.0 / m)   (* value of the function *)
   END Uniform;


Для новичка проще использовать то, что есть "из коробки". Хотя с установкой расширений всё равно придется разобраться рано или поздно.
Автор:  Пётр Кушнир [ Суббота, 21 Октябрь, 2017 18:33 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
Дело не в том, что код совпадает, а в том, что Obx это набор примеров.
Автор:  ScrollLock [ Пятница, 13 Сентябрь, 2024 10:53 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
Иван Денисов писал(а):
Для простых задач обычно достаточно ObxRandom.
Наиболее разнообразная реализация генераторов опубликована у Хельмута.

Что такое "простые задачи" - сложно формализовать. Некоторые весьма "злобные" статистические тесты основаны на сортировке массива псевдослучайных чисел. Думаю, что в качестве генераторов общего назначения следует использовать криптографически стойкие генераторы с периодом не менее 2^{64}. Всё равно они по производительности и сложности реализации сопоставимы с вихрем Мерсенна. А отказ от криптостойкости нужно специально обосновывать. Даже если использовать примитивные алгоритмы на 5-10 строчек, непригодные для шифрования, то они:
1) Должны проходить SmallCrush, Crush и BigCrush из TestU01.
2) Должны проходить PractRand 0.94 на выборке 32 терабайта.
Ни minstd из ObxRandom, ни даже вихрь Мерсенна им не удовлетворяют.

Вот заметка с более подробным обоснованием использования криптографических алгоритмов как генераторов псевдослучайных чисел общего назначения:
https://sortingsearching.com/2023/11/25/random.html

comdiv писал(а):
Для этой задачи полностью подходит простейший линейный конгруэнтный метод

Его не так просто реализовать на Обероне, т.к. нужно умножать 128-битное число на 64-битное и возвращать старшие 32 бита результата. А линейные конгруэнтные генераторы с состоянием короче 128 бит - это скорее игрушки, чем рабочие инструменты.
Автор:  arisu [ Пятница, 13 Сентябрь, 2024 21:23 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
ScrollLock писал(а):
Вот заметка с более подробным обоснованием использования криптографических алгоритмов как генераторов псевдослучайных чисел общего назначения:
https://sortingsearching.com/2023/11/25/random.html
признаться, не нашёл там обоснований, кроме: «а чего, техника быстрая, давайте бездумно тратить циклы без анализа предметной области». это, если что, АНТИрекомендация.
Автор:  ScrollLock [ Суббота, 14 Сентябрь, 2024 00:35 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
arisu писал(а):
кроме: «а чего, техника быстрая, давайте бездумно тратить циклы без анализа предметной области». это, если что, АНТИрекомендация.

Так криптоаналитики как раз занимаются анализом предметной области за нас. И пытаются придумать такие генераторы, для которых нельзя отличить их вывод от случайного тестами, работающими за приемлемое время. Именно это и на самом деле хочет рядовой пользователь ГПСЧ.

Сам по себе анализ предметной области для генераторов псевдослучайных чисел - штука весьма нетривиальная. И над ней много работали такие известные учёные как Дональд Кнут и Джордж Марсалья, и находили всё новые и новые сюрпризы приятные и не очень. Что касается "бездумно тратить циклы", то опасения несколько преувеличены. У меня при попытке самостоятельно померить скорость работы ГПСЧ получилось так:
0) RANLUX++ - 3.82 cpb (старый RANLUX работал ощутимо медленнее). Генератор вполне достоен, но некриптостоек.
1) ChaCha12 при использовании AVX2 - 1.0 cpb (криптостойкий).
2) ISAAC64 - 0.9 cpb (криптостойкий, есть много памяти)
3) minstd, аналогичный ObxRandom - 2.7 cpb (игрушечный генератор).
4) вихрь Мерсенна - около 1.0 cpb (некриптостойкий, ест много памяти, проваливает отдельные тесты)
5) 128-битный линейный конгруэнтный генератор - 0.53 cpb (некриптостойкий, хороший).
6) MWC128X - 0.21 cpb (некриптостойкий, хороший). От классического MWC отличается скрэмблированием выхода.
7) sfc64 - 0.12 cpb (некриптостойкий, хороший)
8) PCG32 - 0.5 cpb (некриптостойкий, хороший)
Измерял для версий на C99, откомпилированных GCC и встроенных в цикл суммирования. cpb - это "тактов процессора на байт".

Т.е. получается, что на современных 64-битных процессорах криптостойкий ChaCha12 обгоняет minstd, 32-битный линейный конгруэнтный генератор, непригодный для реальной работы. Парадокс кажущийся:
1) ChaCha12 выдаёт сразу блок из 16 32-битных псевдослучайных чисел, и это хорошо распараллеливается с помощью SIMD и конвейера.
2) В ChaCha12 нет никаких условных переходов (а циклы легко развернуть), и это любо конвейеру процессора.
3) В ChaCha12 нет операций умножения и деления вообще.

Если же мил сердцу минимализм и не нужно ничего шифровать - то есть генераторы, в 10-30 раз обгоняющие minstd и при этом проходящие BigCrush и PractRand.

Я бы сравнил криптостойкость генератора псевдослучайных чисел как вариант по умолчанию с неотключаемыми проверками границ массива в Обероне.
Автор:  arisu [ Суббота, 14 Сентябрь, 2024 06:08 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
в данном случае предметная область — это задача, для которой нужен prng. вот у меня twin-stick shooter, например. мне там просто необходим криптостойкий prng, без него никак. у меня ж лишнего времени много, мне не надо ai считать, освещение, и ещё стопицот штук. и кэш бесплатный и бесконечный. поэтому конечно, вместо какого-нибудь bjprng/pcg32 — обязательно криптогенератор. чачу. которая на бенчмарках светится, само собой, ибо внутреннее состояние всегда в кэше процессора. и которую CP2 всенепременно запараллелит, потому что… ну фиг его знает, потому что магия, наверное.

про всё это в статье ни слова, просто постулат: «берите криптопрнг!» ну, мы сейчас как раз живем в мире, где программы пишутся именно по постулатам. лично меня результат совершенно не радует.
Автор:  arisu [ Суббота, 14 Сентябрь, 2024 06:20 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
собственно, я там дальше по ссылке полистал мощный бред автора про ai — и понял, что не стоило тратить время вообще. очередной сферический астронавт в вакууме. и демагог к тому же.
Автор:  ScrollLock [ Суббота, 14 Сентябрь, 2024 09:36 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
arisu писал(а):
про всё это в статье ни слова, просто постулат: «берите криптопрнг!» ну, мы сейчас как раз живем в мире, где программы пишутся именно по постулатам. лично меня результат совершенно не радует.

Тенденция в мире прямо противоположная: в стандартные библиотеки языков программирования норовят запихнуть всякую бяку, даже не способную пройти BigCrush. Подход "пихаем по умолчанию криптостойкий, а дальше как хотите" был бы несравненно адекватнее. Хотя и немного избыточен. Правда, я смотрю на ГПСЧ скорее через призму метода Монте-Карло, и меня удивила простота статистических тестов, способная выявить артефакты многих ГПСЧ. А в компьютерной игре иногда возможен подход из DOOM 1 "берём таблицу из 256 чисел и выдаём её в цикле". Но это не значит, что так можно делать в стандартной библиотеке.

Цитата:
pcg32

Он как раз вполне нормален, уж точно нормальнее minstd.

Цитата:
ибо внутреннее состояние всегда в кэше процессора. и которую CP2 всенепременно запараллелит, потому что… ну фиг его знает, потому что магия, наверное.

Почему магия? Просто нужны ассемблерные вставки или интристики компилятора, и две параллельно работающих "чачи" помещаются в 4 256-битных регистра процессора. И состояние у них куда компактнее, чем у вихря Мерсенна, RANLUX или генератора Фибоначчи с запаздыванием.
Автор:  Борис Рюмшин [ Суббота, 14 Сентябрь, 2024 09:56 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
Под Линуксом можно читать из /dev/random и /dev/urandom.
Автор:  arisu [ Суббота, 14 Сентябрь, 2024 11:35 ]
Заголовок сообщения:  Re: Как генерировать случайные числа?
из /dev/random не надо никогда вообще. надо забыть, что это существует.

и ещё — это медленно очень. но в принципе можно, да. тем не менее обычно urandom используют чтобы сидировать внутренний cprng.
Страница 1 из 2 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/