Представлений онлайн генератор випадкових чиселпрацює на основі вбудованого в JavaScript програмного генератора псевдовипадкових чисел з рівномірним розподілом. Генеруються цілі числа. За замовчуванням виводиться 10 випадкових чисел у діапазоні 100...999, числа розділені пробілами.

Основні налаштування генератора випадкових чисел:

• Кількість чисел
• Діапазон чисел
• Тип роздільника
• Увімк/викл функцію видалення повторів (дублів чисел)

Загальна кількість формально обмежена 1000, максимальна кількість- 1 мільярд. Варіанти роздільників: пробіл, кома, крапка з комою.

Тепер ви точно знаєте, де і як в інтернеті отримати безкоштовну послідовність випадкових чисел у заданому діапазоні.

Варіанти застосування генератора випадкових чисел

Генератор випадкових чисел (ГСЧ на JS з рівномірним розподілом) стане в нагоді SMM-фахівцям і власникам груп та спільнот у соціальних мережахІстаграм, Facebook, Вконтакте, Однокласники для визначення переможців лотерей, конкурсів та розіграшів призів.

Генератор випадкових чисел дозволяє проводити розіграш призів серед довільної кількості учасників із заданою кількістю переможців. Конкурси можна проводити без репостів та коментарів - ви самі задаєте кількість учасників та інтервал генерації випадкових чисел. Отримати набір випадкових чисел онлайн і безкоштовно можна на даному сайті, при цьому вам не потрібно ставити будь-яку програму на смартфон або програму на комп'ютер.

Також генератор випадкових чисел онлайн може бути використаний для імітації підкидання монет або гральних кісток. Втім, у нас для цих випадків є окремі спеціалізовані сервіси.

Будь ласка, допоможіть сервісу одним кліком:Розкажіть друзям про генератор!

Генератор чисел онлайн в 1 клік

Генератор випадкових чисел, представлений на нашому сайті, дуже зручний. Наприклад, його можна використовувати у розіграшах та лотереях для визначення переможця. Призери визначаються так: програмою видається одне чи кілька чисел у будь-якому діапазоні, заданому Вами. Підтасування результатів можна відразу виключити. А завдяки цьому переможець визначається у чесному виборі.

Іноді потрібне отримання деякої кількості випадкових чисел відразу. Наприклад, хочеться заповнити лотерейний квиток «4 із 35», довірившись нагоді. Чи можна перевірити: якщо підкинути монетку 32 рази, яка буде ймовірність того, що випаде 10 реверсів поспіль (орел/решка цілком можуть призначатися цифрами 0 і 1)?

Випадкова кількість онлайн відеоінструкція - рандомайзер

Наш генератор чисел дуже простий у використанні. Він не вимагає завантаження програми на комп'ютер – ним можна скористатися онлайн. Для отримання потрібного Вам числа необхідно встановити діапазон випадкових чисел, кількість та, за бажанням, роздільник чисел та виключити повтори.

Щоб згенерувати випадкові числа в певному діапазонічастот:

• Виберіть діапазон;
• Вкажіть кількість випадкових чисел;
• Функція «Розділювач чисел» служить для краси та зручності їх відображення;
• За потреби увімкніть/вимкніть повтори за допомогою галочки;
• Натисніть кнопку "Сгенерувати".

За підсумками Ви отримаєте випадкові числа у заданому діапазоні. Результат генератора чисел може бути скопійований чи надісланий на e-mail. Найкраще буде зробити скріншот або відео даного процесугенерації. Наш рандомайзер вирішить будь-які Ваші завдання!

Зауважимо, що в ідеалі крива густини розподілу випадкових чисел виглядала б так, як показано на рис. 22.3. Тобто в ідеальному випадку кожен інтервал потрапляє однакове числоточок: N i = N/k , де Nзагальна кількість точок, kкількість інтервалів, i= 1, | k .

Мал. 22.3. Частотна діаграма випадання випадкових чисел,
породжуваних ідеальним генератором теоретично

Слід пам'ятати, що генерація довільного довільного числа складається з двох етапів:

• генерація нормалізованого випадкового числа (тобто рівномірно розподіленого від 0 до 1);
• перетворення нормалізованих випадкових чисел r iу випадкові числа x i, які розподілені за необхідному користувачеві(довільному) закону розподілу або у необхідному інтервалі.

Генератори випадкових чисел за способом одержання чисел поділяються на:

• фізичні;
• табличні;
• алгоритмічні.

Фізичні ДСЛ

Прикладом фізичних ГСЧ можуть бути: монета («орел» 1, «решка» 0); гральні кубики; поділений на сектори з цифрами барабан зі стрілкою; апаратурний генератор шуму (ГШ), в якості якого використовують тепловий пристрій, що шумить, наприклад, транзистор (рис. 22.4?22.5 ).

