\input style
\chapno=3\subchno=3\chapnotrue
S6--S9), РАВНО ЛИШЬ~$\floor{{1\over 2}\prod (2c_j+1)}$,  А
НЕ~$\prod(2c_j+1)$, ТАК КАК АЛГОРИТМ ИМЕЕТ ДЕЛО ТОЛЬКО С ТАКИМИ ВЕКТОРАМИ,
У КОТОРЫХ ПЕРВЫЙ НЕНУЛЕВОЙ ЭЛЕМЕНТ ПОЛОЖИТЕЛЕН.)

ЁАССМОТРИМ КРАТКО ПРИМЕР АЛГОРИТМА~$S$ В ДЕЙСТВИИ, КОГДА $a=3141592621$,
$m=10^{10}$, $n=3$. т ТАБЛ.~2 В ПЕРВЫХ СТРОКАХ ПРЕДСТАВЛЕНЫ~$Q$ И~$R$,
ПРИГОТОВЛЕННЫЕ НА ШАГЕ~S1. шССЛЕДОВАНИЕ ЭТИХ МАТРИЦ СРЕДСТВАМИ ЛЕММЫ~A
ПОТРЕБУЕТ ПРОВЕРКИ $10^{29}$~СЛУЧАЕВ, ЧТО ВЫХОДИТ ЗА ВСЯКИЕ ГРАНИЦЫ.
яОСЛЕ ШЕСТИ ИТЕРАЦИЙ НА ШАГАХ~S2--S5 ЭЛЕМЕНТЫ МАТРИЦ~$Q$ И~$R$ СТАЛИ
НАМНОГО МЕНЬШЕ (СМ.~СТРОКУ~7 ТАБЛ.~2), И, СОГЛАСНО ЛЕММЕ~A, ТЕПЕРЬ В
ЭТОЙ НОВОЙ ЗАДАЧЕ~$\abs{x_1}\le 3$, $\abs{x_2}\le 3$, $\abs{x_3}\le 14$.
фАЛЬНЕЙШЕЕ УМЕНЬШЕНИЕ С ПОМОЩЬЮ ЛЕММЫ~B ПРИВОДИТ НАС К СТРОКЕ~8: В
МАТРИЦЕ~$Q$ (СТРОКА~7) ПРИБАВЛЯЕМ СТОЛБЕЦ~3 К СТОЛБЦУ~2, СТРОКУ~3 К
СТРОКЕ~2, ЗАТЕМ 3~РАЗА ВЫЧИТАЕМ СТОЛБЕЦ~3 ИЗ СТОЛБЦА~1 И ТАКЖЕ ТРИ РАЗА
СТРОКУ~3 ИЗ СТРОКИ~1. т МАТРИЦЕ~$R$ ВЫЧИТАЕМ СТОЛБЕЦ~2 ИЗ СТОЛБЦА~3, ЗАТЕМ
ВЫЧИТАЕМ СТРОКУ~2 ИЗ СТРОКИ~3, ПОТОМ ПРИБАВЛЯЕМ ТРИ РАЗА СТОЛБЕЦ~1 К
СТОЛБЦУ~3, А СТРОКУ~1 СНОВА ТРИ
{\def\cell#1{\vcenter{\halign{\hfil$\mathstrut##$\cr#1}}}
 \def\ncell#1{\cell{#1}\qquad}
 \def\lpar{\Bigg(}%\left(\vphantom{\cell{\cr\cr}}
 \def\rpar{\Bigg)\hfill}%\left(\vphantom{\cell{\cr\cr}}
\htable{ЄАБЛИЦА 2}
{яРИМЕР АЛГОРИТМА S}
{$#$\bskip&$\displaystyle#$\bskip&&\hfil$\displaystyle#$\bskip\cr
\noalign{
\hrule
\embedpar{ёТРОКА \hfil ьАТРИЦА~$Q$ \hfil}
\hrule
}
  1.
 &
  \lpar
 &
  \cell{
   1\,00000\,00000\,00000\,00000\cr
   -31415\,92621\,00000\,00000\cr
   36783\,50359\,00000\,00000\cr
  }
 &
  \cell{
   -31415\,92621\,00000\,00000\cr
   9869\,60419\,63216\,49642\cr
   -11555\,87834\,52871\,00939\cr
   }
 &
  \cell{
   36783\,50359\,00000\,00000\cr
   -11555\,87834\,52871\,00939\cr
   13530\,26136\,35554\,28882\cr
  }
 &
  \rpar
 \cr
 \noalign{\smallskip}
  \vdots
 &
  \multispan{4}\hfill$\vdots$\hfill
 \cr
 \noalign{\smallskip}
  7.
 &
  \lpar
 &
  \ncell{
   1160\,62418\cr
   -110\,45623\cr
   324\,06810\cr
  }
 &
 \ncell{
   -110\,45623\cr
   189\,42062\cr
   -70\,72864\cr
  }
 &
  \ncell{
    324\,06810\cr
    -70\,72864\cr
    99\,86024\cr
  }
 &
  \rpar
 \cr
 \noalign{\smallskip}
  8.
 &
  \lpar
 &
  \ncell{
   114\,95774\cr
   126\,21707\cr
   24\,48738\cr
  }
 &
  \ncell{
   126\,21707\cr
   147\,82358\cr
   29\,13160\cr
  }
 &
  \ncell{
   24\,48738\cr
   29\,13160\cr
   99\,86024\cr
  }
 &
  \rpar
 \cr
\noalign{
\hrule
\vskip 5mm
\hrule
\embedpar{ёТРОКА \hfil ьАТРИЦА~$R$ \hfil}
\hrule
}
  1.
 &
  \lpar
 &
  \cell{
    23399\,86555\,98770\,78523\cr
    31415\,92621\,00000\,00000\cr
    -36783\,50359\,00000\,00000\cr
  }
 &
  \cell{
    31415\,92621\,00000\,00000\cr
    1\,00000\,00000\,00000\,00000\cr
    0\cr
   }
 &
  \cell{
   -36783\,50359\,00000\,00000\cr
   0\cr
   1\,00000\,00000\,00000\,00000\cr
  }
 &
  \rpar
 \cr
 \noalign{\smallskip}
  \vdots
 &
  \multispan{4}\hfill$\vdots$\hfill
 \cr
 \noalign{\smallskip}
  7.
 &
  \lpar
 &
  \ncell{
   13913\,04805\,78992\cr
   -11890\,71034\,30888\cr
   -53572\,76149\,67948\cr
  }
 &
  \ncell{
   -11890\,71034\,30888\cr
   10880\,07572\,69932\cr
   46294\,02921\,32522\cr
  }
 &
  \ncell{
   -53572\,76149\,67948\cr
   46294\,02921\,32522\cr
   2\,07645\,57301\,67787\cr
  }
 &
  \rpar
 \cr
 \noalign{\smallskip}
  8.
 &
  \lpar
 &
  \ncell{
    13913\,04805\,78992\cr
    -11890\,71034\,30888\cr
    57\,09301\,99916\cr
  }
 &
  \ncell{
    -11890\,71034\,30888\cr
    10880\,07572\,69932\cr
    -258\,17754\,30074\cr
  }
 &
  \ncell{
    57\,09301\,99916\cr
    -258\,17754\,30074\cr
    1062\,71591\,61243\cr
  }
 &
  \rpar
 \cr
}}%
%% 122
РАЗА ПРИБАВЛЯЕМ К СТРОКЕ~3. ¤ТО УМЕНЬШАЕТ~$Q$ И~$R$, ТАК ЧТО, СОГЛАСНО
ЛЕММЕ~A, ТЕПЕРЬ ОСТАЛОСЬ ПРОВЕРИТЬ ЗНАЧЕНИЕ~$\abs{x_1}\le 3$,
$\abs{x_2}\le 3$, $\abs{x_3}\le 1$, ЧТОБЫ НАЙТИ АБСОЛЮТНЫЙ МИНИМУМ. т
ДЕЙСТВИЕ ПРИВОДИТСЯ МЕТОД ПЕРЕБОРА НА ШАГАХ~S6--S9, КОТОРЫЙ НАХОДИТ
КОМБИНАЦИЮ~$x_1=1$, $x_2=-1$, $x_3=0$, РЕАЛИЗУЮЩУЮ МИНИМАЛЬНОЕ
ЗНАЧЕНИЕ~$x^TQx=1034718$. ¤ТИ ВЫЧИСЛЕНИЯ МОЖНО БЫЛО БЫ СДЕЛАТЬ С ПОМОЩЬЮ
НАСТОЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ МАШИНКИ ЗА НЕСКОЛЬКО ЧАСОВ, ХОТЯ В НАЧАЛЕ ЗАДАЧА
ВЫГЛЯДЕЛА ВЕСЬМА ВНУШИТЕЛЬНО.

ёПЕКТРАЛЬНЫЙ ТЕСТ ВПЕРВЫЕ ПОЯВИЛСЯ В СТАТЬЕ Ё.~ъОВЭЮ И Ё.~ьАКФЕРСОНА
(R.~R.~Coveyou, R.~D.~MacPherson, Fourier Analysis of Uniform Random
Number Generators, {\sl JACM,\/} {\bf 14} (1967), 100--119). т ЭТОЙ СТАТЬЕ
ОПИСАН АЛГОРИТМ, В СУЩНОСТИ ПОДОБНЫЙ АЛГОРИТМУ~$S$, ЗА ИСКЛЮЧЕНИЕМ
НЕСКОЛЬКО ОТЛИЧНОГО ПРАВИЛА ПРЕОБРАЗОВАНИЯ НА ШАГЕ~S4.

\excercises
\ex[ь20] тЫВЕДИТЕ СООТНОШЕНИЕ~(2) ИЗ~(1).

\ex[ь20] яРЕДПОЛАГАЯ, ЧТО~$0\le s_1$~\dots, $s_n<m$, ВЫВЕДИТЕ
СООТНОШЕНИЕ~(1) ИЗ~(2).

\ex[ь22] (a)~яУСТЬ $F(t)$~ОПРЕДЕЛЕНА ДЛЯ ЦЕЛЫХ ЗНАЧЕНИЙ~$t$, $0\le t < m$,
 И ОБЛАСТЬ ЕЕ ОПРЕДЕЛЕНИЯ РАСШИРЕНА НА ВСЕ ЦЕЛЫЕ ЧИСЛА С ПОМОЩЬЮ
ФОРМУЛЫ~$F(t)=F(t\bmod m)$. яУСТЬ~$f(s)$---ПРЕОБРАЗОВАНИЕ ЇУРЬЕ
ФУНКЦИИ~$F(t)$, ОПРЕДЕЛЕННОЕ В СООТВЕТСТВИИ С~(1) ДЛЯ~$n=1$. эАЙДИТЕ
ПРЕОБРАЗОВАНИЕ ЇУРЬЕ ФУНКЦИИ~$F(t+1)$, ВЫРАЗИВ ЕГО ЧЕРЕЗ~$f(s)$.

(b)~эАЙДИТЕ ПРЕОБРАЗОВАНИЕ ЇУРЬЕ СУММЫ~$\sum_{0\le k < m} F(k)G(t-k)$,
ВЫРАЗИВ ЕГО ЧЕРЕЗ ПРЕОБРАЗОВАНИЯ ЇУРЬЕ~$F$ И~$G$.

\rex[ь22] яУСТЬ~$X_0$, $X_1$, $X_2$,~\dots---ПЕРИОДИЧЕСКАЯ
ПОСЛЕДОВАТЕЛЬНОСТЬ ЦЕЛЫХ ЧИСЕЛ С ПЕРИОДОМ~$m$, ТАКАЯ, ЧТО~$0\le X_k<m$, И
ПУСТЬ~$f(s_1, s_2)$---ФУНКЦИЯ, ОПРЕДЕЛЕННАЯ ФОРМУЛОЙ~(4). тЫРАЗИТЕ
ЧЕРЕЗ~$f$ ВЕРОЯТНОСТЬ ТОГО, ЧТО~$X_{k+1}<X_k$ В ЭТОЙ ПОСЛЕДОВАТЕЛЬНОСТИ.
(єПРОСТИТЕ НАСКОЛЬКО ВОЗМОЖНО ВАШ ОТВЕТ, ЧТОБЫ ЯВНО БЫЛИ ПРЕДСТАВЛЕНЫ
КОЭФФИЦИЕНТЫ ПРИ КАЖДОМ ЧАСТНОМ ЗНАЧЕНИИ~$f$.)

\ex[ь23] яУСТЬ~$X_0$, $X_1$, $X_2$,~\dots---ПЕРИОДИЧЕСКАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ
ЦЕЛЫХ ЧИСЕЛ С ДЛИНОЙ ПЕРИОДА~$m$ И ТАКАЯ, ЧТО~$0\le X_k<m$. тЫРАЗИТЕ ЧЕРЕЗ
ФУНКЦИЮ~$F$, ОПРЕДЕЛЯЕМУЮ СООТНОШЕНИЕМ~(3), И ФУНКЦИЮ~$f$, ОПРЕДЕЛЯЕМУЮ
СООТНОШЕНИЕМ~(4), СУММУ~$\sum_{0\le k <m} X_k X_{k+1}$, ПРЕДСТАВЛЯЮЩУЮ
ВАЖНУЮ ЧАСТЬ ФОРМУЛЫ ДЛЯ КОЭФФИЦИЕНТА ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ (ФОРМУЛА~(3.3.2-23)).

\rex[ь28] фОКАЖИТЕ ТЕОРЕМУ~3.3.3P, ИСПОЛЬЗУЯ~(8) И РЕЗУЛЬТАТ УПР.~4.

\ex[ь40] тЫВЕДИТЕ ФОРМУЛЫ, ПОЗВОЛЯЮЩИЕ ДОСТАТОЧНО ЭФФЕКТИВНО ВЫЧИСЛЯТЬ
ТОЧНОЕ ЗНАЧЕНИЕ ВЕРОЯТНОСТИ ТОГО, ЧТО~$X_{k+2}<X_{k+1}<X_k$ ДЛЯ
ЛИНЕЙНОЙ КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ С МАКСИМАЛЬНЫМ ПЕРИОДОМ.
[\emph{єКАЗАНИЕ.} ё ПОМОЩЬЮ МЕТОДОВ, ИСПОЛЬЗУЕМЫХ В УПР.~6, И РЕЗУЛЬТАТА
УПР.~3.3.3-20 ЭТА ВЕЛИЧИНА МОЖЕТ БЫТЬ ЯВНО ВЫРАЖЕНА ЧЕРЕЗ ОБОБЩЕННЫЕ
СУММЫ фЕДЕКИНДА. чАМЕТЬТЕ, ЧТО ЗАДАЧА СИЛЬНО УСЛОЖНЯЕТСЯ, ЕСЛИ НЕ
ПОЛЬЗОВАТЬСЯ ПРЕОБРАЗОВАНИЕМ ЇУРЬЕ.]

\ex[M22] эАЙДИТЕ ПРИЕМЛЕМО ПРОСТОЕ ВЫРАЖЕНИЕ СУММЫ~$\sum_{0\le k < m} X_k X_{k+1}$
ДЛЯ ЛИНЕЙНОЙ КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ С МАКСИМАЛЬНЫМ
ПЕРИОДОМ, ИСПОЛЬЗУЯ РЕЗУЛЬТАТ УПР.~5, А ТАКЖЕ ФОРМУЛУ~(8).

\ex[ть30] (°.~¤РМИТ.) чАДАНА $n\times n\hbox{-МАТРИЦА}$~$A$. фОКАЖИТЕ, ЧТО
СУЩЕСТВУЕТ НЕНУЛЕВОЙ ЦЕЛОЧИСЛЕННЫЙ ВЕКТОР~$x$, ТАКОЙ, ЧТО~$Ax\cdot Ax \le
\left({4\over 3}\right)^{(n-1)/2} (\det A)^{2/n}$.
%% 123
[\emph{єКАЗАНИЕ.} ёНАЧАЛА ПОКАЗАТЬ, ЧТО ДЛЯ ВСЕХ~$\varepsilon>0$
СУЩЕСТВУЕТ ЦЕЛОЧИСЛЕННАЯ МАТРИЦА~$U$, ДЕТЕРМИНАНТ КОТОРОЙ РАВЕН~$1$, И
ПРОИЗВЕДЕНИЕ~$AUx\cdot AUx$ НАХОДИТСЯ В $\varepsilon\hbox{-ОКРЕСТНОСТИ}$
МАКСИМАЛЬНОЙ НИЖНЕЙ ГРАНИЦЫ ЕЕ ЗНАЧЕНИЙ
ПРИ~$(x_1, x_2,~\ldots, x_n)=(1, 0, 0,~\ldots, 0)$. чАТЕМ ДОКАЗАТЬ ОБЩЕЕ
УТВЕРЖДЕНИЕ ИНДУКЦИЕЙ ПО~$n$, ЗАПИСАВ~$Ax\cdot Ax$ В
ВИДЕ~$\alpha(x_1+\beta_2x_2+\cdots+\beta_n x_n)^2+g(x_2,~\ldots, x_n)$,
ГДЕ $g$~СООТВЕТСТВУЕТ $(n-1)\times(n-1)\hbox{-МАТРИЦЕ}$~$A'$.]

\ex[ть30] (ъОВЭЮ И ьАКФЕРСОН). яУСТЬ~$X_0$, $X_1$, $X_2$,
~\dots---ПОСЛЕДОВАТЕЛЬНОСТЬ ЦЕЛЫХ ЧИСЕЛ, ЛЕЖАЩИХ В ПРЕДЕЛАХ~$0\le X_k <m$;
ЕЙ СООТВЕТСТВУЕТ ПРЕОБРАЗОВАНИЕ ЇУРЬЕ~$f(s_1,~\dots, s_n)$, ОПРЕДЕЛЕННОЕ
ФОРМУЛОЙ~(4). яУСТЬ~$U_k=X_k/m$, a~$V_0$, $V_1$, $V_2$,
~\dots---ПОСЛЕДОВАТЕЛЬНОСТЬ НЕЗАВИСИМЫХ ИСТИННО СЛУЧАЙНЫХ ДЕЙСТВИТЕЛЬНЫХ
ЧИСЕЛ, РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ МЕЖДУ~$0$ И~$1$;
$\lambda$---ЧИСЛО, МЕНЬШЕЕ~$1$, И~$W_k=(U_k+\lambda V_k) \bmod 1$.
(ЄЕПЕРЬ~$W_k$---ЭТО СЛУЧАЙНЫМ ОБРАЗОМ "РАЗМАЗАННЫЕ" В ПРЕДЕЛАХ~$\lambda$
ЧЛЕНЫ ПОСЛЕДОВАТЕЛЬНОСТИ~$U_k$.) юПРЕДЕЛИМ КОЭФФИЦИЕНТЫ ЇУРЬЕ ЛЮБОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ МЕЖДУ~$0$ И~$1$ КАК
$$
\lim_{N\to\infty}{1\over N}\sum_{0\le k < N}\exp(2\pi i (s_1
U_k+\cdots+s_n U_{k+n-1})).
$$
тЫРАЗИТЕ КОЭФФИЦИЕНТЫ ЇУРЬЕ ПОСЛЕДОВАТЕЛЬНОСТИ~$\<W_k>$ ЧЕРЕЗ
КОЭФФИЦИЕНТЫ ЇУРЬЕ ПОСЛЕДОВАТЕЛЬНОСТИ~$\<X_k>$.

\ex[ь10] єРАВНЕНИЕ~(8) ПОКАЗЫВАЕТ, ЧТО ЗНАЧЕНИЕ~$c$ В ЛИНЕЙНОЙ
КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ С МАКСИМАЛЬНЫМ ПЕРИОДОМ НЕ ВЛИЯЕТ НА
КОЭФФИЦИЕНТЫ ЇУРЬЕ, А ИЗМЕНЯЕТ ЛИШЬ "АРГУМЕНТ" КОМПЛЕКСНОГО ЧИСЛА~$f(s_1,
~\dots, s_n)$. фРУГИМИ СЛОВАМИ, АБСОЛЮТНОЕ ЗНАЧЕНИЕ~$f(s_1,~\ldots, s_n)$
НЕ ЗАВИСИТ ОТ~$c$. эО МОЖНО ЛИ ВЫБРАТЬ~$c$ ТАК, ЧТОБЫ НЕСЛУЧАЙНЫЙ ЭФФЕКТ
ОДНОЙ ВОЛНЫ~$f(s_1,~\dots, s_n)$ УНИЧТОЖАЛСЯ БЫ "ПРОТИВОПОЛОЖНЫМ" ЭФФЕКТОМ
ДРУГОЙ ВОЛНЫ~$f(s'_1,~\ldots, s'_n)$?

\ex[ть23] фОКАЖИТЕ, НЕ ИСПОЛЬЗУЯ ГЕОМЕТРИЧЕСКИХ АРГУМЕНТОВ, ЧТО ЛЮБОЕ
РЕШЕНИЕ "ПРОБЛЕМЫ~(b)", СФОРМУЛИРОВАННОЙ В ПОДПУНКТЕ~C ТЕКСТА, ДОЛЖНО БЫТЬ
ОДНОВРЕМЕННО РЕШЕНИЕМ СИСТЕМЫ УРАВНЕНИЙ~(28).

\ex[ть30] т ТЕКСТЕ ОСТАЛСЯ В ТЕНИ ДОВОЛЬНО ВАЖНЫЙ ВОПРОС: БЫЛО СДЕЛАНО
МОЛЧАЛИВОЕ ПРЕДПОЛОЖЕНИЕ, ЧТО, ЕСЛИ~$A$---ПРОИЗВОЛЬНАЯ НЕВЫРОЖДЕННАЯ МАТРИЦА
ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ, ФУНКЦИЯ~(18) \emph{ИМЕЕТ} МИНИМУМ, КОТОРЫЙ
\emph{ДОСТИГАЕТСЯ} НА НЕКОТОРОМ ЦЕЛОЧИСЛЕННОМ ВЕКТОРЕ~$x$.
\medskip
\item{(a)} фОКАЖИТЕ, ЧТО НАИБОЛЬШАЯ НИЖНЯЯ ГРАНИЦА ВЕЛИЧИНЫ~(18),
ВЗЯТАЯ ПО ВСЕМ НЕНУЛЕВЫМ ЦЕЛОЧИСЛЕННЫМ ВЕКТОРАМ~$x$, ДОСТИГАЕТСЯ ПРИ
НЕКОТОРОМ~$x$, ЕСЛИ~$A$---НЕВЫРОЖДЕННАЯ МАТРИЦА.

\item{(b)}~яОКАЖИТЕ, ЧТО, ЕСЛИ~$A$---ВЫРОЖДЕННАЯ МАТРИЦА, ТАКОГО
НЕНУЛЕВОГО ЦЕЛОЧИСЛЕННОГО ВЕКТОРА, НА КОТОРОМ ДОСТИГАЕТСЯ НАИБОЛЬШАЯ
НИЖНЯЯ ГРАНИЦА~(18), МОЖЕТ НЕ СУЩЕСТВОВАТЬ.

\rex[24] тЫПОЛНИТЕ ВРУЧНУЮ АЛГОРИТМ~S ДЛЯ~$m=100$, $a=41$, $n=3$.
чАМЕНИТЕ КОНСТАНТУ~"$1000$" НА ШАГЕ~S3 ЧИСЛОМ~"$3$".

\ex[ь18] ўТО ПРОИЗОЙДЕТ, ЕСЛИ ОПЕРАЦИЮ "$k\asg n$" В КОНЦЕ
ШАГА~S1 ЗАМЕНИТЬ НА~"$\asg 1$"?

\ex[ь25] эЕ ИСКЛЮЧЕНО (ХОТЯ ЭТОГО ЕЩЕ НЕ НАБЛЮДАЛОСЬ), ЧТО
АЛГОРИТМ~S МОЖЕТ ЗАЦИКЛИТЬСЯ, ПОВТОРЯЯ БЕСКОНЕЧНОЕ ЧИСЛО РАЗ ШАГИ~S2--S5.
яОКАЖИТЕ, ЧТО ЭТО МОЖЕТ ПРОИЗОЙТИ ТОГДА И ТОЛЬКО ТОГДА, КОГДА ПРИ
ПОСЛЕДОВАТЕЛЬНОМ ВЫПОЛНЕНИИ $n$~РАЗ ШАГА~S4 НЕ ПРОИСХОДИТ ПРЕОБРАЗОВАНИЙ
(Т.~Е.\ НЕТ ОПЕРАЦИЙ~|TRANS|).

\rex[ь28] ьОДИФИЦИРУЙТЕ АЛГОРИТМ~S ТАК, ЧТОБЫ КРОМЕ ВЫЧИСЛЕНИЯ~$q$ В НЕМ
ОПРЕДЕЛЯЛСЯ БЫ НАБОР ЦЕЛЫХ ЧИСЕЛ~$s_1$,~\dots, $s_n$,
УДОВЛЕТВОРЯЮЩИХ~(11) ПРИ~$s_1^2+\cdots+s_n^2=q$. [\emph{єКАЗАНИЕ.}
рЛГОРИТМ~S СОХРАНЯЕТ ТОЛЬКО ЗНАЧЕНИЯ~$Q$ И~$R$ ИЗ~(19), НО НЕ~$A$ И~$B$.
хСЛИ СОХРАНИТЬ ЗНАЧЕНИЯ~$A$ И/ИЛИ~$B$ ПРИ ВЫПОЛНЕНИИ АЛГОРИТМА,
ПО-ВИДИМОМУ, НЕ СЛИШКОМ ТРУДНО БУДЕТ ПОЛУЧИТЬ ЗНАЧЕНИЯ~$s_1$,~\dots, $s_n$.]

\ex[ь25] эАЙДИТЕ $3\times 3\hbox{-МАТРИЦУ}$~$A$, ТАКУЮ, ЧТО ЕСЛИ~$Q=A^TA$
И~$R=Q^{-1}$, ТО ШАГИ~S2--S5 АЛГОРИТМА~S НИКОГДА НЕ ЗАКОНЧАТСЯ ПЕРЕХОДОМ К
ШАГУ~S6
%% 124
(ТАК ЧТО ВЫЧИСЛЕНИЯ НИКОГДА НЕ ПРЕКРАТЯТСЯ). [\emph{єКАЗАНИЕ.} ЁАССМОТРЕТЬ
"КОМБИНАТОРНЫЕ МАТРИЦЫ", Т.~Е.\ МАТРИЦЫ, ЭЛЕМЕНТЫ КОТОРЫХ ИМЕЮТ
ВИД~$a+b\delta_{ij}$; СР.~С~УПР.~1.2.3-39.]

\ex[ь20] яОКАЖИТЕ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ ЇИБОНАЧЧИ${}\bmod m$
СЛУЖИТ ПЛОХИМ ИСТОЧНИКОМ СЛУЧАЙНЫХ ЧИСЕЛ, УБЕДИВШИСЬ, ЧТО СООТВЕТСТВУЮЩАЯ
ФУНКЦИЯ~$f(s_1, s_2, s_3)$, ОПРЕДЕЛЕННАЯ В~(4), ИМЕЕТ БОЛЬШИЕ
НИЗКОЧАСТОТНЫЕ КОМПОНЕНТЫ.

\rex[ь24] тЫЧИСЛИТЕ КОЭФФИЦИЕНТЫ ЇУРЬЕ~$f(s_1,~\dots, s_n)$ ДЛЯ
ЛИНЕЙНОЙ КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ, ОПРЕДЕЛЕННОЙ ВЕЛИЧИНАМИ~$X_0=1$,
$c=0$, $m=2^e\ge 8$ И~$a \bmod 8=5$. юБСУДИТЕ, КАК ОБОБЩИТЬ СПЕКТРАЛЬНЫЙ
ТЕСТ ДЛЯ ЭТОГО ТИПА ДАТЧИКОВ СЛУЧАЙНЫХ ЧИСЕЛ (ОПРЕДЕЛЕННЫЙ В ТЕКСТЕ ТОЛЬКО
ДЛЯ ЛИНЕЙНЫХ КОНГРУЭНТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ С \emph{МАКСИМАЛЬНЫМ}
ПЕРИОДОМ, ТОГДА КАК У ОПРЕДЕЛЕННОЙ ЗДЕСЬ ПОСЛЕДОВАТЕЛЬНОСТИ ДЛИНА ПЕРИОДА РАВНА~$m/4$).

\ex[ь25] яРОДЕЛАЙТЕ ПРЕДЫДУЩЕЕ УПРАЖНЕНИЕ, СЧИТАЯ, ЧТО~$a\bmod 8=3$.

\rex[ь30] яОСТРОЙТЕ АЛГОРИТМ, ПОДОБНЫЙ АЛГОРИТМУ~S, ЗА ИСКЛЮЧЕНИЕМ ТОГО,
ЧТО В НЕМ ИСПОЛЬЗУЕТСЯ ПРЕОБРАЗОВАНИЕ~$U$, ДЛЯ КОТОРОГО ВСЕ
НЕНУЛЕВЫЕ НЕДИАГОНАЛЬНЫЕ ЭЛЕМЕНТЫ НАХОДЯТСЯ В \emph{СТОЛБЦЕ}~$k$, А НЕ В
\emph{СТРОКЕ}~$k$, КАК В~(25). ёРАВНИТЕ ЭТОТ МЕТОД С АЛГОРИТМОМ~S.
яОКАЖИТЕ, ЧТО В ЭТОМ АЛГОРИТМЕ ВЕЛИЧИНА~$\prod (2c_j+1)$  В ШАГЕ~S3
НИКОГДА НЕ УВЕЛИЧИВАЕТСЯ ОТ ОДНОЙ ИТЕРАЦИИ К ДРУГОЙ.

\ex[ь50] эЕСМОТРЯ НА ТО ЧТО В ПРИМЕРЕ ИЗ УПР.~18 ОСНОВНОЙ ЦИКЛ
АЛГОРИТМА~S ВЫНУЖДЕН БЕСКОНЕЧНО ПОВТОРЯТЬСЯ, ДЛЯ "ДВОЙСТВЕННОГО"
АЛГОРИТМА ИЗ УПР.~22 ТОТ ЖЕ ПРИМЕР НЕ ПРЕДСТАВЛЯЕТ НИКАКОЙ ПРОБЛЕМЫ. фЛЯ
УДОБСТВА БУДЕМ НАЗЫВАТЬ ПОСЛЕДНИЙ МЕТОД АЛГОРИТМОМ~$S'$. ЄАК КАК
АЛГОРИТМ~$S'$ В СУЩНОСТИ ЯВЛЯЕТСЯ АЛГОРИТМОМ~S, В КОТОРОМ ПОМЕНЯЛИСЬ
РОЛЯМИ МАТРИЦЫ~$Q$ И~$R$, ТАКЖЕ СУЩЕСТВУЮТ МАТРИЦЫ, ЗАСТАВЛЯЮЩИЕ
ЗАЦИКЛИВАТЬСЯ И ЭТОТ АЛГОРИТМ. юТСЮДА ВЫТЕКАЕТ ИДЕЯ КОМБИНАЦИИ ДВУХ
МЕТОДОВ. эАПРИМЕР, МЫ МОЖЕМ ИСПОЛЬЗОВАТЬ АЛГОРИТМ~S, ПОКА ОН НЕ
ЗАСТРЯНЕТ, ЗАТЕМ ПЕРЕКЛЮЧИТЬСЯ НА АЛГОРИТМ~$S'$ ДО ТЕХ ПОР, ПОКА
\emph{ЭТОТ} НЕ ЗАСТРЯНЕТ, ВЕРНУТЬСЯ ЗАТЕМ СНОВА К АЛГОРИТМУ~S И Т. Д.

яОЛЬЗУЯСЬ ТАКИМ КОМБИНИРОВАННЫМ АЛГОРИТМОМ И ИГНОРИРУЯ ВЕТВЛЕНИЕ
НА ШАГЕ~S3, МЫ МОЖЕМ ПРИ РЕАЛИЗАЦИИ ВЫЧИСЛИТЕЛЬНОЙ ПРОЦЕДУРЫ ОКАЗАТЬСЯ В
ОДНОЙ ИЗ ДВУХ СИТУАЦИЙ: (a)~УСТАНАВЛИВАЕТСЯ ЦИКЛ, В КОТОРОМ, КАЖДЫЙ
ИЗ АЛГОРИТМОВ~S И~$S'$ НЕКОТОРЫМ ОБРАЗОМ ПОПЕРЕМЕННО ПРЕОБРАЗУЮТ~$Q$ И~$R$,
 ТАК ЧТО ВЫЧИСЛЕНИЯ НИКОГДА НЕ СМОГУТ ПРЕКРАТИТЬСЯ, ИЛИ (b)~МЫ ПОЛУЧАЕМ
МАТРИЦЫ~$Q$ И~$R$, НА КОТОРЫЕ НЕ ВЛИЯЮТ НИ АЛГОРИТМ~S, НИ АЛГОРИТМ~$S'$.

¤ТИ НАБЛЮДЕНИЯ, ЕСТЕСТВЕННО, ПРИВОДЯТ К ПОСТАНОВКЕ СЛЕДУЮЩИХ ТРЕХ
ВОПРОСОВ, НА КОТОРЫЕ ДОЛЖЕН БЫТЬ ДАН ОТВЕТ, ЕСЛИ НАМ НУЖНО ИМЕТЬ
ПОЛНОСТЬЮ УДОВЛЕТВОРИТЕЛЬНОЕ РЕШЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ПРОБЛЕМЫ,
СФОРМУЛИРОВАННОЙ В ЭТОМ РАЗДЕЛЕ. ьОЖЕТ ЛИ РЕАЛИЗОВАТЬСЯ СЛУЧАЙ~(a)? ъАК
ДОЛГО МОЖНО ИСКАТЬ КОНСТАНТЫ~$\prod (2c_j+1)$ НА ШАГЕ~S3 В СЛУЧАЕ~(b)?
ёУЩЕСТВУЕТ ЛИ ОБЩАЯ ПРОЦЕДУРА
ВЫЧИСЛЕНИЯ~$\min\{\, x^TQx \mid \hbox{ЦЕЛЫЕ~$x\ne 0$}\,\}$ ДЛЯ ПОЛОЖИТЕЛЬНО
ОПРЕДЕЛЕННОЙ МАТРИЦЫ~$Q$, КОТОРАЯ БЫЛА БЫ ЛУЧШЕ, ЧЕМ ТОЛЬКО ЧТО ОПИСАННАЯ
КОМБИНАЦИЯ АЛГОРИТМОВ~$S$ И~$S'$?

\emph{чАМЕЧАНИЕ.} тТОРОЙ ИЗ ПОСТАВЛЕННЫХ ВЫШЕ ВОПРОСОВ МОЖНО СВЕСТИ К
СЛЕДУЮЩЕМУ: \emph{яУСТЬ~$Q$---СИММЕТРИЧНАЯ ПОЛОЖИТЕЛЬНО ОПРЕДЕЛЕННАЯ
$n\times n\hbox{-МАТРИЦА}$ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ, У КОТОРОЙ ДИАГОНАЛЬНЫЕ
ЭЛЕМЕНТЫ РАВНЫ~$1$, А~$\abs{q_{ij}}\le 1/2$ ДЛЯ~$i\ne j$. яУСТЬ~$R=Q^{-1}$,
a~$\abs{r_{ij}}\le (1/2) r_{jj}$ ДЛЯ~$i\ne j$. ъАК. ВЕЛИКО МОЖЕТ БЫТЬ ПРИ
ЭТИХ УСЛОВИЯХ ЧИСЛО~$r_{11}$?} фО СИХ ПОР НЕ ВСТРЕЧАЛИСЬ ПОДОБНЫЕ МАТРИЦЫ,
ДЛЯ КОТОРЫХ~$r_{11}\ge 2$. хСЛИ ПРИНЯТЬ ВСЕ НЕДИАГОНАЛЬНЫЕ
ЭЛЕМЕНТЫ МАТРИЦЫ~$Q$ РАВНЫМИ~$-1/n$, ТО МОЖНО НАЙТИ, ЧТО~$r_{11}=2n/(n+1)$.
¤ТОТ ПРИМЕР ПОКАЗЫВАЕТ, ЧТО НИКОГДА НЕЛЬЗЯ ПРЕДПОЛАГАТЬ, ЧТО КОНСТАНТА НА
ШАГЕ~S3 ПРИМЕТ ЗНАЧЕНИЕ, МЕНЬШЕЕ~$3^n$, ДЛЯ ПРОИЗВОЛЬНОЙ ПОЛОЖИТЕЛЬНО
ОПРЕДЕЛЕННОЙ МАТРИЦЫ, ДАЖЕ В СЛУЧАЕ КОМБИНАЦИИ АЛГОРИТМОВ~S И~$S'$. т
ПРИМЕРЕ ДОСТИГАЕТСЯ~$\max r_{11}$ ДЛЯ~$n=2$, НО НЕ ДЛЯ~$n=3$.

\ex[ь20] ёРАВНИТЕ ПРЕОБРАЗОВАНИЕ ЇУРЬЕ~$f(s_1,~\ldots, s_n)$, ЗАДАННОЕ
ФОРМУЛОЙ~(1), С \emph{ПРОИЗВОДШЦЕЙ ФУНКЦИЕЙ} ОТ $n$~ПЕРЕМЕННЫХ
ДЛЯ~$F(t_1,~\ldots, t_n)$, onpeДЕЛЕННОЙ
%% 125
ОБЫЧНЫМ ОБРАЗОМ:
$$
g(z_1, \ldots, z_n)=\sum_{0\le t_1 \ldots t_n<m} F(t_1, \ldots, t_n)z_1^{t_1}\ldots z_n^{t_n}.
$$

\ex[ть28] (Ё.~ъОВЭЮ.) яРОАНАЛИЗИРУЙТЕ ДВУМЕРНОЕ ПРЕОБРАЗОВАНИЕ
ЇУРЬЕ~$f(s_1, s_2)$ ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТИ~(3.2.2-4) В МОДИФИЦИРОВАННОМ
МЕТОДЕ СЕРЕДИНЫ КВАДРАТА. [\emph{єКАЗАНИЕ:} РАССМОТРЕТЬ ДВОЙНУЮ СУММУ
ДЛЯ~$\abs{f(s_1, s_2)}^2=f(s_1, s_2)\times f(-s_1, -s_2)$.]

\rex[ь26] ўЕМУ РАВНО ЗНАЧЕНИЕ ТРЕХМЕРНОГО ПРЕОБРАЗОВАНИЯ ЇУРЬЕ~$f(s_1, s_2, s_3)$
ПОСЛЕДОВАТЕЛЬНОСТИ~(3.2.2-8), ИМЕЮЩЕЙ ДЛИНУ ПЕРИОДА~$p^2-1$, В СЛУЧАЕ~$k=2$?

\rex[ть24] (фЖ.~ьАРСАЛЬЯ.) яУСТЬ~$X_0$, $a$, $m$, $c$ ПОРОЖДАЮТ ЛИНЕЙНУЮ
КОНГРУЭНТНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ, И~$U_0$, $U_1$, $U_2$,~$\ldots=X_0/m$,
$X_1/m$, $X_2/m~\ldots\,$. яРЕДПОЛОЖИВ, ЧТО~$s_1$, $s_2$,~\dots,
$s_n$---ЦЕЛЫЕ" ЧИСЛА, УДОВЛЕТВОРЯЮЩИЕ~(11), ДОКАЖИТЕ СЛЕДУЮЩИЕ УТВЕРЖДЕНИЯ:
(a)~КАЖДЫЙ НАБОР $n$~ЧИСЕЛ $(U_k, U_{k+1},~\ldots, U_{k+n-1})$ ОПРЕДЕЛЯЕТ
В $n\hbox{-МЕРНОМ}$ ПРОСТРАНСТВЕ ТОЧКУ, ЛЕЖАЩУЮ НА ОДНОЙ ИЗ
ГИПЕРПЛОСКОСТЕЙ, ЗАДАВАЕМЫХ УРАВНЕНИЕМ
$$
s_1 x_1 + s_2 x_2 +\cdots + s_n x_n=N+(s(a)-s(1))c/(a-1)m,
$$
ГДЕ~$N$---ЦЕЛОЕ, А $s(a)$~ОПРЕДЕЛЯЕТСЯ ФОРМУЛОЙ~(7). (b)~ЁАССТОЯНИЕ МЕЖДУ
СОСЕДНИМИ ПЛОСКОСТЯМИ РАВНО~$1/\sqrt{s_1^2+\cdots+s_n^2}$. (c)~ўИСЛО
ТАКИХ ГИПЕРПЛОСКОСТЕЙ, ПЕРЕСЕКАЮЩИХ $n\hbox{-МЕРНЫЙ}$
КУБ~$0\le x_1,~\ldots, x_n<1$, РАВНО~$\abs{s_1}+\cdots+\abs{s_n}-\delta$,
ГДЕ~$\delta=1$, ЕСЛИ~$s_i s_j < 0$ ДЛЯ НЕКОТОРЫХ~$i$, $j$, В ПРОТИВНОМ
СЛУЧАЕ~$\delta=0$.

\emph{чАМЕЧАНИЕ.} яО СЛОВАМ уИВЕНСА, ПОСЛЕДОВАТЕЛЬНЫЕ СЛУЧАЙНЫЕ ВЕКТОРЫ,
ВЫРАБАТЫВАЕМЫЕ ЛИНЕЙНЫМИ КОНГРУЭНТНЫМИ МЕТОДАМИ, "ОСТАЮТСЯ ГЛАВНЫМ
ОБРАЗОМ В ПЛОСКОСТЯХ". ¤ТО УПРАЖНЕНИЕ УБЕДИТЕЛЬНО ДЕМОНСТРИРУЕТ НЕУДОБСТВО
ЛИНЕЙНЫХ КОНГРУЭНТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЛЯ ПРИМЕНЕНИЙ В МЕТОДЕ
ьОНТЕ-ъАРЛО, ЕСЛИ ТРЕБУЕТСЯ ВЫСОКОЕ РАЗРЕШЕНИЕ. эАПРИМЕР, ТРЕХМЕРНЫЕ
ВЕКТОРЫ~$(U_k, U_{k+1}, U_{k+2})$, ВЫРАБАТЫВАЕМЫЕ ДАТЧИКОМ~(14), ВСЕ ЛЕЖАТ
В ПАРАЛЛЕЛЬНЫХ ПЛОСКОСТЯХ, ОТСТОЯЩИХ ДРУГ ОТ ДРУГА НА $1/\nu_3\approx 0.001$~ЕДИНИЦ.

%% 126
\subchap{фЁєушх тшф√ ёыєўрщэ√ї тхышўшэ } % 3.4
ьЫ УЖЕ ЗНАЕМ, КАК С ПОМОЩЬЮ ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ ВЫРАБАТЫВАТЬ
ПОСЛЕДОВАТЕЛЬНОСТЬ ЧИСЕЛ~$U_0$, $U_1$, $U_2$,~\dots, КОТОРЫЕ ВЕДУТ СЕБЯ
ТАК, КАК ЕСЛИ БЫ ИХ ВЫБИРАЛИ СЛУЧАЙНО И НЕЗАВИСИМО ИЗ МНОЖЕСТВА ЧИСЕЛ,
РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ. фЛЯ ПРАКТИЧЕСКИХ
ПРИМЕНЕНИЙ ЧАСТО БЫВАЮТ НУЖНЫ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ С ДРУГИМИ РАСПРЕДЕЛЕНИЯМИ.
эАПРИМЕР, ЕСЛИ МЫ ХОТИМ СДЕЛАТЬ ВЫБОР МЕЖДУ $k$~ВОЗМОЖНЫМИ АЛЬТЕРНАТИВАМИ,
НАМ МОГУТ ПОНАДОБИТЬСЯ СЛУЧАЙНЫЕ \emph{ЦЕЛЫЕ ЧИСЛА} ОТ~$1$ ДО~$k$. хСЛИ
ДЛЯ НЕКОТОРОГО МОДЕЛИРОВАНИЯ ТРЕБУЮТСЯ СЛУЧАЙНЫЕ ПРОМЕЖУТКИ ВРЕМЕНИ МЕЖДУ
КАКИМИ-ТО НЕЗАВИСИМЫМИ СОБЫТИЯМИ, ПОЛЬЗУЮТСЯ СЛУЧАЙНЫМИ ВЕЛИЧИНАМИ С
"ЭКСПОНЕНЦИАЛЬНЫМ РАСПРЕДЕЛЕНИЕМ". шНОГДА МЫ ВООБЩЕ НЕ НУЖДАЕМСЯ В
СЛУЧАЙНЫХ \emph{ЧИСЛАХ,} А ИНТЕРЕСУЕМСЯ СЛУЧАЙНЫМИ ПЕРЕСТАНОВКАМИ
(РАССТАНОВКОЙ $n$~ЭЛЕМЕНТОВ В СЛУЧАЙНОМ ПОРЯДКЕ) ИЛИ СЛУЧАЙНЫМИ
СОЧЕТАНИЯМИ (Т.~Е.~СЛУЧАЙНЫМ ВЫБОРОМ $k$~ЭЛЕМЕНТОВ ИЗ $n$~ВОЗМОЖНЫХ).

т ПРИНЦИПЕ ЛЮБУЮ ИЗ ЭТИХ СЛУЧАЙНЫХ ВЕЛИЧИН МОЖНО ПОЛУЧИТЬ С ПОМОЩЬЮ
СЛУЧАЙНЫХ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ ЧИСЕЛ~$U_0$, $U_1$, $U_2$,~\dots%
\note{1}{
эИЖЕ ВЕЗДЕ, ГДЕ ГОВОРИТСЯ ПРОСТО О СЛУЧАЙНЫХ ЧИСЛАХ,
ПОДРАЗУМЕВАЮТСЯ СЛУЧАЙНЫЕ ЧИСЛА С РАВНОМЕРНЫМ РАСПРЕДЕЛЕНИЕМ В
ИНТЕРВАЛЕ~$(0, 1)$.---{\sl яРИМ. ПЕРЕВ.\/}}. фЛЯ ЭТОГО СУЩЕСТВУЕТ РЯД ВАЖНЫХ
ПРИЕМОВ, ЭФФЕКТИВНО ИСПОЛЬЗУЕМЫХ ПРИ РАБОТЕ НА ВЫЧИСЛИТЕЛЬНЫХ МАШИНАХ,
шЗУЧЕНИЕ ЭТИХ ПРИЕМОВ ПОЗВОЛЯЕТ ПОНЯТЬ, КАК МОЖНО ПРИМЕНЯТЬ СЛУЧАЙНЫЕ
ЧИСЛА В ЛЮБЫХ ПРИЛОЖЕНИЯХ МЕТОДА ьОНТЕ-ъАРЛО.

ьОЖНО ДОПУСТИТЬ, ЧТО КОГДА-НИБУДЬ КТО-НИБУДЬ ИЗОБРЕТЕТ ДАТЧИК,
ВЫРАБАТЫВАЮЩИЙ ЭТИ ДРУГИЕ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ \emph{НЕПОСРЕДСТВЕННО,} А
НЕ С ПОМОЩЬЮ СЛУЧАЙНЫХ ЧИСЕЛ С РАВНОМЕРНЫМ РАСПРЕДЕЛЕНИЕМ. ъРОМЕ СЛУЧАЯ
ДАТЧИКА "СЛУЧАЙНЫХ БИТОВ", ОПИСАННОГО В П.~3.2.2, ДО СИХ ПОР НЕ БЫЛО
ДОКАЗАНО, ЧТО КАКОЙ-ЛИБО ПОДОБНЫЙ ПРЯМОЙ МЕТОД МОЖЕТ ОКАЗАТЬСЯ БОЛЕЕ ВЫГОДНЫМ.

т СЛЕДУЮЩЕМ РАЗДЕЛЕ БУДЕМ ПРЕДПОЛАГАТЬ, ЧТО~$U_0$, $U_1$,
$U_2$,~\dots---СЛУЧАЙНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ, РАВНОМЕРНО
РАСПРЕДЕЛЕННЫХ МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ. сУКВОЙ~$U$ БЕЗ ИНДЕКСА БУДЕМ
ОБОЗНАЧАТЬ ТЕКУЩИЙ ЭЛЕМЕНТ ЭТОЙ ПОСЛЕДОВАТЕЛЬНОСТИ. сУДЕМ СЧИТАТЬ, ЧТО
НОВОЕ~$U$ ВЫРАБАТЫВАЕТСЯ НЕЗАВИСИМО ОТ ТОГО, ПОНАДОБИТСЯ ЛИ ОНО НАМ ИЛИ
НЕТ. юБЫЧНО СЛУЧАЙНЫЕ ЧИСЛА ПРЕДСТАВЛЯЮТСЯ СОДЕРЖИМЫМ ВСЕГО СЛОВА
ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ,
%% 127
В ПРЕДПОЛОЖЕНИИ, ЧТО ДЕСЯТИЧНАЯ ТОЧКА РАСПОЛОЖЕНА СЛЕВА. ъОНЕЧНО, НА
САМОМ ДЕЛЕ ЧИСЛО В МАШИНЕ ПРЕДСТАВЛЯЕТСЯ С ОГРАНИЧЕННОЙ ТОЧНОСТЬЮ. ш
ЕСЛИ ЭТА ТОЧНОСТЬ ПО КАКОЙ-ЛИБО ПРИЧИНЕ ОКАЖЕТСЯ НЕДОСТАТОЧНОЙ, ВСЕГДА
МОЖНО ОБоЕДИНИТЬ НЕСКОЛЬКО~$U$ ВОДНО ЧИСЛО С БОЛЕЕ ВЫСОКОЙ ТОЧНОСТЬЮ.

\subsubchap{ўИСЛОВЫЕ РАСПРЕДЕЛЕНИЯ}
т ЭТОМ РАЗДЕЛЕ РАССКАЗЫВАЕТСЯ О НАИБОЛЕЕ ИЗВЕСТНЫХ
МЕТОДАХ ПОЛУЧЕНИЯ СЛУЧАЙНЫХ ВЕЛИЧИН ДЛЯ РАЗЛИЧНЫХ ВАЖНЫХ РАСПРЕДЕЛЕНИЙ.
ьНОГИЕ ИЗ ЭТИХ МЕТОДОВ ПЕРВОНАЧАЛЬНО БЫЛИ ПРЕДЛОЖЕНЫ фЖОНОМ ФОН эЕЙМАНОМ В
НАЧАЛЕ 50-Х ГОДОВ, А ЗАТЕМ ПОСТЕПЕННО УЛУЧШАЛИСЬ ДРУГИМИ ЛЮДЬМИ, ОСОБЕННО
фЖОРДЖЕМ ьАРСАЛЬЕЙ.

\section{A.~ёЛУЧАЙНЫЙ ВЫБОР ИЗ КОНЕЧНОГО МНОЖЕСТВА}. яРОСТЕЙШИМ И НАИБОЛЕЕ
ОБЩИМ ТИПОМ РАСПРЕДЕЛЕНИЙ, НЕОБХОДИМЫХ ДЛЯ ПРАКТИКИ, ЯВЛЯЮТСЯ
РАСПРЕДЕЛЕНИЯ \emph{ЦЕЛОЧИСЛЕННЫХ} СЛУЧАЙНЫХ ВЕЛИЧИН. ЎЕЛОЕ ЧИСЛО ОТ~$0$
ДО~$7$ МОЖНО ИЗВЛЕЧЬ ИЗ 3~БИТОВ СЛОВА~$U$ В ДВОИЧНОЙ ВЫЧИСЛИТЕЛЬНОЙ МАШИНЕ.
 т ЭТОМ СЛУЧАЕ ЕГО СЛЕДУЕТ БРАТЬ ИЗ \emph{САМЫХ СТАРШИХ} (ЛЕВЫХ) РАЗРЯДОВ
СЛОВА, ТАК КАК У МНОГИХ ДАТЧИКОВ МЛАДШИЕ РАЗРЯДЫ НЕДОСТАТОЧНО СЛУЧАЙНЫ.
(¤ТО ОБСУЖДАЛОСЬ В~П.~3.2.1.1.)

тООБЩЕ, ЧТОБЫ ПОЛУЧИТЬ СЛУЧАЙНОЕ ЧИСЛО~$X$ МЕЖДУ~$0$ И~$k-1$, МЫ МОЖЕМ
\emph{УМНОЖИТЬ}~$U$ НА~$k$ И ПОЛОЖИТЬ~$X=\floor{kU}$. фЛЯ~\MIX{} МОЖНО НАПИСАТЬ
$$
\vcenter{
\mixcode
LDA & U
MUL & K
\endmixcode
}
\eqno(1)
$$

яОСЛЕ ТОГО КАК ЭТИ ДВЕ КОМАНДЫ БУДУТ ВЫПОЛНЕНЫ, ИСКОМОЕ ЦЕЛОЕ ЧИСЛО
ОКАЖЕТСЯ В РЕГИСТРЕ~$A$. хСЛИ ТРЕБУЕТСЯ СЛУЧАЙНОЕ ЦЕЛОЕ МЕЖДУ~$1$ И~$k$, МЫ
ДОБАВЛЯЕМ К РЕЗУЛЬТАТУ ЕДИНИЦУ. [чА~(1) ПОСЛЕДУЕТ КОМАНДА~"|INCA~1|".]

¤ТОТ МЕТОД ДАЕТ КАЖДОЕ ЦЕЛОЕ ЧИСЛО С РАВНОЙ ВЕРОЯТНОСТЬЮ. [эЕБОЛЬШОЙ
ОШИБКОЙ, ВЫЗВАННОЙ КОНЕЧНОСТЬЮ РАЗМЕРА МАШИННОГО СЛОВА (СМ.~УПР.~2),
ВПОЛНЕ МОЖНО ПРЕНЕБРЕЧЬ, ЕСЛИ $k$~МАЛО, НАПРИМЕР ЕСЛИ~$k/m<1/10000$.] т
БОЛЕЕ ОБЩЕМ СЛУЧАЕ МЫ МОГЛИ БЫ ЗАХОТЕТЬ ПРИПИСАТЬ РАЗЛИЧНЫМ ЦЕЛЫМ ЧИСЛАМ
РАЗНЫЕ ВЕСА. яРЕДПОЛОЖИМ, ЧТО ЗНАЧЕНИЕ~$X=x_1$ ДОЛЖНО ПОЛУЧАТЬСЯ С
ВЕРОЯТНОСТЬЮ~$p_1$, $X=x_2$ С ВЕРОЯТНОСТЬЮ~$p_2$,~\dots, И~$X=x_k$ С
ВЕРОЯТНОСТЬЮ~$p_k$. ьЫ МОЖЕМ ВЫРАБОТАТЬ РАВНОМЕРНО РАСПРЕДЕЛЕННОЕ
ЧИСЛО~$U$ И ПРИНЯТЬ
$$
X=\cases{
x_1, & ЕСЛИ~$0\le U < p_1$;\cr
x_2, & ЕСЛИ~$p_1\le U<p_1+p_2$;\cr
\ldots\cr
x_k, & ЕСЛИ~$p_1+p_2+\cdots+p_{k-1}\le U < 1$.\cr
}
\eqno(2)
$$
(чАМЕТИМ, ЧТО~$p_1+p_2+\cdots+p_k=1$.)
%% 128

ёУЩЕСТВУЕТ ОПТИМАЛЬНЫЙ СПОСОБ СРАВНЕНИЯ~$U$ С
РАЗЛИЧНЫМИ ЗНАЧЕНИЯМИ~$p_1+p_2+\cdots+p_s$, КАК ЭТО ТРЕБУЕТСЯ ДЛЯ
ВЫЧИСЛЕНИЙ~(2); ЭТО ОБСУЖДАЕТСЯ В П.~2.3.4.5. ьОЖНО
ВОСПОЛЬЗОВАТЬСЯ ТАКЖЕ КОМАНДОЙ "ПОИСК В ТАБЛИЦЕ", ИМЕЮЩЕЙСЯ В НЕКОТОРЫХ
МАШИНАХ. ъ ЧАСТНЫМ СЛУЧАЯМ ПРИМЕНИМЫ БОЛЕЕ ЭФФЕКТИВНЫЕ МЕТОДЫ. эАПРИМЕР,
ЧТОБЫ ПОЛУЧИТЬ ОДНО ИЗ ОДИННАДЦАТИ ЗНАЧЕНИЙ~$2$, $3$,~\dots, $12$ С
СООТВЕТСТВУЮЩИМИ ВЕРОЯТНОСТЯМИ~$1\over 36$, $2\over 36$,~\dots, $6\over
36$,~\dots, $2\over 36$, $1\over 36$, МОГЛИ БЫ ВЫЧИСЛИТЬ ДВА НЕЗАВИСИМЫХ
СЛУЧАЙНЫХ ЦЕЛЫХ ЧИСЛА ОТ~$1$ ДО~$6$, А ЗАТЕМ ИХ СЛОЖИТЬ.

юДНАКО НИ ОДИН ИЗ ПЕРЕЧИСЛЕННЫХ ВЫШЕ СПОСОБОВ НЕ ПОЗВОЛЯЕТ МАКСИМАЛЬНО
БЫСТРО ВЫБРАТЬ~$x_1$,~\dots, $x_k$ С ПРАВИЛЬНЫМИ ВЕРОЯТНОСТЯМИ.
чНАЧИТЕЛЬНО БОЛЕЕ ЭФФЕКТИВНЫЙ ДЛЯ БОЛЬШИНСТВА СЛУЧАЕВ МЕТОД, ТРЕБУЮЩИЙ
НЕБОЛЬШОГО УВЕЛИЧЕНИЯ ПАМЯТИ, РАССМАТРИВАЕТСЯ В УПР.~20 И~21.

\section{B.~юБЩИЕ МЕТОДЫ ДЛЯ НЕПРЕРЫВНЫХ РАСПРЕДЕЛЕНИЙ}. ёАМОЕ ОБЩЕЕ
РАСПРЕДЕЛЕНИЕ ДЕЙСТВИТЕЛЬНЫХ СЛУЧАЙНЫХ ВЕЛИЧИН ОПИСЫВАЕТСЯ В ТЕРМИНАХ
"ФУНКЦИИ РАСПРЕДЕЛЕНИЯ"~$F(x)$; МЫ ТРЕБУЕМ, ЧТОБЫ СЛУЧАЙНАЯ ВЕЛИЧИНА~$X$
ПРИНИМАЛА ЗНАЧЕНИЕ, МЕНЬШЕЕ ИЛИ РАВНОЕ~$x$, С ВЕРОЯТНОСТЬЮ~$F(x)$:
$$
F(x)= \hbox{ВЕРОЯТНОСТЬ} (X\le x).
\eqno (3)
$$
¤ТА ФУНКЦИЯ ВСЕГДА МОНОТОННО УВЕЛИЧИВАЕТСЯ ОТ НУЛЯ ДО ЕДИНИЦЫ:
$$
F(x_1) \le F(x_2), \rem{ЕСЛИ~$x_1\le x_2$; $F(-\infty)=0$, $F(+\infty)=1$.}
\eqno (4)
$$
яРИМЕРЫ ФУНКЦИЙ РАСПРЕДЕЛЕНИЯ ПРИВОДЯТСЯ В П.~3.3.1, РИС.~3. хСЛИ~$F(x)$
НЕПРЕРЫВНА И СТРОГО ВОЗРАСТАЕТ (ТАК ЧТО~$F(x_1)<F(x_2)$, ЕСЛИ~$x_1<x_2$),
ОНА ПРИНИМАЕТ ВСЕ ЗНАЧЕНИЯ МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ, И СУЩЕСТВУЕТ ОБРАТНАЯ
ФУНКЦИЯ~$F^{-1}(y)$, ТАКАЯ, ЧТО ЕСЛИ~$0<y<1$, ТО
$$
y=F(x) \hbox{ ТОГДА И ТОЛЬКО ТОГДА, КОГДА } x=F^{-1}(y).
\eqno (5)
$$
юБЩИЙ СПОСОБ ВЫЧИСЛЕНИЯ СЛУЧАЙНОЙ ВЕЛИЧИНЫ~$X$ С НЕПРЕРЫВНОЙ СТРОГО
ВОЗРАСТАЮЩЕЙ ФУНКЦИЕЙ РАСПРЕДЕЛЕНИЯ~$F(x)$ ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО ПОЛАГАЮТ
$$
X=F^{-1}(U).
\eqno(6)
$$

т САМОМ ДЕЛЕ, ВЕРОЯТНОСТЬ ТОГО, ЧТО~$X\le x$, ЯВЛЯЕТСЯ ВЕРОЯТНОСТЬЮ ТОГО,
 ЧТО~$F^{-1}(U)\le x$, Т.~Е.\ ВЕРОЯТНОСТЬЮ СОБЫТИЯ~$U\le F(x)$, А ОНА РАВНА~$F(x)$.

ЄЕПЕРЬ ЗАДАЧА СВОДИТСЯ К ОДНОЙ ИЗ ПРОБЛЕМ ЧИСЛЕННОГО АНАЛИЗА ДЛЯ
ОПРЕДЕЛЕНИЯ ХОРОШИХ МЕТОДОВ ВЫЧИСЛЕНИЯ~$F^{-1}(U)$ С ТРЕБУЮЩЕЙСЯ ТОЧНОСТЬЮ.
ўИСЛЕННЫЙ АНАЛИЗ ВЫХОДИТ ЗА РАМКИ ЭТОЙ КНИГИ. юДНАКО СУЩЕСТВУЕТ РЯД
ВАЖНЫХ РАЦИОНАЛЬНЫХ ПРИЕМОВ,
%% 129
ПРИГОДНЫХ ДЛЯ УСКОРЕНИЯ ЭТОГО ОБЩЕГО МЕТОДА, И МЫ ИХ ЗДЕСЬ РАССМОТРИМ.

яРЕЖДЕ ВСЕГО, ЕСЛИ~$X_1$ И~$X_2$---НЕЗАВИСИМЫЕ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ С
ФУНКЦИЯМИ РАСПРЕДЕЛЕНИЯ~$F_1(x)$ И~$F_2(x)$, ТО
$$
\eqalign{
\max(X_1, X_2) & \rem{ИМЕЕТ РАСПРЕДЕЛЕНИЕ~$F_1(x)F_2(x)$,}\cr
\min(X_1, X_2) & \rem{ИМЕЕТ РАСПРЕДЕЛЕНИЕ~$F_1(x)+F_2(x)-F_1(x)F_2(x)$.}\cr
}
\eqno(7)
$$
(ёМ.~УПР.~4.) эАПРИМЕР, СЛУЧАЙНОЕ ЧИСЛО~$U$ ИМЕЕТ ФУНКЦИЮ
РАСПРЕДЕЛЕНИЯ~$F(x)=x$ ДЛЯ~$0\le x < 1$. хСЛИ~$U_1$, $U_2$,~\dots,
$U_t$---НЕЗАВИСИМЫЕ СЛУЧАЙНЫЕ ЧИСЛА, ТО~$\max(U_1, U_2,~\ldots, U_t)$ ИМЕЕТ
ФУНКЦИЮ РАСПРЕДЕЛЕНИЯ~$F(x)=x^t$, $0\le x < 1$. ¤ТО ЛЕЖИТ В ОСНОВЕ ТЕСТА
"НАИБОЛЬШЕЕ ИЗ~$t$", ОПИСАННОГО В~П.~3.3.2. чАМЕТИМ, ЧТО ОБРАТНАЯ ФУНКЦИЯ
В ЭТОМ СЛУЧАЕ ЕСТЬ~$F^{-1}(y)=\root t \of{y}$. ЄАКИМ ОБРАЗОМ, В ЧАСТНОМ
СЛУЧАЕ~$t=2$ МЫ ВИДИМ, ЧТО ДВЕ ФОРМУЛЫ
$$
X=\sqrt{U} \hbox{ И } X=\max(U_1, U_2)
\eqno (8)
$$
ПРИВОДЯТ К ЭКВИВАЛЕНТНЫМ РАСПРЕДЕЛЕНИЯМ СЛУЧАЙНОЙ ВЕЛИЧИНЫ~$X$, ХОТЯ НА
ПЕРВЫЙ ВЗГЛЯД ЭТО НЕ ОЧЕВИДНО. ьЫ ИЗБАВЛЕНЫ ОТ НЕОБХОДИМОСТИ ВЫЧИСЛЯТЬ
КВАДРАТНЫЙ КОРЕНЬ ИЗ СЛУЧАЙНОЙ ВЕЛИЧИНЫ.

ЄАКИХ ПРИЕМОВ БЕСКОНЕЧНО МНОГО. ыЮБОЙ АЛГОРИТМ, КОТОРОМУ НА ВХОДЕ ЗАДАЮТСЯ
СЛУЧАЙНЫЕ ЧИСЛА, НА ВЫХОДЕ ВЫДАЕТ СЛУЧАЙНУЮ ВЕЛИЧИНУ С \emph{НЕКОТОРЫМ}
РАСПРЕДЕЛЕНИЕМ. чАДАЧА ЗАКЛЮЧАЕТСЯ В ОПРЕДЕЛЕНИИ ОБЩИХ МЕТОДОВ ПОСТРОЕНИЯ
АЛГОРИТМА, ИМЕЯ ЗАДАННУЮ ФУНКЦИЮ РАСПРЕДЕЛЕНИЯ НА ВЫХОДЕ.

яОЛЬЗУЯСЬ СООТНОШЕНИЕМ~(7), МОЖНО ПОЛУЧИТЬ \emph{ПРОИЗВЕДЕНИЕ} ДВУХ
ФУНКЦИЙ РАСПРЕДЕЛЕНИЯ. ёУЩЕСТВУЕТ ТАКЖЕ МЕТОД \emph{СМЕШИВАНИЯ} ДВУХ
РАСПРЕДЕЛЕНИЙ: ПРЕДПОЛОЖИМ, ЧТО
$$
F(x)=pF_1(x)+(1-p)F_2(x), \rem{$0<p<1$.}
\eqno (9)
$$
ьЫ МОЖЕМ ВЫЧИСЛИТЬ ЗНАЧЕНИЕ СЛУЧАЙНОЙ ВЕЛИЧИНЫ~$X$ С
РАСПРЕДЕЛЕНИЕМ~$F(x)$, ОПРЕДЕЛИВ СНАЧАЛА СЛУЧАЙНОЕ ЧИСЛО~$U$. хСЛИ~$U<p$,
 СЧИТАЕМ, ЧТО $X$~ИМЕЕТ РАСПРЕДЕЛЕНИЕ~$F_1(x)$, ЕСЛИ ЖЕ~$U\ge p$,
ТО~$X$---СЛУЧАЙНАЯ ВЕЛИЧИНА С РАСПРЕДЕЛЕНИЕМ~$F_2(x)$.

¤ТА ПРОЦЕДУРА МОЖЕТ БЫТЬ ОЧЕНЬ ПОЛЕЗНА, ЕСЛИ $p$~БЛИЗКО К ЕДИНИЦЕ,
А~$F_1(x)$---РАСПРЕДЕЛЕНИЕ, КОТОРОЕ ЛЕГКО МОДЕЛИРОВАТЬ. ЄОГДА, НЕСМОТРЯ НА
ТО ЧТО ВЫРАБОТКА СЛУЧАЙНЫХ ЗНАЧЕНИЙ ПО РАСПРЕДЕЛЕНИЮ~$F_2(x)$ МОЖЕТ БЫТЬ
БОЛЕЕ ТРУДОЕМКОЙ, ЧЕМ ДЛЯ ТРЕБУЮЩЕГОСЯ ПОЛНОГО РАСПРЕДЕЛЕНИЯ~$F(x)$,
БОЛЕЕ ТРУДНЫЕ ВЫЧИСЛЕНИЯ ДОЛЖНЫ БУДУТ ПРОВОДИТЬСЯ РЕДКО, С
ВЕРОЯТНОСТЬЮ~$(1-p)$. эИЖЕ МЫ УВИДИМ, ЧТО ЭТА ИДЕЯ С УСПЕХОМ ИСПОЛЬЗУЕТСЯ
ДЛЯ НЕСКОЛЬКИХ ВАЖНЫХ СЛУЧАЕВ.

\section{C.~эОРМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ}. \dfn{эОРМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ СО
СРЕДНИМ ЗНАЧЕНИЕМ, РАВНЫМ НУЛЮ, И СТАНДАРТНЫМ ОТКЛОНЕНИЕМ, РАВНЫМ
%% 129
ЕДИНИЦЕ,} ЯВЛЯЕТСЯ, ВОЗМОЖНО, ВАЖНЕЙШИМ ИЗ НЕРАВНОМЕРНЫХ НЕПРЕРЫВНЫХ РАСПРЕДЕЛЕНИЙ:
$$
F(x)={1\over \sqrt{2\pi}}\int_{-\infty}^x e^{-t^2/2}\,dt.
\eqno(10)
$$
фЛЯ ВЫРАБОТКИ НОРМАЛЬНО РАСПРЕДЕЛЕННЫХ СЛУЧАЙНЫХ ВЕЛИЧИН СУЩЕСТВУЕТ
НЕСКОЛЬКО ПРИЕМОВ.

{\sl (1)~ьЕТОД ПОЛЯРНЫХ КООРДИНАТ.\/}

\alg Ё.(ьЕТОД ПОЛЯРНЫХ КООРДИНАТ ДЛЯ НОРМАЛЬНОГО РАСПРЕДЕЛЕНИЯ.) ¤ТОТ
АЛГОРИТМ ВЫЧИСЛЯЕТ ДВЕ НЕЗАВИСИМЫЕ НОРМАЛЬНО РАСПРЕДЕЛЕННЫЕ СЛУЧАЙНЫЕ
ВЕЛИЧИНЫ~$X_1$ И~$X_2$ ПО ДВУМ ЗАДАННЫМ НЕЗАВИСИМЫМ СЛУЧАЙНЫМ ЧИСЛАМ~$U_1$ И~$U_2$.

\st[яОЛУЧИТЬ СЛУЧАЙНЫЕ ЧИСЛА.] тЫРАБОТАТЬ ДВА НЕЗАВИСИМЫХ СЛУЧАЙНЫХ
ЧИСЛА~$U_1$, $U_2$, РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ.
єСТАНОВИТЬ~$V_1\asg 2U_1-1$, $V_2\asg 2U_2-1$. (ЄЕПЕРЬ~$V_1$ И~$V_2$
РАВНОМЕРНО РАСПРЕДЕЛЕНЫ МЕЖДУ~$-1$ И~$+1$. фЛЯ БОЛЬШИНСТВА МАШИН В ЭТОТ
МОМЕНТ ПРЕДПОЧТИТЕЛЬНЕЙ ПРЕДСТАВИТЬ~$V_1$ И~$V_2$ В ФОРМЕ С ПЛАВАЮЩЕЙ ТОЧКОЙ.)

\st[тЫЧИСЛИТЬ~$S$.] єСТАНОВИТЬ~$S\asg V_1^2+V_2^2$.

\st[$S\ge 1$?] хСЛИ~$S\ge1$, ВЕРНУТЬСЯ К ШАГУ~\stp{1}. (°АГИ С~\stp{1}
ПО~\stp{3} В СРЕДНЕМ ВЫПОЛНЯЮТСЯ $1.27$~РАЗ ПРИ СТАНДАРТНОМ
ОТКЛОНЕНИИ~$0.587$; СМ.~УПР.~6).

\st[тЫЧИСЛИТЬ~$X_1$, $X_2$.] яРИСВОИТЬ~$X_1$, $X_2$ ЗНАЧЕНИЯ, ВЫЧИСЛЕННЫЕ
ПО ФОРМУЛАМ
$$
X_1=V_1\sqrt{-2\ln S\over S}, \qquad
X_2=V_2\sqrt{-2\ln S\over S}.
\eqno(11)
$$

¤ТО И ЕСТЬ ТРЕБУЮЩИЕСЯ ЗНАЧЕНИЯ НОРМАЛЬНО РАСПРЕДЕЛЕННЫХ СЛУЧАЙНЫХ ВЕЛИЧИН.
\algend

ўТОБЫ ДОКАЗАТЬ, ЧТО МЕТОД ТОЧЕН, ВОСПОЛЬЗУЕМСЯ ЭЛЕМЕНТАРНОЙ АНАЛИТИЧЕСКОЙ
ГЕОМЕТРИЕЙ. хСЛИ НА ШАГЕ~P3 $S<1$, ТОЧКА ПЛОСКОСТИ С ДЕКАРТОВЫМИ
КООРДИНАТАМИ~$(V_1, V_2)$ ЯВЛЯЕТСЯ \emph{СЛУЧАЙНОЙ ТОЧКОЙ, РАВНОМЕРНО
РАСПРЕДЕЛЕННОЙ ВНУТРИ ЕДИНИЧНОГО КРУГА.} яЕРЕХОДЯ К ПОЛЯРНЫМ
КООРДИНАТАМ~$V_1=R\cos\Theta$, $V_2=R\sin\Theta$, НАХОДИМ~$S=R^2$,
$X_1=\sqrt{-2\ln S}\cos\Theta$, $X_2=\sqrt{-2\ln S}\sin\Theta$. шСПОЛЬЗУЯ
ТАКЖЕ ПОЛЯРНЫЕ КООРДИНАТЫ~$X_1=R'\cos\Theta'$, $X_2=R'\sin\Theta'$, МЫ
ВИДИМ, ЧТО~$\theta'=\theta$ И~$R'=\sqrt{-2\ln S}$. ▀СНО, ЧТО~$R'$
И~$\Theta'$ НЕЗАВИСИМЫ, ТАК КАК~$R$ И~$\Theta$ НЕЗАВИСИМЫ ВНУТРИ ЕДИНИЧНОГО
КРУГА. ъРОМЕ ТОГО, $\Theta'$~РАВНОМЕРНО РАСПРЕДЕЛЕНА МЕЖДУ~$0$ И~$2\pi$, А
ВЕРОЯТНОСТЬ ТОГО, ЧТО~$R'\le r$, РАВНА ВЕРОЯТНОСТИ СОБЫТИЯ---$2\ln S \le
r^2$, Т.~Е.\ ВЕРОЯТНОСТИ СОБЫТИЯ~$S\ge e^{-r^2/2}$. яОСЛЕДНЯЯ
РАВНА~$1-e^{-r^2/2}$, ПОСКОЛЬКУ~$S=R^2$ РАВНОМЕРНО РАСПРЕДЕЛЕНА МЕЖДУ
НУЛЕМ И ЕДИНИЦЕЙ.
%% 131
тЕРОЯТНОСТЬ ТОГО, ЧТО $R'$~ЛЕЖИТ МЕЖДУ~$r$ И~$r+dr$, РАВНА ПОЭТОМУ
ПРОИЗВОДНОЙ ОТ~$1-e^{-r^2/2}$, А ИМЕННО~$re^{-r^2/2}dr$. яОДОБНЫМ ЖЕ
ОБРАЗОМ ВЕРОЯТНОСТЬ ПОПАДАНИЯ~$\Theta'$ В ИНТЕРВАЛ МЕЖДУ~$\theta$
И~$\theta+d\theta$ ЕСТЬ~$(1/2\pi)d\theta$. яОЭТОМУ ВЕРОЯТНОСТЬ ТОГО,
ЧТО~$X_1\le x_1$, А~$X_2\le x_2$, РАВНА
$$
\eqalign{
\int_{\{\, (r,\theta) \mid r\cos\theta \le x_1, r\sin\theta\le x_2\,\}}{1\over 2\pi}e^{-r^2/2}r\,dr\,d\theta&=\cr
&={1\over 2\pi}\int_{\{\,(x,y) \mid x\le x_1, y\le x_2\,\}}e^{-(x^2+y^2)/2}\,dx\,dy=\cr
&=\left(\sqrt{1\over 2\pi}\int_{-\infty}^{x_1}e^{-x^2/2}\,dx\right)\left(\sqrt{1\over 2\pi}\int_{-\infty}^{x_2}e^{-y^2/2}\,dy\right).\cr
}
$$

¤ТО ДОКАЗЫВАЕТ, ЧТО~$X_1$ И~$X_2$ НЕЗАВИСИМЫ И НОРМАЛЬНО РАСПРЕДЕЛЕНЫ, КАК
И ТРЕБОВАЛОСЬ. рЛГОРИТМ~P ПРЕДЛОЖИЛИ фЖ.~сОКС, ь.~ьАЛЛЕР И~фЖ.~ьАРСАЛЬЯ.

{\sl (2)~ьЕТОД ьАРСАЛЬИ (МЕТОД ПРЯМОУГОЛЬНИКА---КЛИНА---ХВОСТА).\/}

т ЭТОМ МЕТОДЕ МЫ ИСПОЛЬЗУЕМ РАСПРЕДЕЛЕНИЕ
$$
F(x)=\sqrt{2\over\pi}\int_0^x e^{-t^2/2}\,dt \rem{$x\ge0$,}
\eqno(12)
$$
ТАК ЧТО $F(x)$~ЯВЛЯЕТСЯ ФУНКЦИЕЙ РАСПРЕДЕЛЕНИЯ \emph{МОДУЛЯ} НОРМАЛЬНОЙ
СЛУЧАЙНОЙ ВЕЛИЧИНЫ. яОСЛЕ ВЫЧИСЛЕНИЯ~$X$ В СООТВЕТСТВИИ С ЭТИМ
РАСПРЕДЕЛЕНИЕМ ЕЕ ЗНАЧЕНИЮ ПРИПИСЫВАЕТСЯ СЛУЧАЙНЫЙ ЗНАК, В РЕЗУЛЬТАТЕ МЫ
ПОЛУЧАЕМ ПРАВИЛЬНОЕ ЗНАЧЕНИЕ НОРМАЛЬНОЙ СЛУЧАЙНОЙ ВЕЛИЧИНЫ.

юБЩИЙ ПОДХОД ьАРСАЛЬИ, ПОЗВОЛЯЮЩИЙ ЭФФЕКТИВНО ИСПОЛЬЗОВАТЬ СЛУЧАЙНЫЕ
ЧИСЛА, БУДЕТ ПРОИЛЛЮСТРИРОВАН НА ПРИМЕРЕ РАСПРЕДЕЛЕНИЯ~(12). шЗУЧАЯ ЭТОТ
ЧАСТНЫЙ ПРИМЕР, МЫ ОДНОВРЕМЕННО УЗНАЕМ НЕСКОЛЬКО ОБЩИХ МЕТОДОВ.

чА ОСНОВУ ПРИНИМАЕТСЯ СЛЕДУЮЩЕЕ ПРЕДСТАВЛЕНИЕ:
$$
F(x)=p_1F_1(x)+p_2F_2(x)+\cdots+p_nF_n(x),
\eqno(13)
$$
ГДЕ~$F_1$, $F_2$,~\dots, $F_n$---НЕКОТОРЫЕ РАСПРЕДЕЛЕНИЯ. ёЛУЧАЙНАЯ
ВЕЛИЧИНА~$X$ ТОГДА ОПРЕДЕЛЯЕТСЯ ПО РАСПРЕДЕЛЕНИЮ~$F_j$ С
ВЕРОЯТНОСТЬЮ~$p_j$. эЕКОТОРЫЕ ИЗ РАСПРЕДЕЛЕНИЙ~$F_j(x)$ МОГУТ ОКАЗАТЬСЯ
ДОВОЛЬНО ТРУДНЫМИ ДЛЯ ВЫЧИСЛЕНИЙ, НО МЫ ОБЫЧНО ПОДБИРАЕМ ИХ ТАК, ЧТОБЫ В
ЭТОМ СЛУЧАЕ ВЕРОЯТНОСТЬ~$p_j$ БЫЛА ОЧЕНЬ МАЛА. сОЛЬШИНСТВО ФУНКЦИЙ
РАСПРЕДЕЛЕНИЯ~$F_j(x)$ ОКАЖУТСЯ ОЧЕНЬ ПРОСТЫМИ, БУДУЧИ ТРИВИАЛЬНЫМИ
МОДИФИКАЦИЯМИ РАВНОМЕРНОГО РАСПРЕДЕЛЕНИЯ. ьЕТОД В ЦЕЛОМ ПОЗВОЛЯЕТ
СОЗДАВАТЬ ЧРЕЗВЫЧАЙНО ЭФФЕКТИВНЫЕ ПРОГРАММЫ, ТАК КАК \emph{СРЕДНЕЕ} ВРЕМЯ
ВЫЧИСЛЕНИЙ ОЧЕНЬ МАЛО.

%% 132

ьЕТОД ЛЕГЧЕ ПОНЯТЬ, ЕСЛИ ИМЕТЬ ДЕЛО С \emph{ПРОИЗВОДНЫМИ} ФУНКЦИЙ
РАСПРЕДЕЛЕНИЯ ВМЕСТО САМИХ РАСПРЕДЕЛЕНИЙ. юБОЗНАЧИМ
$$
f(x)=F'(x), \qquad f_j(x)=F'_j(x).
$$
ЇУНКЦИИ~$f(x)$ И~$f_j(x)$ НАЗЫВАЮТСЯ \dfn{ПЛОТНОСТЯМИ} ЭТИХ ВЕРОЯТНОСТНЫХ
РАСПРЕДЕЛЕНИЙ. єРАВНЕНИЕ~(13) ПРЕОБРАЗУЕТСЯ В
$$
f(x)=p_1f_1(x)+p_2f_2(x)+\cdots+p_nf_n(x).
\eqno(14)
$$
ъАЖДАЯ~$f_j(x)\ge0$, А ПОЛНАЯ ПЛОЩАДЬ ПОД КРИВОЙ~$f_j(x)$
РАВНА~$1$. яОЭТОМУ СУЩЕСТВУЕТ ПРОСТАЯ ГРАФИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ
СООТНОШЕНИЯ~(14). яЛОЩАДЬ ПОД ГРАФИКОМ~$f(x)$ ДЕЛИТСЯ НА $n$~ЧАСТЕЙ,
КАЖДАЯ ИЗ КОТОРЫХ ИМЕЕТ ПЛОЩАДЬ~$p_j$ И СООТВЕТСТВУЕТ~$f_j(x)$. яОСМОТРИТЕ
НА РИС.~9, ПРОЯСНЯЮЩИЙ СИТУАЦИЮ ДЛЯ СЛУЧАЯ, КОТОРЫМ МЫ СЕЙЧАС ИНТЕРЕСУЕМСЯ,
КОГДА~$f(x)=F'(x)=\sqrt{(2/\pi)}e^{-x^2/2}$. яЛОЩАДЬ ПОД КРИВОЙ НА РИСУНКЕ
РАЗДЕЛЕНА НА $n=37$~ЧАСТЕЙ: $12$~ДОВОЛЬНО
\picture{ЁИС.~9. ўАСТОТНАЯ ФУНКЦИЯ, СОСТОЯЩАЯ ИЗ 37~ЧАСТЕЙ. ёЛУЧАЙНАЯ
ВЕЛИЧИНА ВЫЧИСЛЯЕТСЯ В СРЕДНЕМ СТОЛЬКО РАЗ КАКОВА ПЛОЩАДЬ ЧАСТИ,
СООТВЕТСТВУЮЩЕЙ ЕЕ ЧАСТОТЕ.}
БОЛЬШИХ ПРЯМОУГОЛЬНИКОВ,  КОТОРЫЕ СООТВЕТСТВУЮТ~$p_1f_1(x)$,~\dots,
$p_{12}f_{12}(x)$, $12$~УЗКИХ НЕБОЛЬШИХ ПРЯМОУГОЛЬНИКОВ, ПРИМЫКАЮЩИХ
СВЕРХУ К ПРЕДЫДУЩИМ И СООТВЕТСТВУЮЩИХ~$p_{13}f_{13}(x)$,~\dots,
$p_{24}f_{24}(x)$, $12$~КЛИНООБРАЗНЫХ ФИГУР, ПРЕДСТАВЛЯЮЩИХ
ФУНКЦИИ~$p_{25}f_{25}(x)$,~\dots, $p_{36}f_{36}(x)$, И ОСТАВШАЯСЯ
ЧАСТЬ~$p_{37}f_{37}(x)$, СОВПАДАЮЩАЯ С~$f(x)$ ПРИ~$x\ge3$.

ёТУПЕНЬКИ~$f_1(x)$,~\dots, $f_{12}(x)$ ОПИСЫВАЮТ \emph{РАВНОМЕРНЫЕ
РАСПРЕДЕЛЕНИЯ.} эАПРИМЕР,  $f_3(x)$ ОТВЕЧАЕТ СЛУЧАЙНОЙ ВЕЛИЧИНЕ, РАВНО-
%% 133
МЕРНО РАСПРЕДЕЛЕННОЙ МЕЖДУ~$1/2$ И~$3/4$. ьЫ ХОТИМ ОПРЕДЕЛИТЬ~$p_1$, $p_2$,~\dots,
$p_{12}$ ТАК, ЧТОБЫ ЭФФЕКТИВНО ВЫРАБАТЫВАТЬ НОРМАЛЬНЫЕ СЛУЧАЙНЫЕ
ВЕЛИЧИНЫ. (яРЕДПОЛОЖИМ, ЧТО МЫ ИМЕЕМ ДЕЛО С ДВОИЧНОЙ МАШИНОЙ; ДЛЯ
ДЕСЯТИЧНОЙ ПРИМЕНЯЕТСЯ АНАЛОГИЧНАЯ ПРОЦЕДУРА.) тЫБЕРЕМ ИХ КРАТНЫМИ, СКАЖЕМ,
$1/256$. ¤ТО ОЗНАЧАЕТ, ЧТО ПЛОЩАДЬ ПОД~$p_j f_j(x)$ БУДЕТ КРАТНА~$1/256$.
яРИМЕМ ВЫСОТУ~$f_j(x)$ РАВНОЙ
$$
\floor{64 f(j/4)}/64 \rem{$1\le j \le 12$.}
$$

т ТАБЛИЦЕ ПРИВОДЯТСЯ ПОЛУЧАЮЩИЕСЯ ПРИ ЭТОМ ЗНАЧЕНИЯ ВЕРОЯТНОСТЕЙ:
$$
\matrix{
 p_1          & p_2         & p_3         & p_4         & p_5         & p_6         & p_7         & p_8        & p_9        & p_{10}     & p_{11}     & p_{12}     & (p_{13}+\cdots+p_{37}) \cr
 49 \over 256 & 45\over 256 & 38\over 256 & 30\over 256 & 23\over 256 & 16\over 256 & 11\over 256 & 6\over 256 & 4\over 256 & 2\over 256 & 1\over 256 & 0\over 256 & 31\over 256.\cr
}
\eqno(15)
$$

юТСЮДА СЛЕДУЕТ, ЧТО РЕАЛИЗАЦИЯ РАВНОМЕРНЫХ РАСПРЕДЕЛЕНИЙ~$F_1$,~\dots,
$F_{12}$ ЗАЙМЕТ~$p_1+p_2+\cdots+p_{12}=88\%$~ВРЕМЕНИ (88\%~ПЛОЩАДИ
ПОД~$f(x)$ ЗАНИМАЮТ БОЛЬШИЕ ПРЯМОУГОЛЬНИКИ).

ьАРСАЛЬЕЙ БЫЛ ПРЕДЛОЖЕН ЭФФЕКТИВНЫЙ СПОСОБ ВЫБОРА ИЗ 13~ВОЗМОЖНОСТЕЙ,
ПРЕДСТАВЛЕННЫХ В~(15). яРИ ЗАДАННОМ СЛУЧАЙНОМ ДВОИЧНОМ ЦЕЛОМ ЧИСЛЕ В
ПРОМЕЖУТКЕ ОТ~$0$ ДО~$255$, ДВОИЧНОЕ ПРЕДСТАВЛЕНИЕ КОТОРОГО
ЕСТЬ~$b_1b_2b_3b_4b_5b_6b_7b_8$, МЫ ПОСТУПАЕМ СЛЕДУЮЩИМ ОБРАЗОМ:
$$
\vcenter{\halign{
#\bskip&\hfill$#$&${}#\quad$\hfill&{\vtop{\hsize=0.5\hsize\noindent#\par}}\cr
ЕСЛИ&   0&\le b_1b_2b_3b_4 < 10,            & ПОЛАГАЕМ~$X=A[b_1b_2b_3b_4]+{1\over4}U$;\cr
ЕСЛИ&  40&\le b_1b_2b_3b_4b_5b_6<52,        & ПОЛАГАЕМ~$X=B[b_1b_2b_3b_4b_5b_6]+{1\over4}U$;\cr
ЕСЛИ& 208&\le b_1b_2b_3b_4b_5b_6b_7b_8<225, & ПОЛАГАЕМ~$X=C[b_1b_2b_3b_4b_5b_6b_7b_8]+{1\over4}U$;\cr
ЕСЛИ& 225&\le b_1b_2b_3b_4b_5b_6b_7b_8,     & ВЫРАБАТЫВАЕМ~$X$, ИСПОЛЬЗУЯ РАСПРЕДЕЛЕНИЯ~$F_{13}$,~\dots, $F_{37}$, КАК ОПИСЫВАЕТСЯ НИЖЕ.\cr
}}
\eqno (16)
$$

чДЕСЬ~$A$, $B$, $C$---ВСПОМОГАТЕЛЬНЫЕ МАССИВЫ, ПРИВЕДЕННЫЕ В ТАБЛ.~1,
a~$U$---СЛУЧАЙНОЕ ЧИСЛО (ОТ~$0$ ДО~$1$).

ўТОБЫ ПОНЯТЬ, ПОЧЕМУ ЭТА ПРОЦЕДУРА РАБОТАЕТ, РАССМОТРИМ, НАПРИМЕР,
СЛУЧАЙ~$j=4$. ЇУНКЦИЯ~$F_4(x)$---ЭТО РАВНОМЕРНОЕ РАСПРЕДЕЛЕНИЕ СЛУЧАЙНОЙ
ВЕЛИЧИНЫ (МЕЖДУ~$3/4$ И~$1$), КОТОРОЕ ИМЕЕТ
СЛУЧАЙНАЯ ВЕЛИЧИНА~$X={3\over4}+{1\over4}U$. тЕРОЯТНОСТЬ ТОГО, ЧТО
ЭТО РАСПРЕДЕЛЕНИЕ РЕАЛИЗУЕТСЯ В ОПИСАННОМ ВЫШЕ МЕТОДЕ, ТАКОВА:
${1\over16}\times\left(\hbox{ЧИСЛО РАЗ, КОТОРОЕ "}{3\over4}\hbox{"ВСТРЕЧАЕТСЯ
В МАССИВЕ}~A\right)+{1\over 64}\times
(\hbox{АНАЛОГИЧНОЕ ЧИСЛО "ПОЯВЛЕНИЙ" В МАССИВЕ}~$B$)+
{1\over 256}\times  (\hbox{ЧИСЛО "ПОЯВЛЕНИЙ" В МАССИВЕ}~C)$.
%% 134
\htable{ЄАБЛИЦА~1}%
{ЄАБЛИЦЫ ДЛЯ ЭФФЕКТИВНОГО ВЫБОРА ИЗ 12 АЛЬТЕРНАТИВ В МЕТОДЕ~(16)}
{$\displaystyle#\quad$\hfil&$\displaystyle#\quad$\hfil&$\displaystyle#$\hfil\cr
A[0]=0         & B[40]={1\over4} & C[208]=0\cr
A[1]=0         & B[41]={1\over4} & C[209]={1\over4}\cr
A[2]=0         & B[42]={1\over4} & C[210]={1\over2}\cr
A[3]={1\over4} & B[43]={1\over2} & C[211] ={1\over2}\cr
A[4]={1\over4} & B[44]={3\over4} & C[212]={3\over4}\cr
A[5]={1\over2} & B[45]={3\over4} & C[213]={3\over4}\cr
A[6]={1\over2} & B[46]={3\over4} & C[214]=1\cr
A[7]={3\over4} & B[47]=1         & C[215]=1\cr
A[8]=1         & B[48]={3\over2} & C[216]=1\cr
A[9]={5\over4} & B[49]={3\over2} & C[217]={3\over2}\cr
               & B[50]={7\over4} & C[218]={3\over2}\cr
               & B[51]=2         & C[219]={3\over2}\cr
               &                 & C[220]={7\over4}\cr
               &                 & C[221]={7\over4}\cr
               &                 & C[222]={9\over4}\cr
               &                 & C[223]={9\over4}\cr
               &                 & C[224]={5\over2}\cr
}
юНА РАВНА~${1\over16}+{3\over 64}+{2\over 256}={30\over 256}=p_4$, ТАК
ЧТО $F_4(x)$~МОДЕЛИРУЕТСЯ С ПРАВИЛЬНОЙ ВЕРОЯТНОСТЬЮ. ъОНЕЧНО, БЫЛО БЫ ЕЩЕ
БЫСТРЕЕ ВОСПОЛЬЗОВАТЬСЯ ДРУГИМ МЕТОДОМ:
$$
\displaylines{
\hbox{"ЕСЛИ}~0\le b_1b_2b_3b_4b_5b_6b_7b_8 < 225, \hbox{ ПОЛАГАЕМ }\cr
X=T[b_1b_2b_3b_4b_5b_6b_7b_8]+{1\over4}U\hbox{"}\cr
}
$$
ВМЕСТО ПЕРВЫХ ТРЕХ ПРОВЕРОК~(16). чДЕСЬ $T$~ЗАДАВАЛОСЬ БЫ ТАБЛИЦЕЙ ИЗ
225~ЧИСЕЛ, 49 ИЗ КОТОРЫХ РАВНЯЛИСЬ БЫ~"$0$", 45~ЧИСЕЛ
РАВНЯЛИСЬ БЫ~$1\over4$, 38~РАЗ ПОВТОРЯЛОСЬ БЫ~$1\over2$ И~Т.~Д. фЛЯ
СРАВНЕНИЯ В ПРЕДЫДУЩЕМ МЕТОДЕ ИСПОЛЬЗУЕТСЯ ТОЛЬКО ТАБЛИЦА, СОДЕРЖАЩАЯ
39~ВЕЛИЧИН, И ОН НЕНАМНОГО МЕДЛЕННЕЙ, ТАК КАК
ПРОВЕРКА~"$b_1b_2b_3b_4b_5b_6<52$?", ЗАНИМАЕТ НЕ БОЛЕЕ~$3/8$ ВСЕГО ВРЕМЕНИ,
А ПРОВЕРКА~"$b_1b_2b_3b_4b_5b_6b_7b_8<225$?" ТРЕБУЕТ ТОЛЬКО
$3/16$~ВРЕМЕНИ. ¤КОНОМИЯ ПАМЯТИ В МЕТОДЕ, ПОДОБНОМ~(16), ЕЩЕ ЗНАЧИТЕЛЬНЕЙ
В ОБЩЕМ СЛУЧАЕ, КОГДА ИМЕЕТСЯ БОЛЬШЕ 256~ВОЗМОЖНОСТЕЙ.

ўИТАТЕЛЮ СЛЕДУЕТ В ЭТОМ МЕСТЕ СДЕЛАТЬ ПАУЗУ, ЧТОБЫ ТЩАТЕЛЬНО ИЗУЧИТЬ
ВЕСЬ МЕТОД, ПОКА ОН НЕ ПОЙМЕТ, ИЗ-ЗА ЧЕГО ПО ФОРМУЛАМ~(16)
РАСПРЕДЕЛЕНИЯ~$F_j$ ВЫБИРАЮТСЯ С ВЕРОЯТНОСТЯМИ~$p_j$ ДЛЯ~$1\le j \le 12$.

ЁАСПРЕДЕЛЕНИЯ~$F_{13}(x)$,~\dots, $F_{24}(x)$---ТАКЖЕ РАВНОМЕРНЫЕ, И С НИМИ
МОЖНО ПОСТУПАТЬ АНАЛОГИЧНО. юНИ ИМЕЮТ ДОВОЛЬНО МАЛУЮ ВЕРОЯТНОСТЬ
%% 135
$\bigl($НЕКОТОРОЕ ЧИСЛО МЕЖДУ~$0$ И~${1\over256}\bigr)$, ПОЭТОМУ
НАИБОЛЕЕ ЭФФЕКТИВНО ПРОВЕРЯТЬ ЭТИ ВЕРОЯТНОСТИ С ПОМОЩЬЮ ЧАСТИ
НАШЕГО АЛГОРИТМА ДЛЯ ВЫРАБОТКИ НОРМАЛЬНЫХ СЛУЧАЙНЫХ ВЕЛИЧИН, КОТОРЫЙ
БУДЕТ ИСПОЛЬЗОВАТЬСЯ НЕ СЛИШКОМ ЧАСТО (СМ.~ШАГ~M4 В АЛГОРИТМЕ~M, НИЖЕ).
¤ТИ РАСПРЕДЕЛЕНИЯ ПРЕДСТАВЛЯЮТ СОБОЙ ПОПРАВКИ К БОЛЬШИМ ПРЯМОУГОЛЬНИКАМ,
ВОЗНИКАЮЩИЕ ПРИ ОКРУГЛЕНИИ ВЕРОЯТНОСТЕЙ ДЛЯ~(15). ьЫ ИМЕЕМ
$$
p_j+p_{j+12}={1\over4}f(j/4), \rem{$1\le j \le 12$}.
\eqno(12)
$$

ЄЕПЕРЬ ВЕРНЕМСЯ К ВОПРОСУ О ВЫЧИСЛЕНИИ СЛУЧАЙНЫХ ВЕЛИЧИН ДЛЯ КЛИНООБРАЗНЫХ
РАСПРЕДЕЛЕНИЙ~$F_{25}(x)$,~\dots, $F_{36}(x)$. ЄИПИЧНЫЙ СЛУЧАЙ ИЗОБРАЖЕН
НА РИС.~10. ъОГДА~$x<1$, КРИВАЯ ВЫПУКЛА
\picture{
 ЁИС.~10. ЇУНКЦИИ ПЛОТНОСТИ ВЕРОЯТНОСТИ, ДЛЯ КОТОРЫХ ПРИ ВЫРАБОТКЕ
 СЛУЧАЙНЫХ ЧИСЕЛ МОЖЕТ БЫТЬ ИСПОЛЬЗОВАН АЛГОРИТМ~L.
}
ВВЕРХ, А ПРИ~$x>1$---ВНИЗ, НО В ОБОИХ СЛУЧАЯХ КРИВАЯ ОЧЕНЬ БЛИЗКА К ПРЯМОЙ
ЛИНИИ И МОЖЕТ БЫТЬ ВЛОЖЕНА, КАК ПОКАЗАНО НА РИСУНКЕ, МЕЖДУ ДВУМЯ ПРЯМЫМИ.

\alg L.(яОЧТИ ЛИНЕЙНЫЕ ПЛОТНОСТИ.) ¤ТОТ АЛГОРИТМ МОЖНО ИСПОЛЬЗОВАТЬ ДЛЯ
ВЫРАБОТКИ ЗНАЧЕНИЯ СЛУЧАЙНОЙ ВЕЛИЧИНЫ~$X$ ДЛЯ ЛЮБОЙ ПЛОТНОСТИ
РАСПРЕДЕЛЕНИЯ~$f(x)$, УДОВЛЕТВОРЯЮЩЕЙ СЛЕДУЮЩИМ УСЛОВИЯМ (СР.~С~РИС.~10):
$$
\displaynarrow{
 f(x)=0 \rem{ДЛЯ~$x<s$ И~$x>s+h$;}\cr
 a-b(x-s)/h \le f(x) \le b-b(x-s)/h \rem{ДЛЯ~$s\le x \le s+h$.}\cr
}
\eqno(18)
$$

\st[яОЛУЧИТЬ~$U\le V$.] тЫРАБОТАТЬ ДВА НЕЗАВИСИМЫХ СЛУЧАЙНЫХ ЧИСЛА~$U$,
$V$, РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ. хСЛИ~$U>V$,
ПОМЕНЯТЬ МЕСТАМИ~$U\xchg V$.

\st[яРОСТОЙ СЛУЧАЙ?] хСЛИ~$V\le a/b$, ПЕРЕЙТИ К~\stp{4}.

%% 136

\st[яОПЫТАТЬСЯ ЕЩЕ РАЗ?] хСЛИ~$V>U+(1/b)f(s+hU)$, ВЕРНУТЬСЯ ОБРАТНО К
ШАГУ~\stp{1}. (хСЛИ~$a/b$ БЛИЗКО К~$1$, ЭТОТ ШАГ АЛГОРИТМА БУДЕТ
ИСПОЛЬЗОВАТЬСЯ НЕ СЛИШКОМ ЧАСТО.)

\st[тЫЧИСЛИТЬ~$X$.] єСТАНОВИТЬ~$X\asg s+hU$.
\algend

фЛЯ ДОКАЗАТЕЛЬСТВА ПРАВИЛЬНОСТИ АЛГОРИТМА ЗАМЕТИМ, ЧТО, КОГДА МЫ ПРИХОДИМ
К ШАГУ~L4, ТОЧКА~$(U, V)$---ЭТО СЛУЧАЙНАЯ
\picture{ЁИС. 11. юБЛАСТЬ "ПРИНЯТИЯ РЕЗУЛЬТАТА" В АЛГОРИТМЕ L.}
ТОЧКА В КВАДРАТЕ, ИЗОБРАЖЕННОМ НА РИС.~11, А ИМЕННО~$0\le U\le V \le U+(1/b)f(s+hU)$.

єСЛОВИЯ~(18) ГАРАНТИРУЮТ, ЧТО
$$
{a\over b}\le U+{1\over b}f(s+hU)\le 1.
$$
ЄЕПЕРЬ ВЕРОЯТНОСТЬ ТОГО, ЧТО~$X\le s+hx$ ДЛЯ~$0\le x \le 1$,
РАВНА ОТНЕШЕНИЮ ПЛОЩАДИ СЛЕВА ОТ ВЕРТИКАЛЬНОЙ ЛИНИИ~$U=x$ НА РИС.~11 КО
ВСЕЙ ПЛОЩАДИ, Т.~Е.\
$$
\int_0^x{1\over b}f(s+hu)\,du\bigg/ \int_0^1{1\over b}f(s+hu)\,du=\int_s^{s+hx}f(v)\,dv;
$$
ПОЭТОМУ $X$~ИМЕЕТ НУЖНОЕ РАСПРЕДЕЛЕНИЕ.

ўТОБЫ ИСПОЛЬЗОВАТЬ ЭТОТ АЛГОРИТМ, НАМ НЕОБХОДИМО ОПРЕДЕЛИТЬ~$a_j$, $b_j$,
$s_j$, $h$ ДЛЯ ПЛОТНОСТЕЙ ВЕРОЯТНОСТЕЙ~$f_{j+24}(x)$ (РИС.~9). эЕТРУДНО
ВИДЕТЬ, ЧТО ПРИ~$1\le j \le 12$
$$
\displaynarrow{
f_{j+24}(x)={1\over p_j+24}\sqrt{2\over\pi}(e^{-x^2/2}-e^{-(j/4)^2/2}), \rem{$s_j\le x \le s_j+h$;}\cr
h={1\over4}; s_j=(j-1)/4;\cr
p_{j+24}=\sqrt{2\over\pi}\int_{s_j}^{s_j+h}(e^{-t^2/2}-e^{-(j/4)^2/2})\,dt.\cr
}
\eqno(19)
$$
%% 137
ъРОМЕ ТОГО,
$$
\eqalignter{
 a_j&=f_{j+24}(s_j)                & \rem{ПРИ~$1\le j \le 4$,}\cr
 b_j&=f_{j+24}(s_j)                & \rem{ПРИ~$5\le j \le 12$;}\cr
 b_j&=-hf'_{j+24}(s_j+h)           & \rem{ПРИ~$1\le j \le 4$,}\cr
 a_j&=f_{j+24}(x_j)+(x_j-s_j)b_j/h & \rem{ПРИ~$5\le j \le 12$,}\cr
}
\eqno(20)
$$
ГДЕ~$x_j$---КОРЕНЬ УРАВНЕНИЯ~$f'_{j+24}(x_j)=-b_j/h$.

яОСЛЕДНЕЕ РАСПРЕДЕЛЕНИЕ~$F_{37}(x)$ ДОЛЖНО МОДЕЛИРОВАТЬСЯ ТОЛЬКО ОДИН РАЗ
ИЗ ЧЕТЫРЕХСОТ. юНО ИСПОЛЬЗУЕТСЯ ВСЕГДА, КОГДА ДОЛЖЕН
\picture{
 ЁИС.~12. рЛГОРИТМ "ПРЯМОУГОЛЬНИК-КЛИН-ХВОСТ" ДЛЯ ВЫРАБОТКИ НОРМАЛЬНО
 РАСПРЕДЕЛЕННЫХ СЛУЧАЙНЫХ ВЕЛИЧИН.
}
ПОЛУЧИТЬСЯ РЕЗУЛЬТАТ~$X\ge 3$. т ЭТОМ СЛУЧАЕ МОЖНО ПРИМЕНИТЬ МОДИФИКАЦИЮ
АЛГОРИТМА~P, КАК ПОКАЗАНО НИЖЕ (ШАГИ~ь8---ь9). яРЕДОСТАВЛЯЕМ ЧИТАТЕЛЮ
ВОЗМОЖНОСТЬ ДОКАЗАТЬ, ЧТО ПРИВЕДЕННЫЙ МЕТОД ТОЧЕН.

ЄЕПЕРЬ ПРИВОДИМ ПРОЦЕДУРУ ПОЛНОСТЬЮ.

\alg M.(ьЕТОД ьАРСАЛЬИ---ьАКЛАРЕНА ДЛЯ НОРМАЛЬНЫХ СЛУЧАЙНЫХ ВЕЛИЧИН.) т ЭТОМ
АЛГОРИТМЕ ИСПОЛЬЗУЮТСЯ НЕКОТОРЫЕ ВСПОМОГАТЕЛЬНЫЕ ТАБЛИЦЫ, УСТРОЕННЫЕ, КАК
ОБоЯСНЯЛОСЬ В ТЕКСТЕ (ПРИМЕРЫ ПРИВЕДЕНЫ В ТАБЛ.~1 И~2). рЛГОРИТМ
ПРИВОДИТСЯ ДЛЯ ДВОИЧНОЙ МАШИНЫ, ДЛЯ ДЕСЯТИЧНОЙ МАШИНЫ ОН СТРОИТСЯ АНАЛОГИЧНО.
%% 138
\htable{ЄАБЛИЦА 2}%
{яРИМЕРЫ ТАБЛИЦ, ИСПОЛЬЗУЕМЫХ В АЛГОРИТМЕ~M%
\note{1}{эА ПРАКТИКЕ ДАННЫЕ ДЛЯ ТАБЛИЦ~$P$, $Q$, $D$, $E$ СЛЕДУЕТ ДАВАТЬ С БОЛЬШЕЙ ТОЧНОСТЬЮ.}
}%
{\hfil$#$\bskip&\hfil\bskip$#$\bskip\hfil&&\hfil$#$&$#$\bskip\hfil\cr
 j &  S[j]     &  &P[j] &  & Q[j]&  &D[j]& & E[j] \cr
 1 &  0        & 0&.885 & 0&.881 & 0&.51 & 16 \cr
 2 &  1\over 4 & 0&.895 & 0&.885 & 0&.79 & 8\cr
 3 &  1\over 2 & 0&.910 & 0&.897 & 0&.90 & 5&.33\cr
 4 &  3\over 4 & 0&.929 & 0&.914 & 0&.98 & 4 \cr
 5 &  1        & 0&.945 & 0&.930 & 0&.99 & 3&.08 \cr
 6 &  5\over 4 & 0&.960 & 0&.947 & 0&.99 & 2&.44 \cr
 7 &  3\over 2 & 0&.971 & 0&.960 & 0&.98 & 2&.00 \cr
 8 &  7\over 4 & 0&.982 & 0&.974 & 0&.96 & 1&.67 \cr
 9 &  2        & 0&.987 & 0&.982 & 0&.95 & 1&.43 \cr
10 &  9\over 4 & 0&.991 & 0&.989 & 0&.93 & 1&.23 \cr
11 &  5\over 2 & 0&.994 & 0&.992 & 0&.94 & 1&.08 \cr
12 & 11\over 4 & 0&.997 & 0&.996 & 0&.94 & 0&.95 \cr
13 &  3        & 1&.000 \cr
}

\st[яОЛУЧИТЬ~$U$.] тЫРАБОТАТЬ СЛУЧАЙНОЕ ЧИСЛО~$U=.b_0b_1b_2\ldots{} b_t$.
(чДЕСЬ~$b$---БИТЫ В ДВОИЧНОМ ПРЕДСТАВЛЕНИИ~$U$. фЛЯ ХОРОШЕЙ ТОЧНОСТИ~$t$
ДОЛЖНО БЫТЬ НЕ МЕНЬШЕ~24.) єСТАНОВИТЬ~$\psi\asg b_0$. (яОЗЖЕ
$\psi$~ПОНАДОБИТСЯ ДЛЯ ОПРЕДЕЛЕНИЯ ЗНАКА РЕЗУЛЬТАТА.)

\st[сОЛЬШОЙ ПРЯМОУГОЛЬНИК?] хСЛИ~$b_1b_2b_3b_4<10$, ГДЕ
"$b_1b_2b_3b_4$"~ОБОЗНАЧАЕТ ДВОИЧНОЕ ЦЕЛОЕ ЧИСЛО~$8b_1+4b_2+2b_3+b_4$, УСТАНОВИТЬ
$$
X\asg A[b_1b_2b_3b_4]+.00b_5b_6\ldots{} b_t
$$
И ПЕРЕЙТИ К~\stp{10}. шНАЧЕ, ЕСЛИ~$b_1b_2b_3b_4b_5b_6<52$, УСТАНОВИТЬ
$$
X\asg B[b_1b_2b_3b_4b_5b_6]+.00b_7b_8\ldots{}b_t
$$
И ПЕРЕЙТИ К~\stp{10}. шНАЧЕ, ЕСЛИ~$b_1b_2b_3b_4b_5b_6b_7b_8<225$, УСТАНОВИТЬ
$$
X\asg C[b_1b_2b_3b_4b_5b_6b_7b_8]+.00b_9b_{10}\ldots{}b_t
$$
И ПЕРЕЙТИ К~\stp{10}.

\st[ъЛИН ИЛИ ХВОСТ?] эАЙТИ \emph{НАИМЕНЬШЕЕ} ЗНАЧЕНИЕ~$j$, $1\le j \le 13$,
 ДЛЯ КОТОРОГО~$b_1b_2\ldots{}b_t<P[j]$. хСЛИ~$j=13$, ПЕРЕЙТИ К ШАГУ~\stp{8}.

\st[єЗКИЙ ПРЯМОУГОЛЬНИК?] хСЛИ~$.b_1b_2\ldots{}b_t<Q[j]$, ВЫРАБОТАТЬ
НОВОЕ СЛУЧАЙНОЕ ЧИСЛО~$U$, УСТАНОВИТЬ~$X\asg S[j]+{1\over 4}U$ И ПЕРЕЙТИ К~\stp{10}.

%% 139

\st[яОЛУЧИТЬ~$U\le V$.] тЫРАБОТАТЬ ДВА НОВЫХ СЛУЧАЙНЫХ ЧИСЛА~$U$, $V$;
ЕСЛИ~$U>V$, ПОМЕНЯТЬ ИХ МЕСТАМИ~$U\xchg V$. (ЄЕПЕРЬ ВЫПОЛНЯЕТСЯ
АЛГОРИТМ~L.) єСТАНОВИТЬ~$X\asg S[j]+{1\over4}U$.

\st[яРОСТОЙ СЛУЧАЙ?] хСЛИ~$V\le D[j]$, ПЕРЕЙТИ К~\stp{10}.

\st[хЩЕ ОДНА ПОПЫТКА?] хСЛИ~$V>U+E[j](e^{-(X^2-S[j+1]^2)/2}-1)$, ВЕРНУТЬСЯ
К ШАГУ~\stp{5}; В ПРОТИВНОМ СЛУЧАЕ ПЕРЕЙТИ К~\stp{10}. (¤ТОТ ШАГ
ВЫПОЛНЯЕТСЯ С МАЛОЙ ВЕРОЯТНОСТЬЮ.)

\st[яОЛУЧИТЬ~$U^2+V^2<1$.] тЫРАБОТАТЬ ДВА НОВЫХ СЛУЧАЙНЫХ ЧИСЛА~$U$, $V$.
єСТАНОВИТЬ~$W\asg U^2+V^2$. хСЛИ~$W\ge1$, ПОВТОРИТЬ ЭТОТ ШАГ.

\st[тЫЧИСЛИТЬ~$X\ge 3$.] єСТАНОВИТЬ~$T\asg\sqrt{(9-2\ln W)/W}$.
єСТАНОВИТЬ~$X\asg U\times T$. хСЛИ~$X>3$, ПЕРЕЙТИ К~\stp{10}; В ПРОТИВНОМ
СЛУЧАЕ УСТАНОВИТЬ~$X\asg V\times T$. хСЛИ~$X\ge3$, ПЕРЕЙТИ К~\stp{10};
ИНАЧЕ ВЕРНУТЬСЯ К ШАГУ~\stp{8}. (яОСЛЕДНЕЕ ПРОИСХОДИТ В ПОЛОВИНЕ ВСЕХ
СЛУЧАЕВ, КОГДА ВЫПОЛНЯЕТСЯ ДАННЫЙ ШАГ.)

\st[яРИСВОИТЬ ЗНАК.] хСЛИ~$\psi=1$, УСТАНОВИТЬ~$X\asg -X$.
\algend

тЕСЬ АЛГОРИТМ ЯВЛЯЕТ СОБОЙ ВЕСЬМА ПРИЯТНЫЙ ПРИМЕР МАТЕМАТИЧЕСКОЙ ТЕОРИИ,
ГУСТО СДОБРЕННОЙ ИЗОБРЕТАТЕЛЬНОСТЬЮ ПРОГРАММИСТА. ¤ТО ПРЕКРАСНАЯ
ИЛЛЮСТРАЦИЯ ИСКУССТВА ПРОГРАММИРОВАНИЯ.

ЄАБЛИЦЫ~$A$, $B$ И~$C$ УЖЕ БЫЛИ ОПИСАНЫ. юСТАЛЬНЫЕ ТАБЛИЦЫ, НЕОБХОДИМЫЕ
ДЛЯ АЛГОРИТМА~$M$, СТРОЯТСЯ СЛЕДУЮЩИМ ОБРАЗОМ;
$$
\eqalign{
S[j]&=(j-1)/4,  \rem{$1 \le j \le 13$}; \cr
P[j]&=p_1+p_2+\cdots+p_{12}+(p_{13}+p_{25})+\cdots+(p_{12+j}+p_{24+j}), \rem{$1\le j \le 12$; $P[13]=1$;}\cr
Q[j]&=P[j]-p_{24+j}, \rem{$1\le j \le 12$;} \cr
D[j]&=a_j/b_j, \rem{$1\le j \le 12$;}\cr
E[j]&=\sqrt{2\over\pi} e^{-(j/4)^2/2}/b_jp_{j+24}, \rem{$1\le j \le 12$.}\cr
}
\eqno(21)
$$
[тЕЛИЧИНЫ~$a_j$, $b_j$, $p_{j+24}$ ОПРЕДЕЛЯЮТСЯ В~(19) И~(20).]

т ТАБЛ.~2 ЗНАЧЕНИЯ ПРИВОДЯТСЯ ТОЛЬКО С НЕСКОЛЬКИМИ ЗНАЧАЩИМИ ЦИФРАМИ, НО
В НАСТОЯЩЕЙ ПРОГРАММЕ ОНИ ДОЛЖНЫ ИМЕТЬ ТОЧНОСТЬ, СООТВЕТСТВУЮЩУЮ ПОЛНОМУ
МАШИННОМУ СЛОВУ. фЛЯ ВСЕХ ВСПОМОГАТЕЛЬНЫХ ТАБЛИЦ АЛГОРИТМА~M ТРЕБУЕТСЯ 101~МАШИННОЕ СЛОВО.

¤ТОТ МЕТОД ЧРЕЗВЫЧАЙНО БЫСТРЫЙ, ТАК КАК 88\%~ВРЕМЕНИ РАБОТАЮТ ТОЛЬКО
ШАГИ~M1, M2 И~M10, ОСТАЛЬНЫЕ ЖЕ ШАГИ ТАКЖЕ НЕ СЛИШКОМ МЕДЛЕННЫЕ. эА РИС.~9
МЫ РАЗДЕЛИЛИ ИНТЕРВАЛ ОТ~$0$ ДО~$3$ НА 12~ЧАСТЕЙ. хСЛИ БЫ МЫ РАЗДЕЛИЛИ ЕГО
НА БОЛЬШЕЕ ЧИСЛО ЧАСТЕЙ, СКАЖЕМ~48, ПОНАДОБИЛИСЬ БЫ БОЛЕЕ ДЛИННЫЕ ТАБЛИЦЫ,
НО ЗАТО ПРИ  ЭТОМ В 97\%~СЛУЧАЕВ ВЫЧИСЛЕНИЯ ОГРАНИЧИВАЛИСЬ ТОЛЬКО
%%140
ШАГАМИ~M1, M2, M10. яОЛНЫЕ ТАБЛИЦЫ КАК ДЛЯ ДВОИЧНЫХ, ТАК И ДЛЯ ДЕСЯТИЧНЫХ
МАШИН ПРИВОДЯТСЯ В СТАТЬЕ ьАРСАЛЬИ, ьАКЛАРЕНА И сРЭЯ ({\sl CACM,\/} {\bf 7}
(1964), 4--10). ЄАМ ДЛЯ ЭКОНОМИИ ПАМЯТИ РАЗРАБОТАН ДОПОЛНИТЕЛЬНЫЙ ПРИЕМ,
СВЯЗАННЫЙ С ПЕРЕКРЫВАНИЕМ ЧАСТЕЙ ТАБЛИЦ~$A$, $B$, $C$ И~$S$.)

{\sl (3)~ьЕТОД ЄЕЙЧРОЕВА.\/} эОРМАЛЬНЫЕ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ МОЖНО ПОЛУЧИТЬ
ТАКЖЕ СЛЕДУЮЩИМ ОБРАЗОМ. тЫРАБОТАЕМ 12~НЕЗАВИСИМЫХ СЛУЧАЙНЫХ ЧИСЕЛ~$U_1$,
$U_2$,~\dots, $U_{12}$, РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ.
яОЛОЖИМ~$R=(U_1+U_2+\cdots+U_{12}-6)/4$. тЫЧИСЛИМ
$$
X=((((a_9R^2+a_7)R^2+a_5)R^2+a_3)R^2+a_1)R,
\eqno (22)
$$
ГДЕ
$$
\displaynarrow{
 a_1=3.94984\,6138, \quad a_3=0.25240\,8784,\cr
 a_5=0.07654\,2912,  \quad a_7=0.00835\,5968,\quad a_9=0.02989\,9776.\cr
}
\eqno (23)
$$
ЄАКОЕ~$X$ БУДЕТ ХОРОШИМ ПРИБЛИЖЕНИЕМ ДЛЯ НОРМАЛЬНОЙ СЛУЧАЙНОЙ ВЕЛИЧИНЫ.
эИКОГДА НЕ ПОЛУЧАЕТСЯ СЛИШКОМ БОЛЬШИХ ЗНАЧЕНИЙ~$X$, НО С ВЕРОЯТНОСТЬЮ,
МЕНЬШЕЙ~$1/50000$, ВЫРАБАТЫВАЮТСЯ ЗНАЧЕНИЯ, ПРЕВЫШАЮЩИЕ ТЕ, ГДЕ МЕТОД
РАБОТАЕТ ПРАВИЛЬНО.

ьЕТОД ОСНОВАН НА ТОМ, ЧТО $R$~ИМЕЕТ \emph{ПРИБЛИЗИТЕЛЬНО} НОРМАЛЬНОЕ
РАСПРЕДЕЛЕНИЕ СО СРЕДНИМ ЗНАЧЕНИЕМ НУЛЬ И СТАНДАРТНЫМ
ОТКЛОНЕНИЕМ~${1\over4}$. яУСТЬ~$F_1(x)$---ИСТИННОЕ РАСПРЕДЕЛЕНИЕ ДЛЯ~$R$,
a~$F(x)$---НОРМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ, ОПРЕДЕЛЯЕМОЕ ФОРМУЛОЙ~(10).
яОЛОЖИМ~$X=F^{-1}(F_1(R))$; ТАК КАК~$F_1(R)$---РАВНОМЕРНО РАСПРЕДЕЛЕННАЯ
СЛУЧАЙНАЯ ВЕЛИЧИНА, $X$~БУДЕТ РАСПРЕДЕЛЕНА НОРМАЛЬНО. ЇОРМУЛА~(22)
ПРЕДСТАВЛЯЕТ ПРИБЛИЖЕНИЕ ФУНКЦИИ~$F^{-1}(F_1(R))$ ПОЛИНОМОМ В
ПРОМЕЖУТКЕ~$\abs{R}\le 1$.

{\sl (4)~ёРАВНЕНИЕ МЕТОДОВ.\/} ьЫ ПРИВЕЛИ ТРИ МЕТОДА ДЛЯ
ВЫРАБОТКИ НОРМАЛЬНЫХ СЛУЧАЙНЫХ ВЕЛИЧИН. ьЕТОД ПОЛЯРНЫХ КООРДИНАТ ДОВОЛЬНО
МЕДЛЕННЫЙ, НО ОБЕСПЕЧИВАЕТ АБСОЛЮТНУЮ ТОЧНОСТЬ. хГО ЛЕГКО
ЗАПРОГРАММИРОВАТЬ, ЕСЛИ ЕСТЬ СТАНДАРТНЫЕ ПРОГРАММЫ ДЛЯ ВЫЧИСЛЕНИЯ
КВАДРАТНОГО КОРНЯ И ЛОГАРИФМА. ьЕТОД ЄЕЙЧРОЕВА ТАКЖЕ ЛЕГКО ПРОГРАММИРУЕТСЯ,
ДЛЯ НЕГО НЕ НУЖНО ДРУГИХ ПОДПРОГРАММ. яОЭТОМУ ОН НУЖДАЕТСЯ В МЕНЬШЕЙ
ПАМЯТИ. ьЕТОД ЭТОТ ПРИБЛИЖЕННЫЙ, ХОТЯ ДЛЯ БОЛЬШИНСТВА ПРИЛОЖЕНИЙ ДАЕТ
ДОСТАТОЧНУЮ ТОЧНОСТЬ (ОШИБКА НЕ ПРЕВЫШАЕТ~$2\times 10^{-4}$
ПРИ~$\abs{R}\le 1$). ьЕТОД ьАРСАЛЬИ ЗНАЧИТЕЛЬНО БЫСТРЕЕ ЛЮБЫХ ДРУГИХ И
ПОДОБНО МЕТОДУ ПОЛЯРНЫХ КООРДИНАТ ИМЕЕТ АБСОЛЮТНУЮ ТОЧНОСТЬ. фЛЯ НЕГО
НЕОБХОДИМЫ ПОДПРОГРАММЫ КВАДРАТНОГО КОРНЯ, ЛОГАРИФМА И ПОКАЗАТЕЛЬНОЙ
ФУНКЦИИ И, КРОМЕ ТОГО, ВСПОМОГАТЕЛЬНЫЕ ТАБЛИЦЫ ДЛЯ 100--400~КОНСТАНТ.
яОЭТОМУ ТРЕБОВАНИЯ К ПАМЯТИ ДОВОЛЬНО ВЫСОКИЕ. юДНАКО НА БОЛЬШИХ МАШИНАХ
СКОРОСТЬ МЕТОДА
%% 141
\bye