стартового числа і при різних його значеннях виходять різні послідовності випадкових чисел. У той же час, багато властивості цієї послідовності визначаються вибором коефіцієнтів у формулі і не залежать від вибору стартового числа. Ясно, що послідовність чисел, що генерується таким алгоритмом, періодична з періодом, не перевищуючи m. При цьому довжина періоду дорівнює m тоді і тільки тоді, коли:
) НОД (c, m)=1 (тобто c і m взаємно прості)
) a - 1 кратно p для всіх простих p - дільників m;
) a - 1 кратно 4, якщо m кратно 4.
Статистичні властивості одержуваної послідовності випадкових чисел повністю визначаються вибором коефіцієнтів a і c.
Метод Фібоначчі
Цікавий клас генераторів псевдовипадкових послідовностей заснований на використанні послідовностей Фібоначчі. Класичний приклад такої послідовності {0,1,1,2,3,5,8,13,21,34 ...} - за винятком перших двох її членів, кожний наступний член дорівнює сумі двох попередніх.
Особливості розподілу випадкових чисел, що генеруються лінійним конгруентним алгоритмом, роблять неможливим їх використання в статистичних алгоритмах, що вимагають високого дозволу.
У зв'язку з цим лінійний конгруентний алгоритм поступово втратив свою популярність, і його місце зайняло сімейство Фібоначчієва алгоритмів, які можуть бути рекомендовані для використання в алгоритмах, критичних до якості випадкових чисел. В англомовній літературі Фібоначчієва датчики такого типу називають зазвичай Subtract-with-borrow Generators (SWBG).
Найбільшу популярність Фібоначчієва датчики отримали у зв'язку з тим, що швидкість виконання арифметичних операцій з речовими числами зрівнялася зі швидкістю цілочисельний арифметики, а Фібоначчієва датчики природно реалізуються у речовій арифметиці.
Один з широко поширених Фібоначчієва датчиків заснований на наступній итеративной формулою:
=
де - дійсні числа з діапазону [0,1), a, b - цілі позитивні числа, звані лагами. Для роботи Фібоначчієва датчику потрібно знати max {a, b} попередніх згенерованих випадкових чисел. При програмної реалізації для зберігання згенерованих випадкових чисел використовується кінцева циклічна чергу на базі масиву. Для старту Фібоначчієва датчику потрібно max {a, b} випадкових чисел, які можуть бути згенеровані простим конгруентним датчиком.
Лаги a і b - магічні і їх не слід вибирати довільно. Рекомендуються наступні значення лагів: (a, b)=(55,24), (17,5) або (97,33). Якість одержуваних випадкових чисел залежить від значення константи, a чим воно більше, тим вище розмірність простору, в якому зберігається рівномірність випадкових векторів, утворених з отриманих випадкових чисел. У той же час, зі збільшенням величини константи a збільшується обсяг використовуваної алгоритмом пам'яті.
Значення (a, b)=(17,5) можна рекомендувати для простих додатків, що не використовують вектори високої розмірності з випадковими компонентами. Значення (a, b)=(55,24) дозволяють отримувати числа, задовільні для більшості алгоритмів, вимогливих до якості випадкових чисел. Значення (a, b)=(97,33) дозволяють отримувати дуже якісні випадкові числа і використовуються в алгоритмах, що працюють з випадковими векторами високої розмірності. Отримувані випадкові числа володіють хорошими статистичними властивостями, причому всі біти випадкового числа рівнозначні за статистичними властивостями.
Вихор Мерсенна
Вихор Мерсенна (Mersenne twister) - це генератор псевдовипадкових чисел, заснований на властивостях простих чисел Мерсенна і забезпечує швидку генерацію високоякісних псевдовипадкових чисел. Вихор Мерсенна позбавлений багатьох недоліків властивих іншим ГПСЧ таких як малий період, передбачуваність, легко виявляється статистична залежність.
Вихор Мерсенна є Віткової регістром зсуву з узагальненої віддачею (twisted generalised feedback shift register, TGFSR). Вихор - Це перетворення, яке забезпечує рівномірний розподіл генеруються псевдовипадкових чисел в 623 вимірах (для лінійних конгруентних генераторів воно обмежене 5-ю вимірами). Тому кореляція між послідовними значеннями у вихідний послідовності Вихора Мерсенна пренебрежимо мала.
Вихор Мерсенна має величезний період, а саме, доведено, що його період дорівнює числу Мерсенна 219937? 1, що більш ніж достатньо для багатьох практичних застосувань.
Існують ефективні реалізації Вихора Мерсенна, що перевершують за швидкістю багато стандартні ГПСЧ (зокрема, в 2-3 рази швидше лінійних конгруентних генераторів). Алгоритм заснований на наступному рекуррентном вираженні:
=+ () A, (k=0,1,2 ...)
де n - ціле, яке позначає ступінь рекурентності, - ціле, 1 l...
