Старий погляд на нові речі

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

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

"Ми ніколи не розуміємо, які скарби перед нами. Знаєш чому? Тому що люди взагалі не вірять в скарби." Пауло Коельо "Алхімік"

Озирніться навколо і ви зрозумієте, що світом правлять випадковості - вони скрізь і всюди: від шуму в радіоприймачі, до гри в орлянку і карт Таро, від російської рулетки і до ... генерування паролів. І адже не відомо, що більш небезпечно.

Просто дивно наскільки вся наша цивілізація (від великого IT-фахівця, до простого селянина) залежить від різного роду випадковостей. А найсмішніше те (і таємниче) ми самі ставимо себе в залежність від якихось генераторів випадкових чисел (ГВЧ) (random number generator). Причому на превеликий жаль аж ніяк не всі ГВЧ є дійсно випадковими. Погляньте хоча б на популярну функцію rand () зі стандартної бібліотеки stdlib.h - її оманливе поведінка докладно розглядається в статті "Приборкання rand () і random ()". На перший погляд звучить дуже забавно, що на випадкові числа навіть накладають ГОСТ-и.

Як же взагалі отримують ці чудові числа? Існують наступні способи отримання випадкових чисел: 1. Апаратний спосіб. Можна використовувати спеціальні приставки - генератори (датчики) випадкових чисел. Цей спосіб не вимагає додаткових обчислювальних операцій ЕОМ з вироблення випадкових чисел, а необхідна тільки операція звернення до зовнішнього пристрою (датчика). В якості фізичних ефектів лежать в основі таких генераторів можуть бути використані шуми в електронних і напівпровідникових приладах (обумовлені наступним: тепловими флуктуаціями, випадковими варіаціями числа частинок в електронних потоках, хаотичним перемагнічуванням доменів у феромагнітних сердечниках), явище розпаду радіоактивних елементів. 2. Табличний спосіб. Випадкові числа, оформлені у вигляді таблиці, поміщаються в зовнішню чи оперативну пам'ять ЕОМ. Запас чисел обмежений. Ефективно використовувати тільки для порівняно невеликих таблиць, тому що масив займає деякий об'єм оперативної пам'яті! 3. Алгоритмічний спосіб. Формування випадкових (вірніше - псевдовипадкових) чисел за допомогою спеціальних алгоритмів. На генерацію псевдовипадкових чисел витрачається машинний час.

Нижче наведені приклади алгоритмічного отримання випадкових чисел: Однією з історично перших процедур отримання псевдовипадкових чисел була процедура, яка називається метод серединних квадратів. Нехай є 2n-розрядне число, менше 1. Зведемо його в квадрат, а потім відберемо середні 2n-розрядів, які й будуть черговим числом псевдослучйной послідовності. Приклад: x0 = 0.2152 x0 ^ 2 = 0.04631104 x1 = 0.6311 x1 ^ 2 = 0.39828721 x2 = 0.8287 ...

Головний недолік цього методу - наявність кореляції між числами послідовності, а іноді випадковість може бути відсутнім зовсім. Приклад: x0 = 0.4500 x0 ^ 2 = 0.20250000 x1 = 0.2500 x1 ^ 2 = 0.06250000 x2 = 0.2500 ...

Інший широко застосовуваний тип генераторів випадкових чисел-це так звані конгруентні генератори. Для генерації використовується наступна рекурентна послідовність: X (n +1) = a * X (n) + c * (mod M). a називається мультиплікатором, c - инкрементом, M - модулем. mod - це залишок від ділення (основа системи числення).

На підставі такого генератора працює вже згадувана Дволика функція rand ().

Мабуть пора поглянути на ці цікаві числа. Давайте розглянемо наступну послідовність чисел:

8628034825 3421170679 8214808651 3282306647 0938446095 5058223172 5359408128 4811174502 8410270193 8521105559 6446229489 5493038196 4428810975 6659334461 2847564823 3786783165 2712019091 4564856692 3460348610 4543266482 1339360726 0249141273 7245870066 0631558817 4881520920 9628292540 9171536436 7892590360 0113305305 4882046652 1384146951 9415116094 3305727036 5759591953 0921861173 8193261179 3105118548 0744623799 6274956735 1885752724 8912279381 8301194912 9833673362 4406566430 8602139494 6395224737 1907021798 6094370277 0539217176 2931767523 8467481846 7669405132 0005681271 4526356082 7785771342 7577896091 7363717872 1468440901 2249534301 4654958537 1050792279 6892589235 4201995611 2129021960

Як по-вашому є вона випадковою? Хтось може дати позитивну відповідь. Хтось, можливо відчуваючи підступ, відповість негативно. По-справжньому мудро надійде той, хто не стане відповідати, засумнівавшись в коректності питання. Справа в тому (тільки не дуже дивуйтеся), що ця послідовність відноситься до числа ПІ (PI), тобто, точніше кажучи, це последователность чисел з 81-го по 720-й знак після коми числа ПІ. То чи можна назвати ці числа випадковими? Нижче дається відповідь на це питання:

Thus the successive digits of PI are as determinate as any numbers can be, yet a block of a thousand of them might serve quite well as random numbers for agricultural experiments, not because they are random but because they are probably uncorrelated with the peculiarities of a particular set of plots. Supplementation by "chance" thus means (apart from minor, special requirements) supplementation by taking effects (or variety) from a system whose behaviour is uncorrelated with that of the main system. An example was given in S.12/15. Thus if a chance variable were required, yesterday's price of a gold-share might be suitable if the main system under study was a rat in a maze, but it would not be suitable if the main system were a portion of the financial-economic system .)

(Ashby WR An introduction to CYBERNETICS) Для тих, хто не дуже сильний в англійській, або в кого перекладача немає:) дам невелике пояснення: "послідовність десяткових знаків числа ПІ є певними (детермінованими), але блок з тисячі знаків міг би служити, як випадкові числа, дуже добре, для сільськогосподарських експериментів, не тому, що вони випадкові, а тому, що вони ймовірно не корельовані зі специфічними особливостями земельних ділянок. ... "

А тепер давайте подивимось які ж кошти для генерації "випадкових" чисел надає улюблена ОС Linux. Загляньте в директорію / dev / і там ви зможете побачити дві дивовижні пристрої, а саме / dev / random та / dev / urandom, які є спеціальними пристроями, що надають доступ до засобів генерування випадкових чисел, вбудованим в ядро. Давайте подивимося, що видають ці пристрої. Зробити це нескладно. Скористаємося утилітою od (параметри-t x1 кажуть, щоб утиліта видавала вміст файлу в шістнадцятковому форматі. Додаткову інформацію по цій утиліті можете отримати по команді man od).

$ Od-t x1 / dev / random 0000000 cc fe 69 8b ce 70 18 1c da de 1962 9e f4 3f 3b 9a 0000020 f2 b0 16 9c ab 5c 5f 35 7f 5d d1 75 00 9b ce 16 0000040 4f af b0 6b 4e 1952 50 32 b1 0c 36 70 e9 f2 5d b6 0000060 5d 7c 2d 28 23 d7 83 d3 38 a5 17 98 05 3d 06 dd 0000100 93 60 b4 d7 84 9f ce 07 ec 6a 4d e8 32 2b 2b 04
$ Od-t x1 / dev / urandom 0000000 9d f8 32 64 9e 8e f0 26 0d 1e c4 f5 bb 99 37 f0 0000020 9a c1 37 8a 02 2d 78 81 64 d8 eb 6c 23 листопада 1919 5b 0000040 10 e1 7d 3b 30 28 Лютий 1997 a9 57 c4 27 2c 4e 4f ef 0000060 ea 7a 4e a7 c1 d6 95 96 0a 99 f0 d4 cc 59 84 94 0000100 dd f6 85 df e9 5a 37 53 1c 04 b7 ba f9 3a 8f 35