Мал. 22.4. Схема апаратного методу генерації випадкових чисел
Мал. 22.5. Діаграма одержання випадкових чисел апаратним методом

Завдання "Генерація випадкових чисел за допомогою монети"

Згенеруйте випадкове трирозрядне число, розподілене за рівномірним законом в інтервалі від 0 до 1 за допомогою монети. Точність три знаки після коми.

Перший спосіб розв'язання задачі Підкиньте монету 9 разів, і якщо монета впала рішкою, то запишіть "0", якщо орлом, то "1". Отже, припустимо, що в результаті експерименту отримали випадкову послідовність 100110100. Накресліть інтервал від 0 до 1. Зчитуючи числа в послідовності зліва направо, розбивайте інтервал навпіл і вибирайте щоразу одну із частин чергового інтервалу (якщо випав 0, то ліву, якщо випала 1, то праву). Таким чином, можна дістатися до будь-якої точки інтервалу, як завгодно точно. Отже, 1 : інтервал ділиться навпіл і , вибирається права половина, інтервал звужується: . Наступне число, 0 : інтервал ділиться навпіл і , вибирається ліва половина , інтервал звужується: . Наступне число, 0 : інтервал ділиться навпіл і , вибирається ліва половина , інтервал звужується: . Наступне число, 1 : інтервал ділиться навпіл і , вибирається права половина , інтервал звужується: . За умовою точності завдання рішення знайдено: ним є будь-яке число з інтервалу, наприклад, 0.625. У принципі, якщо підходити суворо, то розподіл інтервалів потрібно продовжити доти, поки ліва і права межі знайденого інтервалу не співпадуть між собою з точністю до третього знака після коми. Тобто з позицій точності згенероване число вже не буде відмінним від будь-якого числа з інтервалу, в якому воно знаходиться. Другий спосіб розв'язання задачі Розіб'ємо отриману двійкову послідовність 100110100 на тріади: 100, 110, 100. Після перекладу цих двійкових чиселу десяткові одержуємо: 4, 6, 4. Підставивши спереду «0.», отримаємо: 0.464. Таким методом можуть виходити тільки числа від 0.000 до 0.777 (оскільки максимум, що можна «вичавити» з трьох двійкових розрядів – це 111 2 = 7 8) – тобто, по суті, ці числа представлені в восьмеричній системіобчислення. Для перекладу восьмеричногочисла в десятковеподання виконаємо: 0.464 8 = 4 · 8 1 + 6 · 8 2 + 4 · 8 3 = 0.6015625 10 = 0.602 10. Отже, число, що шукається, дорівнює: 0.602.

Табличні ДСЛ

Табличні ГСЧ як джерело випадкових чисел використовують спеціальним чином складені таблиці, що містять перевірені некорельовані, тобто не залежать один від одного, цифри. У табл. 22.1 наведено невеликий фрагмент такої таблиці. Обходячи таблицю зліва направо зверху донизу, можна отримувати рівномірно розподілені від 0 до 1 випадкові числа з необхідним числом знаків після коми (у прикладі ми використовуємо кожному за число по три знака). Так як цифри в таблиці не залежать одна від одної, то таблицю можна оминати різними способаминаприклад, зверху вниз, або праворуч наліво, або, скажімо, можна вибирати цифри, що знаходяться на парних позиціях.

Таблиця 22.1. Випадкові цифри. Поступово розподілені від 0 до 1 випадкові числа

Випадкові цифри								Поступово розподілені від 0 до 1 випадкові числа
9	2	9	2	0	4	2	6	0.929
9	5	7	3	4	9	0	3	0.204
5	9	1	6	6	5	7	6	0.269

Гідність даного методуу цьому, що він дає справді випадкові числа, оскільки таблиця містить перевірені некоррелированные цифри. Недоліки методу: для зберігання великої кількостіцифр потрібно багато пам'яті; Великі проблеми породження та перевірки такого роду таблиць, повтори під час використання таблиці не гарантують випадковості числової послідовності, отже, і надійності результату.

Розташована таблиця, що містить 500 абсолютно випадкових перевірених чисел (взято з книги І. Г. Венецького, В. І. Венецької «Основні математико-статистичні поняття та формули в економічному аналізі»).

Алгоритмічні ДСЛ

Числа, що генеруються за допомогою цих ГСЧ, завжди є псевдовипадковими (або квазівипадковими), тобто кожне наступне число, що згенерується, залежить від попереднього:

r i + 1 = f(r i) .

Послідовності, складені з таких чисел, утворюють петлі, тобто обов'язково існує цикл, що повторюється нескінченне числоразів. Повторювані цикли називаються періодами.

