t; m lt; n,
А - матриця розміру WxW
У правій частині позначає старші wr біт , І, молодші r біт
3. Тестування псевдовипадкових послідовностей
Тестування псевдовипадкових послідовностей (ПСП) - сукупність методів визначення міри близькості заданої псевдовипадкової послідовності до випадкової. У якості такого заходу зазвичай виступає наявність рівномірного розподілу, великого періоду, рівної частоти появи однакових подстрок і т.п.
Існує кілька методів тестування ПСП:
. Графічний тест.
До цієї категорії відносяться тести, результати яких відображаються у вигляді графіків, що характеризують властивості досліджуваної послідовності. Серед них:
а) гістограма розподілу елементів послідовності (дозволяє оцінити рівномірність розподілу символів в послідовності і визначити частоту повторення кожного символу);
б) розподіл на площині (призначене для визначення залежності між елементами послідовності);
в) перевірка серій (дозволяє визначити рівномірність окремих символів в послідовності, а так само рівномірність розподілу серій з k біт);
г) перевірка на монотонність.
. Статистичний тест.
На відміну від графічних тестів, статистичні тести видають чисельну характеристику послідовності і дозволяють однозначно сказати, чи пройдено тест.
4. Генератор випадкових чисел в Borland C ++
У мовах програмування зазвичай передбачені функції, що дозволяють генерувати випадкові числа в певному за замовчуванням діапазоні. Насправді генеруються невипадкові, а так звані псевдовипадкові числа; вони виглядають випадково, але обчислюються за цілком конкретною формулою. Але для простоти далі ми все одно будемо називати їх випадковими.
У Borland C ++ (як і в багатьох інших реалізаціях C/C ++) використовується лінійний конгруентний ГВЧ. Довжина періоду цього ГСЧ становить 232 числа.
У мові програмування C отримати випадкове число можна за допомогою функції rand (), яка входить в стандартну бібліотеку мови. Ця функція не приймає ніякі параметри. Функція rand () повертає ціле число від 0 до значення присвоєного константі RAND_MAX. Значення RAND_MAX залежить від системи і визначено в заголовному файлі stdlib. h. Так, наприклад, воно може бути дорівнює 32767 (двухбайтовое ціле) або 2147483647 (чотирьохбайтове ціле).
Код нижче виводить на екран 50 випадкових чисел:
# include lt; stdio. h gt;
# include lt; stdlib. h gt; () {i; (i=1; i lt;=50; i ++) {(% 15d raquo ;, rand ()); (i% 5 == 0) printf ( n );
}
}
У тілі циклу здійснюється перехід на новий рядок після кожних виведених на екран п'яти чисел. Для цього використовується вираз, в якому знаходиться залишок від ділення i на 5, результат порівнюється з 0. Щоб після першого числа не відбувається перехід на новий рядок, i спочатку присвоюється одиниця, а не нуль (т.к.0 ділиться на 5 без залишку ).
При кожному запуску програми числа залишаються однаковими. Навіть якщо ви перекомпіліруете програму, результат не зміниться. Даний ефект пов'язаний з тим, що початкове (инициализирующее) число, яке підставляється в формулу обчислення першого та наступних псевдовипадкових чисел, для кожної системи завжди одне і те ж.
Однак це початкове число можна змінити за допомогою функції srand (), якою як параметр передається будь-яке ціле число. Инициализирующее значення прив'язують до якого-небудь процесу, що протікає в операційній системі, наприклад, до годинника. Час (враховуючи не тільки час доби, але і дату) ніколи не буває однаковим. Значить значення для srand (), перетворене в ціле з системного часу, буде різним.
Поточний час можна дізнатися за допомогою функції time (), прототип якої описаний у файлі time. h. Передавши time () як параметра NULL, ми отримаємо ціле число, яке можна передати в srand () :( time (NULL));
Ситуація з речовими числами виглядає дещо по-іншому. По-перше, ми не можемо отримати залишок від ділення, якщо ділене або дільник дробове число. По друге при обчисленні довжини діапазону не можна додавати одиницю. Таким чином формула для отримання випадкового дійсного числа виглядає так:
(float) rand ()/RAND_MAX * (max - min) + min
Функція rand () генерує будь-яке випадкове число від 0 до RAND_MAX з рівною часткою ймовірності. Іншими словами, у числа 100 є такий же шанс випасти, як і у чис...
