Детерминированная случайность

Не правда ли, нелепое сочетание слов подзаголовка, как деревянная железка! Но тем не менее такая случайность существует.

И появилась она из сугубо практической необходимости — создания надежного датчика случайных чисел. Такие числа очень нужны при эксплуатации современных ЭВМ, решающих задачи моделирования (их мы рассмотрим подробно в третьей главе). Причем качество моделирования зависит от качества случайных чисел. Они должны быть «хорошими».

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

Всем хороши физические датчики, но каждый из них обладает каким-то досадным недостатком из-за их «физичности». Например, электронный шум не может быть надежным источником случайности, так как его свойства изменяются (вспомним, как влияет температура на уровень электронного шума). Радиоактивный распад не подвержен действию среды, но изменяется со временем (вспомним понятие: период полураспада) и требует специальной защиты персонала от радиации.

И, наконец, все физические источники случайности не обладают очень важным для ЭВМ свойством повторимости. Очень часто при работе ЭВМ надо повторить какой-то кусок вычислений (например, для проверки, не была ли сделана ошибка). Если при этом использовался физический датчик случайных чисел, ни о каком повторении речи быть не может!

Все это заставило искать новые способы генерации случайных чисел в ЭВМ. И такие способы были найдены.

Основная идея заключалась в том, чтобы составить программу датчика таких случайных чисел, которые не зависели бы от среды и времени и были бы воспроизводимы любое число раз. Ведь ЭВМ — это программируемый автомат, и, как говорят, сам бог велел воспользоваться этой ее особенностью. И такие программы были составлены. В их основу были положены соответствующие алгоритмы. Рассмотрим один из них — простейший.

Его идея состоит в последовательном преобразовании полученного на предыдущем шаге числа в другое и т. д. (Такой процесс называется рекуррентным.) Для этого достаточно умножить полученное ранее число на заданное большое и взять дробную часть от результата. Пусть заданное число равно а = 15,783 (по сравнению с единицей это большое число), а исходное x0 = 0,5, тогда первое случайное число (x1) равно дробной части произведения ах0 = 7,8915, то есть x1 = 0,891.5. Второе число получаем как дробную часть произведения ах1 = 15,7830,8915 = 14,07054, то есть x2 = 0,07054 (сохраняем 5 знаков после запятой). Далее x3 равна дробной части ax2, эта дробная часть равна 0,11333 и т. д.

Легко написать общую формулу для вычисления чисел (ее и называют «датчиком»):