Перевагою даних ГСЛ є швидкодія; генератори мало потребують ресурсів пам'яті, компактні. Недоліки: числа не можна повною мірою назвати випадковими, оскільки між ними є залежність, а також наявність періодів послідовності квазівипадкових чисел.

Розглянемо кілька алгоритмічних методівотримання ДСЛ:

• метод серединних квадратів;
• метод серединних творів;
• метод перемішування;
• лінійний конгруентний метод.

Метод серединних квадратів

Є деяке чотиризначне число R 0 . Це число зводиться у квадрат і заноситься до R 1 . Далі з R 1 береться середина (чотири середні цифри) - нове випадкове число - і записується в R 0 . Потім процедура повторюється (див. рис. 22.6). Зазначимо, що насправді як випадкове число необхідно брати не ghij, а 0.ghijз приписаним зліва нулем і десятковою точкою. Цей факт відображено як на рис. 22.6 , і наступних подібних малюнках.

Мал. 22.6. Схема методу серединних квадратів

Недоліки методу: 1) якщо на деякій ітерації число R 0 стане рівним нулю, то генератор вироджується, тому важливим є правильний вибір початкового значення R 0; 2) генератор буде повторювати послідовність через M nкроків (у найкращому випадку), де nрозрядність числа R 0 , M¦ основа системи числення.

Наприклад на рис. 22.6: якщо число R 0 буде представлено в двійковій системічислення, то послідовність псевдовипадкових чисел повториться через 24 = 16 кроків. Зауважимо, що повторення послідовності може статися і раніше, якщо початкове число буде вибрано невдало.

Описаний вище спосіб був запропонований Джоном фон Нейманом і належить до 1946 року. Оскільки цей спосіб виявився ненадійним, від нього швидко відмовилися.

Метод серединних творів

Число R 0 множиться на R 1 , з отриманого результату R 2 вилучається середина R 2 * (це чергове випадкове число) і множиться на R 1 . За цією схемою обчислюються всі наступні випадкові числа (див. рис. 22.7).

Мал. 22.7. Схема методу серединних творів

Метод перемішування

У методі перемішування використовуються операції циклічного зсуву вмісту комірки вліво та вправо. Ідея методу полягає у наступному. Нехай у осередку зберігається початкове число R 0 . Циклічно зрушуючи вміст комірки вліво на 1/4 довжини комірки, отримуємо нове число R 0*. Так само, циклічно зрушуючи вміст комірки R 0 вправо на 1/4 довжини комірки, отримуємо друге число R 0**. Сума чисел R 0* і R 0 ** дає нове випадкове число R 1 . Далі R 1 заноситься в R 0 і вся послідовність операцій повторюється (див. рис. 22.8).

Мал. 22.8. Схема методу перемішування

Зверніть увагу, що число, отримане в результаті підсумовування R 0* і R 0 ** , може не вміститися повністю в осередку R 1 . У цьому випадку від отриманого числа мають бути відкинуті зайві розряди. Пояснимо це для рис. 22.8 де всі осередки представлені вісьмома двійковими розрядами. Нехай R 0 * = 10010001 2 = 145 10 , R 0 ** = 10100001 2 = 161 10 тоді R 0 * + R 0 ** = 100110010 2 = 306 10 . Як бачимо, число 306 займає 9 розрядів (у двійковій системі числення), а комірка R 1 (як і R 0) може вмістити максимум 8 розрядів. Тому перед занесенням значення в R 1 необхідно прибрати один «зайвий», крайній лівий біт з числа 306, в результаті чого R 1 піде вже не 306, а 001100102 = 5010. Також зауважимо, що в таких мовах, як Паскаль, «урізання» зайвих бітів при переповненні комірки здійснюється автоматично відповідно до заданого типу змінної.

Лінійний конгруентний метод

Лінійний конгруентний метод є однією з найпростіших і найвживаніших в даний час процедур, що імітують випадкові числа. У цьому вся методі використовується операція mod( x, y), що повертає залишок від поділу першого аргументу на другий. Кожне наступне випадкове число розраховується на основі попереднього випадкового числа за такою формулою:

r i+ 1 = mod ( k · r i + b, M) .

Послідовність випадкових чисел, одержаних за допомогою даної формули, називається лінійною конгруентною послідовністю. Багато авторів називають лінійну конгруентну послідовність при b = 0 мультиплікативним конгруентним методом, а при b ≠ 0 — змішаним конгруентним методом.

