\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
