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

Припустимо, що ми віробляємо шестирозрядні псевдовипадкові десяткові цілі числа. Виберемо довільне шестирозрядне число 678542, піднесемо його до квадрату і отримаємо 460419245764. Виділимо із середини отриманого числа шестирозрядне число 419245, піднесемо його до квадрату і т.д. Таким шляхом утворюється послідовність псевдовипадкових чисел, в якій кожне наступне число визначається попереднім.

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

Математично метод має вигляд співвідношення x_n+1 = (a× x_n + b) mod m, n = 0, 1...,

параметрами якого є

x₀ – початкове значення,

a – множник,

b – приріст,

m – модуль.

Указані числа мають природні обмеження, а саме: модуль m – ціле додатне число, числа x₀, a і b –цілі, невід’ємні і менші модуля m.

Властивістю даного співвідношення є те, що отримувана послідовність обов’язково

зациклюється

1). Значення модуля m має бути досить великим, щоб було можливо отримувати більші значення періоду. Доцільно вибирати значення m рівними степеням двійки, тобто виду 2^k

2). Числа a і m – взаємно прості, числа b і m – теж взаємно прості.

3). Початкове значення x⁰ – довільне, що задовольняє умовам 0 ≤ x0 < m

Оцінка якості послідовності псевдовипадкових чисел.

Приклад 1. У відповідності з рекомендаціями лінійного конгруентного методу виберемо m = 8, a = 3, b =7, x₀ = 1. Отримуємо наступну послідовність псевдовипадкових чисел: 1, 2, 5, 6, 1, 2, 5, 6. Перід послідовності рівний 4.

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

Приклад 2. У відповідності з рекомендаціями лінійного конгруентного методу виберемо m = 8, a = 5, b = 3, x₀ = 1. Отримуємо наступну послідовність псевдовипадкових чисел: 1, 0, 3, 2, 5, 4, 7, 6. Перід послідовності рівний 8, тобто максимальний. Але сама послідовність не має вигляду випадкової, оскільки числа в ній розташовані парами.

Цей приклад є підтвердженням того, що потрібне дослідження рівня випадковості отриманої послідовності. Щоб вирішити питання, чи справляє послідовність враження випадкової, досить ефективним є застосування візуального тестування.

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