Для якісного генератора потрібно підібрати відповідні коефіцієнти. Необхідно, щоб число Mбуло досить великим, тому що період не може мати більше Mелементів. З іншого боку, розподіл, який використовується в цьому методі, є досить повільною операцією, тому для двійкової обчислювальної машини логічним буде вибір M = 2 N, оскільки в цьому випадку перебування залишку від поділу зводиться всередині ЕОМ до двійкової логічної операції"AND". Також широко поширений вибір найбільшого простого числа M, меншого, ніж 2 N: у спеціальній літературі доводиться, що у цьому випадку молодші розряди отримуваного випадкового числа r i+ 1 поводяться так само випадково, як і старші, що позитивно позначається на всій послідовності випадкових чисел загалом. Як приклад можна навести одне з чисел Мерсенна, рівне 2 31 1 , і таким чином, M= 2 31 1 .

Однією з вимог до лінійних конгруентних послідовностей є якомога більша довжина періоду. Довжина періоду залежить від значень M , kі b. Теорема, яку ми наведемо нижче, дозволяє визначити, чи можливе досягнення періоду максимальної довжинидля конкретних значень M , kі b .

Теорема. Лінійна конгруентна послідовність, визначена числами M , k , bі r 0 має період довжиною Mтоді і тільки тоді, коли:

• числа bі Mвзаємно прості;
• k 1 кратно pдля кожного простого p, що є дільником M ;
• k 1 кратно 4, якщо Mкратно 4.

Нарешті, на закінчення розглянемо кілька прикладів використання лінійного конгруентного способу для генерації випадкових чисел.

Було встановлено, що ряд псевдовипадкових чисел, що генеруються на основі даних прикладу 1, буде повторюватися через кожні M/ 4 чисел. Число qзадається довільно перед початком обчислень, проте при цьому слід мати на увазі, що ряд справляє враження випадкового при великих k(а отже, і q). Результат можна трохи покращити, якщо bнепарно і k= 1 + 4 · q У цьому випадку ряд повторюватиметься через кожні Mчисел. Після довгих пошуків kдослідники зупинилися на значеннях 69069 та 71365 .

Генератор випадкових чисел, який використовує дані з прикладу 2, видаватиме випадкові неповторні числа з періодом, рівним 7 мільйонів.

Мультиплікативний метод генерації псевдовипадкових чисел було запропоновано Д. Г. Лехмером (D. H. Lehmer) у 1949 році.

Перевірка якості роботи генератора

Від якості роботи ДСЛ залежить якість роботи всієї системи та точність результатів. Тому випадкова послідовність, що породжується ДСЛ, повинна задовольняти цілу низку критеріїв.

Перевірки, що здійснюються, бувають двох типів:

• перевірки на рівномірність розподілу;
• перевірки на статистичну незалежність

Перевірки на рівномірність розподілу

1) ДСЧ має видавати близькі до наступним значеннястатистичних параметрів, притаманних рівномірного випадкового закону:

2) Частотний тест

Частотний тест дозволяє з'ясувати, скільки чисел потрапило до інтервалу (m r – σ r ; m r + σ r) , тобто (0.5? 0.2887; 0.5 + 0.2887) або, зрештою, (0.2113; 0.7887) . Так як 0.7887 0.2113 = 0.5774, укладаємо, що в хорошому ДСЧ в цей інтервал має потрапляти близько 57.7% з усіх випадкових чисел, що випали (див. рис. 22.9).

Мал. 22.9. Частотна діаграма ідеального ДСЛ
у разі перевірки його на частотний тест

Також необхідно враховувати, що кількість чисел, що потрапили в інтервал (0; 0.5), повинна бути приблизно дорівнює кількості чисел, що потрапили в інтервал (0.5; 1).

3) Перевірка за критерієм «хі-квадрат»

Критерій «хі-квадрат» (χ 2 -критерій) – це один із найвідоміших статистичних критеріїв; він є основним методом, що використовується у поєднанні з іншими критеріями. Критерій «хі-квадрат» було запропоновано у 1900 році Карлом Пірсоном. Його чудова робота сприймається як фундамент сучасної математичної статистики.

Для нашого випадку перевірка за критерієм "хі-квадрат" дозволить дізнатися, наскільки створений нами реальнийДСЧ близький до еталону ГСЧ, тобто задовольняє він вимогу рівномірного розподілу чи ні.

Частотна діаграма еталонногоДСЧ представлена ​​на рис. 22.10. Оскільки закон розподілу еталонного ГСЧ рівномірний, то (теоретична) ймовірність p iвлучення чисел у i-ий інтервал (всього цих інтервалів k) дорівнює p i = 1/k . І, таким чином, у кожний з kінтервалів потрапить рівнопо p i · N чисел ( Nзагальна кількість згенерованих чисел).

Мал. 22.10. Частотна діаграма стандартного ГСЧ

Реальний ДСЧ видаватиме числа, розподілені (причому, не обов'язково рівномірно!) kінтервалам і кожен інтервал потрапить по n iчисел (у сумі n 1 + n 2 + | n k = N ). Як же нам визначити, наскільки ГСЧ, що випробовується, хороший і близький до еталонного? Цілком логічно розглянути квадрати різниць між отриманою кількістю чисел n iта «еталонним» p i · N . Складемо їх, і в результаті отримаємо:

χ 2 експ. = ( n 1 | p 1 · N) 2 + (n 2 | p 2 · N) 2 + | n k – p k · N) 2 .

