- •1. Случайные числа и случайные цифры. Таблицы случайных цифр.
- •3. Датчики случайных чисел.
- •4. Сравнение трех способов с практической точки зрения.
- •5. Метод псевдослучайных чисел.
- •6. Стандартный датчик псевдо-сдучайных чисел реализованный на эвм
- •7. Простые алгоритмы. Длина отрезка апериодичности
- •9. Алгоритм д. Неймана
- •10. Алгоритм д. Леммера
- •11. Тесты для проверки случайных цифр
- •12. Проверка псевдослучайных чисел.
- •13. Моделирование дискретных случайных величин.
- •14. Оптимизация метода интервалов
- •15. Моделирование случайных событий.
- •Моделирование случайных непрерывных величин.
- •Моделирование многомерной случайной точки.
- •Поправки к приближенным распределениям.
- •Разделение области моделирования случайной величины.
- •Общая характеристика методов.
- •Метод Неймана.
- •Модифицированный метод Неймана.
- •Метод Метрополиса
- •Моделирование усеченных распределений.
- •Выбор равномерно распределенных точек в сложных пространственных областях.
- •Простейший метод вычислений.
- •Геометрический метод.
- •Сравнение точности методов Монте Карло.
- •Сравнение трудоемкости различных алгоритмов Монте Карло.
- •31. Моделирование процесса переноса иМетод имитации для решения задач о прохождении излучения через слой.
4. Сравнение трех способов с практической точки зрения.
При решении на ЭВМ большинства задач на получение псевдослучайных чисел затрачивается гораздо меньше времени, чем на расчет самих задач. В самом деле, практика показывает, что в настоящее время количество псевдослучайных чисел, используемых при решении отдельных задач, как правило, имеет порядок 104—105 и редко достигает 106—107. Если на выработку каждого числа затрачивать 5 операций, то на получение всех чисел уйдет не более 5·107 операций. На современных ЭВМ, скорость которых равна 5·105 операций в секунду, это составит не более 100 секунд.
Используя датчики, можно организовать «сверхбыструю» выработку случайных чисел, так как, присоединив к ЭВМ k датчиков, мы будем за один такт работы ЭВМ получать k случайных чисел. Однако выигрыш времени при расчете сложной задачи в указанных выше условиях окажется меньше двух минут. Так что, исходя из интересов методов Монте-Карло, не стоит гнаться за «сверхбыстрой» выработкой случайных величин. Разумно требовать, чтобы скорость выработки была того же порядка, что скорость счета ЭВМ. Псевдослучайные числа этому требованию удовлетворяют.
Таблица 1
Метод |
Достоинства |
Недостатки |
таблиц |
Проверка однократная. Воспроизводить числа можно |
Запас чисел ограничен. Занимает много места в накопителе или медленно вводится. Нужна внешняя память |
датчиков |
Запас чисел неограничен. Сверхбыстрое получение. Места в накопителе не занимает |
Проверка периодическая. Воспроизводить числа нельзя. Требуется специальное устройство |
псевдослучайных чисел |
Проверка однократная. Воспроизводить числа можно. Быстрое получение. Места в накопителе занимает мало. Внешние устройства не нужны |
Запас чисел ограничен |
5. Метод псевдослучайных чисел.
С точки зрения математика равномерно распределенная случайная величина — это абстрактное понятие; и только опыт может убедить нас в том, что какая-либо конкретная последовательность чиселобладает интересующими нас свойствами независимых случайных чисел.
Числа , которые вычисляются по какой-либо заданной формуле и могут быть использованы вместо случайных чисел при решении некоторых задач, называютсяпсевдослучайными числами.
Не для каждой задачи подойдет любой генератор псевдослучайных чисел, все зависит от конкретных требований задачи к генератору.
Конкретная последовательность псевдослучайных чисел сходна с таблицей случайных чисел: ее можно один раз тщательно проверить и затем многократно применять; все числа легко воспроизводятся; и запас чисел в такой последовательности практически не ограничен. Однако метод псевдослучайных чисел свободен от главного недостатка таблиц: существуют простые формулы для расчета псевдослучайных чисел, такие, что на получение каждого числа затрачивается всего 3—5 команд ЭВМ, а программа расчета занимает в накопителе лишь несколько ячеек.
Подавляющее большинство расчетов методами Монте-Карло выполнено с помощью псевдослучайных чисел.
6. Стандартный датчик псевдо-сдучайных чисел реализованный на эвм
В качестве примера нелинейного алгоритма, использующего некоторые особенности системы команд ЭВМ, рассмотрим алгоритм, предложенный автором книги для ЭВМ «Стрела». В этом алгоритме число получается из числа тремя командами:
1) число умножается на большую константу g;
2) изображение произведения g в ячейке ЭВМ сдвигается на 7 разрядов влево;
3) вычисляется абсолютная величина полученного числа, которая и есть (при вычислении абсолютной величины число нормализуется).
Удовлетворительная последовательность псевдослучайных чисел получается, например, при g= и (L = 87835, Р= 53 535); результаты статистической проверки этих чисел приведены в [75].
Чтобы пояснить этот алгоритм, необходимо указать, что в ЭВМ «Стрела» числа представляются в нормализованной двоичной форме х=sgnx, где р =1+Ц(|х| )— порядок числа, а m — мантисса (0,5<m<1). Ячейка ЭВМ, в которую записывается число x,
Рис. 6.
состоит из 43 двоичных разрядов (рис. 6). В j-ом разряде записана величина , которая может равняться нулю или единице, и
sgnx=(-1), sgnp=(-1)
(в двоичной записи
m=0, |p|=).
Если произведению g соответствует ячейка [0, ], то после операции сдвига получаем []. Абсолютная величина этого числа в двоичной записи равна
Нетрудно проверить, что в случае, когда размещение мантиссы m и порядка р в ячейке ЭВМ другое, то же число можно у получить из g с помощью двух или трех сдвигов и поразрядного сложения результатов этих сдвигов.