Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторна робота №1
«Генерація послідовності псевдовипадкових чисел»
Мета роботи
Навчитися створювати засобами Асемблер системні генератори псевдовипадкових чисел для систем програмування та власних програм.
Теоретичні відомості
Загальні відомості про псевдовипадкові послідовності
Випадкові числа застосовують в широкому діапазоні математичних алгоритмів, які знаходять вжиток як в задачах чистого програмування, так і в статистичних методах, типу метода Монте-Карло. Для того щоб отримати такі послідовності, використовуються так звані генератори псевдовипадкових послідовностей.
Генератор псевдовипадкових послідовностей (ГПВЧ, англ. Pseudorandom number generation, PRNG) – алгоритм, що генерує послідовність чисел, елементи якої майже не залежні один від одного й підкоряються заданому розподілу (зазвичай рівномірному).
Ці генератори звуться псевдовипадковими через те, що отримані в їх результаті послідовності все-таки містять в собі деякі закономірності. Американський математик Джордж Марсалія склав так звані статистичні тести DIEHARD, які перевіряють їх наявність у алгоритмі ГПВЧ. Серед них наступні:
За результатами цих, а також інших тестів, повинна бути отримана послідовність із розподілом по Пуассону чи за нормальним законом розподілу. Якщо послідовність такому закону не відповідає, тест вважається проваленим.
На сьогодні в програмуванні використовуються наступні алгоритми, які частково, або повністю проходять тести DIEHARD.
Лінійний конгруентний алгоритм (алгоритм Лемера)
Цей алгоритм полягає у обчисленні деякої рекурсивної послідовності по модулю. Формула надзвичайно проста:
а, с – деякі цілочисельні аргументи.
Отримана послідовність цілком залежить від обраного числа хn і при різних його значеннях будуть отримані різні ряди. В той же час, чільна частина статистичних властивостей цих рядів залежить від значень аргументів а та с, і від стартового числа не залежать. Така двоїстість дозволяє генерувати статистично хороші послідовності, однак він не є криптостійким через наявність однозначної залежності від початкового числа.
Зазвичай цей алгоритм використовується для навчальних посібників, а також входить в набір стандартних функцій більшості мов програмування, оскільки допускає реалізації генератора ПВЧ як із будь-якою розрядністю.
При реалізації цього алгоритму часто обирають значення 2с, де с – число бітів в машинному слові. Це пришвидшує алгоритм, адже дозволяє позбавитись операції цілочисельного ділення, але в такому разі збільшується залежність від хn і знижується криптостійкість.
Алгоритм Mother-of-All
Алгоритм «Всезагальна матір» був запропонований Джорджем Марсалією як узагальнення конгруентного методу. Він базується на множенні із перенесенням і має піреод в 2250, на відміну від класичного алгоритму Лемера. Він позбавлений всіх його недоліків, однак він може бути реалізований виключно із 64-бітною розрядністю, через великий розмір коефіціентів. Це робить його погано застосовним для асемблерних програм, а також повільним, тому що для отримання псевдовипадкових послідовностей із малою кількістю цифр необхідно використовувати як початкові аргументи числа в діапазоні від 0 до 1.
S – наудачу взяте число, яке править за «seed», початкове число послідовності.
На практиці через велику розрядність цього алгоритму, як xn так і С на початковій ітерації встановлюють рівними і визначають як випадкове число, отримане за допомогою іншого ГПВЧ, або найчастіше – поточне значення таймера.
Алгоритм вихору (Mersenne Twister)
Алгоритм вихору Мерсенна був запропонований 1997р. Мацумото Макото та Нішімурою Такуджі. Заснований він на властивостях простих чисел і забезпечує швидку генерацію псевдовипадкових послідовностей.
Прості числа Мерсенна широко застосовують в математичному програмуванні, бо вони засновані на ступені двійки. Загальна формула таких чисел: Mn = 2n – 1, де n – натуральне число.
Відповідно, найпростіша послідовність простих чисел виглядатиме наступним чином: Mn = 1, 3, 7, 15, 31…
Тим не менш цей алгоритм застосований лише в обмеженому спектрі задач, так як не є криптостійким. Достатньо аналізу 624 елементів послідовності, і цього досить для визначення будь-якого іншого її елементу. Тим не менш. на сьогодні існує тільки один вид шифрувального алгоритму, заснований на вихрі Мерсенна – запропонований він все тим же Мацумото – однак із іншими криптографічними алгоритмами він виграє виключно за рахунок швидкості.
Як і попередній, цей алгоритм має високу розрядність. Для отримання масива 32-бітних чисел необхідні 42-бітні обчислення. У якості стартової точки також вибирається наугад взяте число, наприклад, поточне значення таймера. Далі числа послідовно множаться за модулем два і зсуваються два рази вправо і два рази вліво на кількість бітів, що відповідають простим числам Мерсенна, і множаться на 16-бітні коефіціенти. Процедура зсуву, власне, і створює той самий вихор. Так, наприклад, для 32-бітних чисел математичн алгоритм буде виглядати наступним чином:
Mn = 1812433253 * (Mn-1 ⊕ (Mn-1 >> 30 + n)
Mn = Mn >> n
Mn = (Mn << 3) ^ 2636928640
Mn = (Mn >> 7) ^ 4022730752
Mn = Mn << 15
В такий спосіб можна згенерувати послідовність 64-бітних чисел. з яких беруться молодші 32 біт. Аналогічним способом генеруються будь-які інші послідовності, також можуть змінюватись і прості числа, на які відбувається зсув. Якщо такі числа більші за 64, відбувається циклічний зсув.
Алгоритм Xershift
Цей алгоритм також запропонований Джорджем Марсалією, і є найбільш швидким з усіх алгоритмів. Він залежить від 4 коефіціентів, на основі яких генерує псевдовипадкові числа. Наприклад, якщо існують коефіціенти x, y, z, w, то для випадкового числа t маємо:
t = x ⊕ (x << 11)
x = y, y = z, z = w
t = w ⊕ (w >> 19) ⊕ (t ⊕ (t >>8))
w = t
Зациклюючи даний алгоритм, можна отримати послідовність високоякісних псевдовипадкових чисел. Крім того, в ньому використовується тільки прості операції, що робить його найбільш простим і швидким алгоритмом. Крім того, замість зациклювати основні аргументи алгоритму x i w, їх можна обирати за допомогою іншого ГПВЧ, таким чином підвищуючи криптостійкість метода.
Інші математичні алгоритми псевдовипадкових рядів
Крім вищеописаних існує ще безліч різноманітних способів генерувати псевдовипадкові числа. Яскравим прикладом є алгоритм Блюма-Блюма-Шуба, запропонований Ленором Блюмом, Мануелем Блюмом та Майклом Шубом. Він заснований на рекурсивному додаванні за модулем два добутку двох простих чисел P та Q і наступним вибором біта парності результуючого числа. Із послідовності вибраних бітів й складається псевдовипадкове число.
Сам алгоритм може бути описаний наступними виразами:
Mn = (Mn-1)2 mod (P*Q)
Zn = parity (Mn)
Також заслуговує уваги метод Фібоначчі з запізненням. Цей метод дуже добре комбінується із уже описаним вище методом xorshift, так як в ньому використовується два числа (які можуть бути використані у якості основних параметрів). Основна формула такого генератора надзвичайно проста:
Mn = (Mn-a + Mn-b) mod m
Параметри a та b використовуються як «коефіціенти запізнення». Якщо у якості початкових чисел послідовності використовуються числа, що отримані за допомогою xorshift, алгоритм стає криптостійким.
Крім того, існують числені модифікації алгоритма Лемера, як, наприклад, алгоритм Парка-Міллера – в якому у якості модуля використовується просте число Мерсенна. Для криптографічних систем розробляються окремі алгоритми – типу алгоритму Наора-Рейнгольда із складеним математичним апаратом, який дозволяє генерувати майже бездоганні статистичні послідовності.
Для комп’ютерної графіки теж існують спеціалізовані алгоритми. Один із них , який є складовою математичного забезпечення GPU сучасних відеоплат, називається WarpStandart. Він характеризується дуже високим періодом – 21024, і характеризується високим споживанням оперативної пам’яті.
Нарешті, існує цілий клас гібридних ГПВЧ, в яких поєднується два або більше алгоритми (вище уже був описаний варіант гібрідизації метода Фібоначчі із методом xorshift). Ідея таких генераторів надзвичайно проста – якщо дві послідовності взаємно прості, то період такого генератора буде дорівнювати добутку їх періода.
Рекомендації по реалізації
Розглянемо просту реалізацію алгоритму Лемера:
A div 7
X div 1
C div 13
M div 255
N div 6
Перемістимо номер елемента послідовності, який необхідно отримати в регістр CX і організуємо цикл, в якому виконаємо необхідні математичні дії. В регістрі АХ зберігається поточний елемент послідовності.
mov CX, X
cycles:
mov AX, X
mul A
mov AX, C
div X
mov X, DX
mov AX, DX
loop cycle
Цикл перерветься на необхідній нам послідовності. Щоб вивести її на екран, знадобиться процедура виведення на екран десяткового числа. Для цього використайте стандартну процедуру, здатну вивести будь-яке 16-бітне число (аналогічна процедура може бути написана як для 32-бітного, так і для 64-бітного числа).
Щоб використовувати цю процедуру, збережіть в стеку вміст регістра СХ.
printDecimal proc
mov bx, 0
mov cx, 10
digits:
inc bx
xor dx, dx
div cx
push dx
cmp ax, 0
jne digits
mov ah, 2h
print:
pop dx
cmp bx, 0
je exit
add dl, ‘0’
int 21h
dec bx
cmp bx, 0
je exit
jmp print
exit:
mov dl, ‘ ‘
int 21h
ret
printDecimal endp
code ends
end main
Для генерації початкових елементів послідовності (для реалізації, наприклад, алгоритму «Мати всіх») можна скористатись функцією визначення поточної константи часу 2ch переривання переривання 21h. В регістрах ch, cl, dh, знаходитимуться відповідно години, хвилини, секунди, і сотні долі секунди поточного часу. Відповідний код матиме вигляд:
mov ah, 2ch
int 21
Більш складним способом є отримання поточного числа тактів мікропроцесора. Для цього застосовується команда rdtsc, яка переміщує поточне значення лічильника тактів в регістр edx;eax. Цю команду, однак, можна використовувати лише для мікропроцесорів Pentium та вище.
Подальша реалізація алгоритмів генерації псевдовипадкових послідовностей полягає у правильній реалізації математичних перетворень.
Порядок виконання роботи
Необхідний інструментарій
Borland Turbo Assembler, або Nasm, або Microsoft Assembler (masm).
Контрольні питання