Як перевірити генератор випадкових чисел
Є програма яка в процесі роботи використовує вбудований генератор випадкових чисел як перевірити, що він дійсно випадковий.
За інституту пам'ятаю були якісь методи.
> Як перевірити, що він дійсно випадковий
"У цьому світі випадків немає .." (с) МВ
Він не випадковий. Він псевдовипадковий. Але ти можеш перевірити отриману послеждовтаельность чисел на соотвествие пропонованим вимогам, наприклад рівномірність розподілу та ін.
Можна перевірити так:
Виконай Random (1000) 1000 разів і вважай числа в 10 інтервалах (1..100, 101..200. 901..1000) і якщо рахунок в десетях інтервалів рівної, то генератор дійсно випадковий.
якщо тобі необхідно віз.представленіе розподілу, то організуй 2-мірний integer-масив, в якому № елемента - це "випадкове" число в діапазоні, що не перевищує межі масиву, а значення цього ел-та масиву ти будеш збільшувати на 1-цу всякий раз, коли генератор видасть очер.чісло, що збігається з номером цього елемента
в циклі "від забору і до обіду" отримуй "случйное" число, шукай соотв.елемент масиву і инкрементируются знайдений елемент
після завершення циклу будь-яким зручним способом візуалізуй масив у вигляді стовпчастого графіка, де по осі Х - "випадкові" числа, а по осі Y - кол-ва "випадінь" кожного з цих чисел
Ну і що з того, що псевдовипадковий?
А перевірити точно можна, хоча б прімітівниой статистикою,
але на скільки я пам'ятаю, є конкретні методи з критеріями і т.д.
Я б сказав, що розподіл одержуваного ряду чисел д.б.н. рівномірним, а також рівномірним д.б.н. розподіл різниць між двома послідовно отриманими числами (деяка гарантія незалежності ряду, хоча, наскільки я розумію, всі подібні ряди марковские і в тій чи іншій мірі кожне число залежить від попереднього). Рівномірність розподілу перевіряють по хи-квадрату.
Пошукай опис тестів DIEHARD. Це стандарт на сьогодні для перевірки "випадковості" генераторів.
А з чого це розподіл має бути рівномірним? Воно у Random рівномірно. А програма може генерувати для себе будь-який розподіл. Рівномірність не може бути критерієм випадковості.
В основі методів генерації "випадкових" послідовностей із заданим розподілом лежать, як правило "генератори з рівномірним розподілом.
Якщо не відтестували рівномірний, то тестувати похідний складніше, та й не так.
Критеріїв повно. Візьми другий том Кнута, подивися. Там вони описані. Але перевіряти генератор треба не на всі критерії, а на потрібні. А для цього треба знати, для чого потрібен програмі цей генератор. Одна справа - колоду карт перемішати, інше - знайти методом Монте-Карло значення кратного інтеграла. У другому випадку, до речі, прове6рка простіше :)
А код генератора є?
Не знаю точну умову задачі застосування випадкових чисел, але в клієнт-банках (точно не скажу як) використовується генератор випадкових чисел спільно з рухом миші по екрану, генератор задає інтервал при якому прочитуються координати екрану і це більш ймовірність отримання масиву випадкових чисел.
Пам'ять: 0.75 MB
Час: 0.065 c