З цієї формули випливає, що менше різниця в кожному з доданків (а значить, і чим менше значенняχ 2 експ. ), тим більше закон розподілу випадкових чисел, генерованих реальним ГСЧ, тяжіє до рівномірного.

У попередньому вираженні кожному з доданків приписується однакова вага (рівна 1), що насправді може не відповідати дійсності; тому для статистики «хі-квадрат» необхідно провести нормування кожного i-го доданку, поділивши його на p i · N :

Нарешті, запишемо отриманий вираз компактніше і спростимо його:

Ми отримали значення критерію «хі-квадрат» для експериментальнихданих.

У табл. 22.2 наведено теоретичнізначення «хі-квадрат» (? 2 теор.), де ν = N 1 1 це число ступенів свободи, pЦе довірча ймовірність, що задається користувачем, який вказує, наскільки ДСЛ повинен задовольняти вимоги рівномірного розподілу, або p — це ймовірність того, що експериментальне значення 2 експ. буде менше табульованого (теоретичного) ? 2 теор. або одно йому.

Таблиця 22.2. Деякі відсоткові точки 2 -розподілу

	p = 1%	p = 5%	p = 25%	p = 50%	p = 75%	p = 95%	p = 99%
ν = 1	0.00016	0.00393	0.1015	0.4549	1.323	3.841	6.635
ν = 2	0.02010	0.1026	0.5754	1.386	2.773	5.991	9.210
ν = 3	0.1148	0.3518	1.213	2.366	4.108	7.815	11.34
ν = 4	0.2971	0.7107	1.923	3.357	5.385	9.488	13.28
ν = 5	0.5543	1.1455	2.675	4.351	6.626	11.07	15.09
ν = 6	0.8721	1.635	3.455	5.348	7.841	12.59	16.81
ν = 7	1.239	2.167	4.255	6.346	9.037	14.07	18.48
ν = 8	1.646	2.733	5.071	7.344	10.22	15.51	20.09
ν = 9	2.088	3.325	5.899	8.343	11.39	16.92	21.67
ν = 10	2.558	3.940	6.737	9.342	12.55	18.31	23.21
ν = 11	3.053	4.575	7.584	10.34	13.70	19.68	24.72
ν = 12	3.571	5.226	8.438	11.34	14.85	21.03	26.22
ν = 15	5.229	7.261	11.04	14.34	18.25	25.00	30.58
ν = 20	8.260	10.85	15.45	19.34	23.83	31.41	37.57
ν = 30	14.95	18.49	24.48	29.34	34.80	43.77	50.89
ν = 50	29.71	34.76	42.94	49.33	56.33	67.50	76.15
ν > 30	ν + sqrt(2 ν ) · x p+ 2/3 · x 2 p 2/3 + O(1/sqrt( ν ))
x p =	2.33	1.64	0.674	0.00	0.674	1.64	2.33

Прийнятним вважають p від 10% до 90%.

Якщо χ 2 експ. набагато більше ? 2 теор. (тобто pвелике), то генератор не задовільняєвимогу рівномірного розподілу, оскільки значення, що спостерігаються n iзанадто далеко уникають теоретичних p i · N і не можуть розглядатись як випадкові. Іншими словами, встановлюється такий великий довірчий інтервал, що обмеження на числа стають дуже нежорсткими, вимоги до числа слабкими. При цьому спостерігатиметься дуже велика абсолютна похибка.

Ще Д. Кнут у своїй книзі «Мистецтво програмування» зауважив, що мати χ 2 експ. Маленьким теж, загалом, погано, хоча і здається, здавалося б, чудово з погляду рівномірності. Справді, візьміть ряд чисел 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, ?п і вони ? буде практично нульовим, але навряд чи ви визнаєте їх випадковими.

Якщо χ 2 експ. набагато менше ? 2 теор. (тобто pмало), то генератор не задовільняєвимоги випадкового рівномірного розподілу, оскільки значення, що спостерігаються n iнадто близькі до теоретичних p i · N і не можуть розглядатись як випадкові.

А от якщо χ 2 експ. лежить у деякому діапазоні, між двома значеннями 2 теор. , які відповідають, наприклад, p= 25% та p= 50%, можна вважати, що значення випадкових чисел, породжувані датчиком, цілком є ​​випадковими.

При цьому додатково треба мати на увазі, що всі значення p i · N повинні бути досить великими, наприклад, більше 5 (з'ясовано емпіричним шляхом). Тільки тоді (при досить великій статистичній вибірці) умови проведення експерименту вважатимуться задовільними.

Отже, процедура перевірки має такий вигляд.

Перевірки на статистичну незалежність

1) Перевірка на частоту появи цифри у послідовності

