Старый взгляд на новые вещи

Эта статья не даёт ответов - она лишь ставит вопросы. Здесь вы не найдёте инструкций для выполнения - лишь указано направление. Нет уверенности, что вам вообще нужно её читать.

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

Оглянитесь вокруг и вы поймёте, что миром правят случайности - они везде и всюду: от шума в радиоприёмнике, до игры в орлянку и карт Таро, от русской рулетки и до ... генерирования паролей. И ведь не известно, что более опасно.

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

Как же вообще получают эти замечательные числа? Существуют следующие способы получения случайных чисел: 1. Аппаратный способ. Можно использовать специальные приставки - генераторы(датчики) случайных чисел. Этот способ не требует дополнительных вычислительных операций ЭВМ по выработке случайных чисел, а необходима только операция обращения ко внешнему устройству(датчику). В качестве физических эффектов лежащих в основе таких генераторов могут быть использованы шумы в электронных и полупроводниковых приборах(обусловлены следующим: тепловыми флуктуациями, случайными вариациями числа частиц в электронных потоках, хаотическим перемагничиванием доменов в ферромагнитных сердечниках), явление распада радиоактивных элементов. 2. Табличный способ. Случайные числа, оформленные в виде таблицы, помещаются во внешнюю или оперативную память ЭВМ. Запас чисел ограничен. Эффективно использовать только для сравнительно небольших таблиц, т.к. массив занимает некоторый объём оперативной памяти! 3. Алгоритмический способ. Формирование случайных (вернее - псевдослучайных) чисел с помощью специальных алгоритмов. На генерацию псевдослучайных чисел затрачивается машинное время.

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

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

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

На основании такого генератора работает уже упоминавшаяся двуликая функция rand().

Пожалуй пора взглянуть на эти интересные числа. Давайте рассмотрим следующую последовательность чисел:

Как по-вашему является ли она случайной? Кто-то может дать положительный ответ. Кто-то, возможно чувствуя подвох, ответит отрицательно. По-настоящему мудро поступит тот, кто не станет отвечать, усомнившись в корректности вопроса. Дело в том (только не слишком удивляйтесь), что эта последовательность относится к числу ПИ(PI), то есть, точнее говоря, это последователность чисел с 81-го по 720-й знак после запятой числа ПИ. Так можно ли назвать эти числа случайными? Ниже даётся ответ на этот вопрос:

(Ashby W. R. An introduction to CYBERNETICS) Для тех, кто не очень силён в английском, или у кого переводчика нет :) дам небольшое пояснение: " последовательность десятичных знаков числа ПИ являются определёнными(детерминированными), но блок из тысячи знаков мог бы служить, как случайные числа, весьма хорошо, для сельскохозяйственных экспериментов, не потому, что они случайны, а потому, что они вероятно не коррелированы со специфическими особенностями земельных участков. ..."

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

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

На основе этих замечательных устройств можно легко написать простенькую функцию генерирования случайных чисел:

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

Если уподобиться разного типа богоискателям можно сказать, что случайности(в нашем случае - ГСЧ) -это один из языков Cтарика. Другие же применения ГСЧ чрезвычайно интересны - от когнитивной эволючии и моделирования AI (читайте о Creativity Machine на membrana.ru) , до анализа безопасности ( вызывает умиление применение ГСЧ в статье "Случайные числа упрощают алгоритм").

Но как всегда человек с надеждой смотрит в будущее ,даже если оно определяется каким-то ГСЧ.

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

P.S. Эта статья является некоторым итогом серии выпусков рассылки Моделирование Виртуальной Вычислительной Системы. В этой статье автор выражает некоторые суждения, которые могут быть весьма спорными, не претендуя на истину в последней инстанции и глубину своих познаний в данной области автор с благодарностью готов выслушать замечания и дополнения.