x1 = ]ax1[ ,

где вывернутые прямые скобки обозначают процедуру выделения дробной части числа, попавшего в эти скобки. Применяя эту формулу, можно получить последовательность чисел x0, x1, x2 ... xn.

В таблице приведены первые двадцать значений этих чисел для a=15,783, которые может получить каждый с помощью карманного калькулятора:

i        0       1       2       3       4       5       6       7       8       9

X1 50     89     07     11     78     46     35     66     46     26

 

10     11     12     13     14     15     16     17     18     19     20

14     23     74     71     33     31     02     40     33     25     94

(здесь приведены лишь две цифры после запятой, но расчет велся с точностью до десяти знаков). Если показать эту таблицу любому специалисту по выявлению закономерностей (но не говорить, откуда она появилась), он в ней не найдет ни малейшего отклонения от равномерных случайных чисел. Самая строгая проверка этой короткой последовательности подтвердит лишь одну версию — о ее случайном характере.

Но ведь эта последовательность однозначно определяется формулой «датчиком» и двумя числами a и x0. Это строго детерминированная последовательность вычисляется на сколь угодно много шагов вперед. Считать ее случайной (в смысле: непредсказуемой) никак нельзя. В чем здесь дело?

Такие последовательности называют псевдослучайными. Они, не будучи случайными, ведут себя как случайные, то есть все характеристики псевдослучайных последовательностей почти совпадают с характеристиками случайных.

Здесь сказано осторожное «почти». Что это значит?

А то, что числа в этой последовательности обладают двумя недостатками, которые не позволяют полученную последовательность считать чисто случайной, — она чуть «подпорчена», что можно выяснить, лишь обработав большой ее кусок (если, разумеется, не знать формулы «датчика», порождающей эту последовательность).

Это «чуть» состоит в следующем. Во-первых, не все числа последовательности независимы от предыдущих.

В этом легко убедиться, если представить, что на каком-то N-м шаге получено очень малое число xn. Тогда следующее число xn+1 будет наверняка тоже мало и равно axn , то есть в а раз больше. Это явная зависимость двух соседних значений нашей последовательности.

Но этот недостаток не так важен, поскольку проявляется лишь при очень малых хn, что бывает достаточно редко. Другой недостаток значительно серьезней. Он состоит в том, что наша последовательность с некоторого момента начинает повторять один свой кусок — его называют циклом. Причина этому очевидна.

Действительно, наша последовательность чисел устроена так, что каждое последующее число вычисляется из предыдущего. И если на каком-то N-м. шаге будет получено, например, исходное число x0, то дальше в соответствии с формулой «датчиком» будут получены x1, x2 и т. д. ...до опять-таки x0, после чего этот цикл повторится снова, затем снова и опять снова... Очевидно, что то же самое произойдет, если в процессе вычислений на N-м шаге встретится любое из предыдущих чисел (например, q). Тогда цикл начнется с этого q-го — числа (xq). Легко видеть, что величина цикла равна N - q. Это проиллюстрировано на рисунке на стр. 24, где представлена ось номеров i последовательности. Цикл величиной N - q чисел повторяется после N-го числа с «железной» неизбежностью.

Величину N называют числом апериодичности. Она характеризует «добротную» часть последовательности до повторения ее чисел. Все числа до iV в этой последовательности разные. Очевидно, что датчик случайных чисел можно считать хорошим только тогда, если величины N и периоды N-q достаточно велики.

Эти величины прежде всего зависят от разрядности ЭВМ, на которой ведутся вычисления. Чем больше число разрядов, тем больше величины N и N-q.

Создатели датчиков случайных чисел, конечно же, стараются сделать их так, чтобы числа эти были бы как можно больше. И часто в погоне за большим циклом забывают о другой важной характеристике датчика — зависимости между случайными числами (точнее, независимости). Иногда это обнаруживается слишком поздно...

Лет десять назад три дотошных математика исследовали свойства датчика случайных чисел для одной из самых распространенных серий машин, называемой «Системой-360», американской фирмы IBM (читается: Ай-бн- эм). Эта фирма считается крупнейшей в мире по разработке, производству и эксплуатации вычислительных машин. Этот датчик назывался RANDU (Rand по-английски — случай) и входил в пакет программ для научных расчетов, прилагаемых к «Системе-360». Разработчики датчика RANDU добились периода 231, то есть более миллиарда — это очень много. Но... при этом упустили, что датчик выдавал очень зависимые случайные числа, что и выявили математики, которые закончили свое исследование ’грустными словами:  «Поскольку RANDU почти несомненно применялся пользователями «Системы-360», то мы серьезно сомневаемся в результатах большого числа моделирования. И мы настоятельно призываем вас не использовать RANDU!»

Эти отчаянные призывы, увы, прозвучали с большим опозданием, так как датчик использовался во всем мире уже с 1960 года, и за это время огромное число расчетов и следующих за ними решений были приняты на основе никуда не годного датчика случайных чисел. Трудно оценить ущерб, нанесенный этой ошибкой (зависимые случайные числа считались независимыми), так как неудачные решения наверняка «списывались» на другие возможные причины (сбой ЭВМ, неправильная постановка задачи и т. д.). Но почти наверняка стоимость этой ошибки превысила стоимость той печально знаменитой ошибки в программе вывода на орбиту космической ракеты, «благодаря» которой ракета сбилась с курса и ее пришлось взорвать. Стоила эта ошибка столько же, сколько стоит экспериментальная космическая ракета, — несколько миллиардов долларов.

Читатель может возразить, что, мол, нельзя сравнивать конкретные миллиарды от потери экспериментальной ракеты с сомнительными потерями от плохого датчика случайных чисел. Действительно, в последнем случае потери учесть трудно, но можно. И дело здесь в том, что программу RANDU использовали наверняка много миллионов раз и столько же раз она давала небольшую, но реальную ошибку, которая и наносила ущерб, помноженный на миллионы обращений к этому самому RANDU. Это и есть плата за незнание свойств случайности!

  • Скажите, у Вас есть баня? Дело в том, что имея свой дом, человек, как правило, стремится к большему. Например, многие хотят построить ещё и баню (мини-сауну), однако, средств на такое строительство хватает не у всех. Но даже из этой, казалось бы, безвыходной ситуации, есть простой выход – надо найти место, где строят НЕДОРОГО! Если Вас интересует строительство бань под ключ, и всё это – недорого, вот http://www.house4you.su, кликайте по ней и узнавайте все подробности недорогого строительства!