Розглянемо приклад. Випадкове число 0.2463389991 складається з цифр 2463389991, а число 0.5467766618 складається з цифр 5467766618. З'єднуючи послідовності цифр, маємо: 24633899915467766618.

Зрозуміло, що теоретична ймовірність p iвипадання i-ї цифри (від 0 до 9) дорівнює 0.1.

2) Перевірка появи серій із однакових цифр

Позначимо через n Lчисло серій однакових поспіль цифр довжини L. Перевіряти треба все Lвід 1 до m, де mЦе задане користувачемчисло: найбільше число однакових цифр у серії.

У прикладі «24633899915467766618» виявлено 2 серії завдовжки 2 (33 і 77), тобто n 2 = 2 і 2 серії завдовжки 3 (999 і 666), тобто n 3 = 2 .

Імовірність появи серії довжиною в Lдорівнює: p L= 9 · 10 | L (Теоретична). Тобто ймовірність появи серії завдовжки один символ дорівнює: p 1 = 0.9 (теоретична). Імовірність появи серії довжиною у два символи дорівнює: p 2 = 0.09 (теоретична). Імовірність появи серії довжиною в три символи дорівнює: p 3 = 0.009 (теоретична).

Наприклад, ймовірність появи серії завдовжки один символ дорівнює p L= 0.9 , тому що всього може зустрітися один символ із 10, а всього символів 9 (нуль не вважається). А ймовірність того, що поспіль зустрінуться два однакові символи «XX» дорівнює 0.1 · 0.1 · 9, тобто ймовірність 0.1 того, що в першій позиції з'явиться символ «X», множиться на ймовірність 0.1 того, що в другій позиції з'явиться такий самий символ "X" і множиться на кількість таких комбінацій 9.

Частина появи серій підраховується за раніше розібраною формулою «хі-квадрат» з використанням значень. p L .

Примітка: генератор може бути перевірений багаторазово, проте перевірки не мають властивість повноти і не гарантують, що генератор видає випадкові числа. Наприклад, генератор, що видає послідовність 12345678912345, при перевірках буде вважатися ідеальним, що, очевидно, не зовсім так.

На закінчення відзначимо, що третій розділ книги Дональда Еге. Кнута «Мистецтво програмування» (том 2) повністю присвячено вивченню випадкових чисел. У ній вивчаються різні методигенерування випадкових чисел, статистичні критерії випадковості, а також перетворення рівномірно розподілених випадкових чисел на інші типи випадкових величин. Викладення цього матеріалу приділено понад двісті сторінок.

Найчастіше під час розробки програм виникає у послідовності випадкових чисел. В іграх, послідовність випадкових чисел може використовуватися у різноманітних ситуаціях: створення монстрів, генерація території, поведінка штучного інтелекту.

Багато речей можна зробити і без генератора випадкових чисел. Ось наприклад, така послідовність чисел не може вважатися випадковою: (0, 1, 2, 3, 4, 5, 6, 7). Тут, знаючи попереднє число, дуже легко вгадати таке. Існують інші послідовності. Наприклад: (0, 1, 3, 2, 6, 7, 5, 4). Тут, вгадати таку кількість значно складніше. Подібні послідовності іноді зручно використовувати у програмах. Ця послідовність визначається кодом Грея. При першому огляді здається, що тут представлені випадкові числа.

Замість використання у програмах послідовності чисел, що підпорядковуються якомусь закону, у багатьох випадках краще використовувати випадково згенеровані.

Генерація псевдовипадкових чисел

Зазвичай використовується генерація псевдовипадкових чисел. Тобто. Числа не зовсім випадкові. Ми вже розглядали функцію rand(). Якщо Ви напишіть програму, що використовує цю функцію, При кожному запуску програми, rand() буде генерувати одну і ту ж послідовність чисел. Послідовність згенерована rand() визначається початковим числом (seed). Спочатку задається початкове число, потім, за певною формулою, обчислюються всі інші числа послідовності. Знаючи початкове число та формулу за якою розраховуються числа, можна обчислити наступне число.

Такі алгоритми називаються детерміністичними (визначеними). Тобто. у яких послідовність чисел створюється з урахуванням початкових даних. У цьому послідовність чисел - псевдовипадкова: тобто. знаючи початкове число, можна дізнатись і всі наступні. Але користувач навряд чи їх дізнається, цифри здаватимуться випадковими.

Одним із визначених (детерміністичних) алгоритмів створення випадкових чисел є лінійно-конгруентний.

Установка початкового значення (для функції rand(), яку ми використовували досі) виглядає приблизно так:

