\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