Як бачите обидва пристрої видають випадкові числа. На прикладі поки незрозуміло, чим же відрізняються файли / dev / random та / dev / urandom один від одного. Коли ж ви запустите утиліту і трохи почекаєте, то побачите, що / dev / urandom не припиняє видавати числа, тоді як / dev / random незабаром перестане це робити (виведення нових чисел припиниться), але як тільки ви поворушіть мишкою або натиснете клавіші на клавіатурі , як пристрій видає чергову порцію чисел (погодьтеся дуже нагадує старанне натискання різних клавіш при генеруванні ключа PGP). Тобто суттєва відмінність між цими пристроями полягає в тому, що / dev / random створює тільки випадкові байти, які виходять від зовнішнього джерела хаосу - користувача!! Але запас випадкових чисел в ядрі обмежений і якщо читати велику кількість байт з файлу (і не робити ніяких користувача дій), то система заблокує операцію читання. Ну а / dev / urandom повертає стільки байт, скільки треба, тобто коли запас випадкових чисел в ядрі закінчується, то за справу береться генератор випадкових чисел. Таким чином random більш кращий для генерування ключів доступу та інших даних, до яких пред'являється вимоги підвищеної випадковості, так як urandom видає псевдовипадкові числа.

На основі цих чудових пристроїв можна легко написати простеньку функцію генерування випадкових чисел:

/ / For low-level file working

# Include

# Include

# Include

# Include

/ / Generate random numbers: [0 .. number)

int rnd (int number)

{

/ / Read random numbers from / dev / urandom

/ / For store files descriptor

static int dev_urandom =- 1;

/ / Errors flags

bool urandom_error = false;

bool read_error = false;

int bytes;

uint data;

if (dev_urandom ==- 1)

{

dev_urandom = open ("/ dev / urandom", O_RDONLY);

if (dev_urandom ==- 1)

urandom_error = true;

}

if (! urandom_error)

{

bytes = read (dev_urandom, & data, sizeof (data));

if (bytes! = sizeof (data))

read_error = true;

else

{

data = data% (number +1);

}

}

return data;

}

Але головне не треба забувати такого розумного дядька, як Джон фон Нейман, який говорив:

Якщо уподібнитися різного типу богошукачам можна сказати, що випадковості (у нашому випадку - ГВЧ)-це одна з мов Cтаріка. Інші ж застосування ГВЧ надзвичайно цікаві - від когнітивної еволючіі і моделювання AI (читайте про Creativity Machine на membrana.ru), до аналізу безпеки (викликає розчулення застосування ГВЧ у статті "Випадкові числа спрощують алгоритм").

Але як завжди людина з надією дивиться в майбутнє, навіть якщо воно визначається якимось ГВЧ.

Додаткова інформація 1. man 4 random 2. Теорія Ймовірності (online-підручник) 3. random.org 4. RFC 1750 5. Ashby WR An introduction to CYBERNETICS, CHAPMAN & HALL, London, 1956. (Російський переклад: Ешбі У. Р. Введення в кібернетику, Видавництво іноземної літератури, М.: 1959) Дуже раджу дістати і прочитати цю книгу! В інтернеті можна скачати ел. варіант книги (англійською), у форматі. pdf (близько 2 Mb) на сторінці http://pespmc1.vub.ac.be/ASHBBOOK.html Сам я знайшов цю книгу в своїй місцевій бібліотеці, чого і вам бажаю! 6. Д.Е. Батіг "Мистецтво програмування" т.2

PS Ця стаття є деяким підсумком серії випусків розсилки Моделювання Віртуальної Обчислювальної Системи. У цій статті автор висловлює деякі судження, які можуть бути досить спірними, не претендуючи на істину в останній інстанції і глибину своїх знань у цій галузі автор з вдячністю готовий вислухати зауваження і доповнення.

Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Реферат
18.9кб. | скачати


Схожі роботи:
Чехов а. п. - Старий світ і нові господарі життя
Старий Ростов
Старий Заповіт
Ігор Старий
Дослідження ринку пива Старий Юз
СНІД - дуже старий вірус
Про старий і новому календарному стилі
Блок а. а. - Старий і новий світ в поемі а. блоку
Старий Оскол в роки Великої Вітчизняної війни
© Усі права захищені
написати до нас