код мовою c++ int i; cin >> i; srnd(i); // Установка початкового значення rand();

Функція srnd встановлює початкове значення i.

Лінійний конгруентний (linear congruential) метод генерації випадкових чисел

Існує багато методів створення випадкових чисел. Лінійно-конгруентний лише один із них. Метод досить старий – 1950х років. Розробив його Деррік Лемер.

Для реалізації алгоритму необхідно задати чотири параметри:

Діапазон значень m, причому m > 0.
Множник a (0<= a <= m).
Інкрементуюче значення c (0<= c <= m).
Початкове значення X0 (0<= X0 < m).

Визначивши ці параметри, можна скористатися формулою:

Xi+1 = (aXi + c) % m (де i більше або дорівнює 0)

i - номер елемента у послідовності.
m - кількість значень у тому числі формується послідовність.
Нагадую що % - залишок від розподілу

Давайте розглянемо приклад невеликої послідовності. Візьміть аркуш паперу, олівець і прорахуйте всі значення:

imax = 5; // формуємо послідовність із 5 елементів
m = 10; // значення послідовність варіюються від нуля до 9
a = 2;
c = 3;
X0 = 6; // Початкове значення (seed)

Xi+1 = (2*Xi + 3) % 10 (де i більше або дорівнює 0)

X1 = 15% 10 = 5
X2 = 13% 10 = 3
X3 = 9% 10 = 9
X4 = 21% 10 = 1
X5 = 5% 10 = 5

Якщо збільшимо послідовність, то значення почнуть повторюватися. Таким чином, кілька неповторних значень у послідовності формують період. Період у цьому прикладі: (5, 3, 9, 1).

Отже, за допомогою лінійного конгруентного методу ми отримали послідовність випадкових чисел із п'яти елементів.

Щоб передбачити значення елементів у послідовності можна скористатися формулою:

Xi+k = (a*k*Xi + (a*k-1)*c/b) % m (де k і i більше або дорівнюють 0)

Тут b = a - 1. При цьому a> = 2, b> = 1.

Обчислимо шостий елемент за допомогою цієї формули (адже ми вже знаємо п'ятий):

X5+1 = (a*1*X5 + (a*1-1)*c/b) % m = (2*1*5 + (2*1-1)*3/1) % 10 = 13 % 10 = 3

Все росто, правда?

У послідовності створеної за допомогою лінійного конгруентного методу і визначеної цілими параметрами m, a, c і X0, період дорівнює m коли виконуються такі умови:
1. Найбільший загальний дільник c і m дорівнює 1.
2.b - кратно будь-якого простого числа, що є дільником m.
3.Якщо m кратно 4, тоді b також кратно 4.

Вибір m

Період не може бути більшим за число m. Отже, m має бути досить великим.

Найкраще якби m дорівнював максимальному елементу в послідовності imax + 1 (одиницю додаємо, так як відлік i йде від нуля). Ще одним популярним вибором є ступінь двійки 2n. За умови, що n - довжина машинного слова в бітах, операції взяття залишку можна позбутися. Якщо m є ступенем двійки, то операцію взяття залишку можна замінити більш швидку операцію поразрядного І (хоча сучасних комп'ютерів це актуально):

x % 2n == x & (2n - 1)
Приклади (x - ціле число):

x % 2 == x & 1;
x % 4 == x & 3;
x % 8 == x & 7;
Дуже часто для m вибирають одне із простих чисел Мерсенна. Часто число 231 - 1 використовується, коли обчислення ведуться з 32 бітними даними.

Множник a

Множник потрібно вибирати так, щоб період був якомога довшим. Існує серйозна проблема з цим коефіцієнтом: при малих значеннях a, якщо поточний елемент послідовності досить малий, цілком імовірно, що наступний елемент теж буде невеликим.

Інкремент з

Цей параметр можна вибирати досить довільно. Дуже часто його задають у вигляді нуля, але при цьому зменшується довжина періоду та X0! = 0.

Початкове значення (seed)

Отже, ми з'ясували, що у послідовності є період. У прикладі період дорівнює всього чотирьом елементам. В інших випадках період може бути дуже великим, але він завжди є! Тобто при генерації випадкових чисел лінійним конгруентним методом, якщо нам потрібна дуже велика послідовність, то в ній значення повторюватимуться з певною періодичністю.

Ось так ось! Генерація послідовних чисел - це справжнісінька містифікація!

Тобто. у нас допустимо є генератор випадкових чисел. Ми використовуємо його для різних програм. Завжди завжди цей генератор створює однакову послідовність чисел (при однакових початкових значеннях). Ми можемо встановити початкове значення.

Взагалі кажучи, за допомогою арифметичних методів не можна побудувати по-справжньому випадкову послідовність чисел. Як невесело жартував наш друг - Джон Фон Нейман:

"Anyone, які використовують аритметичні методи, що виробляються рядом номерів, є в штаті sin." (C) Джон Фон Нейман.

Сумно все це. Ось так живеш-живеш. Перебуваючи в стані незнання, думаєш: "А ось круто було б створити генератор випадкових чисел на основі лінійного когнруентного методу!". А виявляється, що по-справжньому випадкову послідовність таким чином створити не можна. Крах надій! Депресія і ти вже на порозі першої стадії алкоголізму. Цей вантаж неможливості реалізувати свої бажання буде тиснути на тебе все життя, що залишилося... Щось я відволікся. Продовжимо.

Реалізація генерації випадкових чисел

Тепер, коли ми розглянули теоретичні питання щодо генераторів випадкових чисел, давайте подивимося на реалізацію, тим паче вона досить проста.

Для послідовності розглянутої вище, генератор буде виглядати так:

код мовою з++ int rnd() ( int m = 10, a = 2, c = 3; static int x = x0; // x оголошується статичною змінною x = ((a * x) + c) % m; // формула x0 = x ; return x; )

X0 оголошується як глобальна змінна:

int x0 = 6;

Це найпримітивніший варіант генератора. Насправді таке чудовисько використовувати не можна! Але ми це робитимемо!

У цій реалізації ми не відстежуємо можливість переповнення змінних. Замість типу int використовуйте тип _int64 це цілий восьмибайтний тип.

Прості числа

Прості числа - числа які можна розділити без залишку тільки на одиницю і саме число. Наприклад: 11, 3, 7.

Код Грею

Код Грея є послідовністю чисел, де наступне число відрізняється від попередньої одним бітом. Тобто. щоб вгадати послідовність, треба дивитися не так на десяткові числа, але в їх двійкові еквіваленти.

Ось зростаюча послідовність чисел від 0 до 7 у двійковому коді:

000 0
001 1
010 2
011 3
100 4
101 5
110 6
111 7
Використовуючи код Грея, отримаємо таку послідовність:

000 0
001 1
011 3
010 2
110 6
111 7
101 5
100 4
Прості числа Мерсенна

На даний момент відомо 44 числа Мерсенна. З назви відомо, що ці числа - прості, тобто. поділяються лише на одиницю та на самих себе. Крім того, дані числа повинні підкорятися наступній формулі:

Де n також просте число. Для перших дев'яти простих чисел Мерсенна n такі: (2, 3, 5, 7, 13, 17, 19, 31, 61).

Порозрядні логічні операції

Ми вже розглядали логічні операції &&(І) та || (АБО). Існують також порозрядні логічні операції & (порозрядне І) та | (порозрядне АБО). Працюйте операція так:

5 && 3; // && завжди повертає нуль або одиницю (тут 1)
5 & ​​3; // & повертає число

101
011
=
001 // в результаті одиниця
Тобто в цій операції порівнюються відповідні позиції двох чисел і якщо вони рівні, то в результуючому числі в даній позиції пишеться 1, інакше - нуль.
5 | 3; // | повертає число

101
011
=
111 // В результаті 7

Степінь числа

Щоб звести число в будь-який ступінь, можна скористатися функцією pow(x,y). При цьому ви отримаєте xy. Функція перевантажена, тому можна використовувати з різними типами. Для використання функції pow() необхідно увімкнути заголовний файл math.h.
Інші генератори випадкових чисел

Крім лінійного конгруентного генератора існує багато інших. Наприклад Вихор Мерсенна, винайдений двома японськими вченими (не пам'ятаю як з звуть) в 1997. У нього дуже великий (дуже великий це м'яко сказано) період. До речі, вихор Мерсенна використовує лінійний конгруентний генератор встановлення початкового значення (seed).

Генератори випадкових чисел застосовуються під час шифрування. Але тут використовуються спеціальні генератори – криптографічно захищені генератори псевдовипадкових чисел. Наприклад, блоковий шифр (block cipher), потоковий шифр (stream cipher), який був розроблений на основі шифру Вернама.

Вправи:

Реалізуйте генератори випадкових чисел з урахуванням лінійного когруентного методу. Як параметри скористайтеся такими:

m = 232; a = 1664525; c = 1013904223. Дані параметри використовувалися в прикладі реалізації генератора в одній старій книжці за Фортраном.
m = 232; a = 214013; c = 2531011; Дані параметри використовують у реалізації методу Visual C++. У цьому беруться старші біти 30..16. Беруться верхні біти, т.к. у лінійному конгруентному методі нижні біти набагато менш випадкові. Так як ми поки що не вміємо брати конкретні біти, можете використовувати все число.
Як m виберіть один із чисел Мерсенна. Почніть із малих (23-1,25-1). Спробуйте підставити 231-1 та 261-1.