\input style
\chapno=3\subchno=3\chapnotrue
S6--S9), RAVNO LISHX~$\floor{{1\over 2}\prod (2c_j+1)}$,  A
NE~$\prod(2c_j+1)$, TAK KAK ALGORITM IMEET DELO TOLXKO S TAKIMI VEKTORAMI,
U KOTORYH PERVYJ NENULEVOJ |LEMENT POLOZHITELEN.)

rASSMOTRIM KRATKO PRIMER ALGORITMA~$S$ V DEJSTVII, KOGDA $a=3141592621$,
$m=10^{10}$, $n=3$. v TABL.~2 V PERVYH STROKAH PREDSTAVLENY~$Q$ I~$R$,
PRIGOTOVLENNYE NA SHAGE~S1. iSSLEDOVANIE |TIH MATRIC SREDSTVAMI LEMMY~A
POTREBUET PROVERKI $10^{29}$~SLUCHAEV, CHTO VYHODIT ZA VSYAKIE GRANICY.
pOSLE SHESTI ITERACIJ NA SHAGAH~S2--S5 |LEMENTY MATRIC~$Q$ I~$R$ STALI
NAMNOGO MENXSHE (SM.~STROKU~7 TABL.~2), I, SOGLASNO LEMME~A, TEPERX V
|TOJ NOVOJ ZADACHE~$\abs{x_1}\le 3$, $\abs{x_2}\le 3$, $\abs{x_3}\le 14$.
dALXNEJSHEE UMENXSHENIE S POMOSHCHXYU LEMMY~B PRIVODIT NAS K STROKE~8: V
MATRICE~$Q$ (STROKA~7) PRIBAVLYAEM STOLBEC~3 K STOLBCU~2, STROKU~3 K
STROKE~2, ZATEM 3~RAZA VYCHITAEM STOLBEC~3 IZ STOLBCA~1 I TAKZHE TRI RAZA
STROKU~3 IZ STROKI~1. v MATRICE~$R$ VYCHITAEM STOLBEC~2 IZ STOLBCA~3, ZATEM
VYCHITAEM STROKU~2 IZ STROKI~3, POTOM PRIBAVLYAEM TRI RAZA STOLBEC~1 K
STOLBCU~3, A STROKU~1 SNOVA TRI
{\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{tABLICA 2}
{pRIMER ALGORITMA S}
{$#$\bskip&$\displaystyle#$\bskip&&\hfil$\displaystyle#$\bskip\cr
\noalign{
\hrule
\embedpar{sTROKA \hfil mATRICA~$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{sTROKA \hfil mATRICA~$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
RAZA PRIBAVLYAEM K STROKE~3. eTO UMENXSHAET~$Q$ I~$R$, TAK CHTO, SOGLASNO
LEMME~A, TEPERX OSTALOSX PROVERITX ZNACHENIE~$\abs{x_1}\le 3$,
$\abs{x_2}\le 3$, $\abs{x_3}\le 1$, CHTOBY NAJTI ABSOLYUTNYJ MINIMUM. v
DEJSTVIE PRIVODITSYA METOD PEREBORA NA SHAGAH~S6--S9, KOTORYJ NAHODIT
KOMBINACIYU~$x_1=1$, $x_2=-1$, $x_3=0$, REALIZUYUSHCHUYU MINIMALXNOE
ZNACHENIE~$x^TQx=1034718$. eTI VYCHISLENIYA MOZHNO BYLO BY SDELATX S POMOSHCHXYU
NASTOLXNOJ VYCHISLITELXNOJ MASHINKI ZA NESKOLXKO CHASOV, HOTYA V NACHALE ZADACHA
VYGLYADELA VESXMA VNUSHITELXNO.

sPEKTRALXNYJ TEST VPERVYE POYAVILSYA V STATXE r.~kOV|YU I r.~mAKFERSONA
(R.~R.~Coveyou, R.~D.~MacPherson, Fourier Analysis of Uniform Random
Number Generators, {\sl JACM,\/} {\bf 14} (1967), 100--119). v |TOJ STATXE
OPISAN ALGORITM, V SUSHCHNOSTI PODOBNYJ ALGORITMU~$S$, ZA ISKLYUCHENIEM
NESKOLXKO OTLICHNOGO PRAVILA PREOBRAZOVANIYA NA SHAGE~S4.

\excercises
\ex[m20] vYVEDITE SOOTNOSHENIE~(2) IZ~(1).

\ex[m20] pREDPOLAGAYA, CHTO~$0\le s_1$~\dots, $s_n<m$, VYVEDITE
SOOTNOSHENIE~(1) IZ~(2).

\ex[m22] (a)~pUSTX $F(t)$~OPREDELENA DLYA CELYH ZNACHENIJ~$t$, $0\le t < m$,
 I OBLASTX EE OPREDELENIYA RASSHIRENA NA VSE CELYE CHISLA S POMOSHCHXYU
FORMULY~$F(t)=F(t\bmod m)$. pUSTX~$f(s)$---PREOBRAZOVANIE fURXE
FUNKCII~$F(t)$, OPREDELENNOE V SOOTVETSTVII S~(1) DLYA~$n=1$. nAJDITE
PREOBRAZOVANIE fURXE FUNKCII~$F(t+1)$, VYRAZIV EGO CHEREZ~$f(s)$.

(b)~nAJDITE PREOBRAZOVANIE fURXE SUMMY~$\sum_{0\le k < m} F(k)G(t-k)$,
VYRAZIV EGO CHEREZ PREOBRAZOVANIYA fURXE~$F$ I~$G$.

\rex[m22] pUSTX~$X_0$, $X_1$, $X_2$,~\dots---PERIODICHESKAYA
POSLEDOVATELXNOSTX CELYH CHISEL S PERIODOM~$m$, TAKAYA, CHTO~$0\le X_k<m$, I
PUSTX~$f(s_1, s_2)$---FUNKCIYA, OPREDELENNAYA FORMULOJ~(4). vYRAZITE
CHEREZ~$f$ VEROYATNOSTX TOGO, CHTO~$X_{k+1}<X_k$ V |TOJ POSLEDOVATELXNOSTI.
(uPROSTITE NASKOLXKO VOZMOZHNO VASH OTVET, CHTOBY YAVNO BYLI PREDSTAVLENY
KO|FFICIENTY PRI KAZHDOM CHASTNOM ZNACHENII~$f$.)

\ex[m23] pUSTX~$X_0$, $X_1$, $X_2$,~\dots---PERIODICHESKAYA POSLEDOVATELXNOSTX
CELYH CHISEL S DLINOJ PERIODA~$m$ I TAKAYA, CHTO~$0\le X_k<m$. vYRAZITE CHEREZ
FUNKCIYU~$F$, OPREDELYAEMUYU SOOTNOSHENIEM~(3), I FUNKCIYU~$f$, OPREDELYAEMUYU
SOOTNOSHENIEM~(4), SUMMU~$\sum_{0\le k <m} X_k X_{k+1}$, PREDSTAVLYAYUSHCHUYU
VAZHNUYU CHASTX FORMULY DLYA KO|FFICIENTA POSLEDOVATELXNOJ KORRELYACII (FORMULA~(3.3.2-23)).

\rex[m28] dOKAZHITE TEOREMU~3.3.3P, ISPOLXZUYA~(8) I REZULXTAT UPR.~4.

\ex[m40] vYVEDITE FORMULY, POZVOLYAYUSHCHIE DOSTATOCHNO |FFEKTIVNO VYCHISLYATX
TOCHNOE ZNACHENIE VEROYATNOSTI TOGO, CHTO~$X_{k+2}<X_{k+1}<X_k$ DLYA
LINEJNOJ KONGRU|NTNOJ POSLEDOVATELXNOSTI S MAKSIMALXNYM PERIODOM.
[\emph{uKAZANIE.} s POMOSHCHXYU METODOV, ISPOLXZUEMYH V UPR.~6, I REZULXTATA
UPR.~3.3.3-20 |TA VELICHINA MOZHET BYTX YAVNO VYRAZHENA CHEREZ OBOBSHCHENNYE
SUMMY dEDEKINDA. zAMETXTE, CHTO ZADACHA SILXNO USLOZHNYAETSYA, ESLI NE
POLXZOVATXSYA PREOBRAZOVANIEM fURXE.]

\ex[M22] nAJDITE PRIEMLEMO PROSTOE VYRAZHENIE SUMMY~$\sum_{0\le k < m} X_k X_{k+1}$
DLYA LINEJNOJ KONGRU|NTNOJ POSLEDOVATELXNOSTI S MAKSIMALXNYM
PERIODOM, ISPOLXZUYA REZULXTAT UPR.~5, A TAKZHE FORMULU~(8).

\ex[vm30] (sh.~eRMIT.) zADANA $n\times n\hbox{-MATRICA}$~$A$. dOKAZHITE, CHTO
SUSHCHESTVUET NENULEVOJ CELOCHISLENNYJ VEKTOR~$x$, TAKOJ, CHTO~$Ax\cdot Ax \le
\left({4\over 3}\right)^{(n-1)/2} (\det A)^{2/n}$.
%% 123
[\emph{uKAZANIE.} sNACHALA POKAZATX, CHTO DLYA VSEH~$\varepsilon>0$
SUSHCHESTVUET CELOCHISLENNAYA MATRICA~$U$, DETERMINANT KOTOROJ RAVEN~$1$, I
PROIZVEDENIE~$AUx\cdot AUx$ NAHODITSYA V $\varepsilon\hbox{-OKRESTNOSTI}$
MAKSIMALXNOJ NIZHNEJ GRANICY EE ZNACHENIJ
PRI~$(x_1, x_2,~\ldots, x_n)=(1, 0, 0,~\ldots, 0)$. zATEM DOKAZATX OBSHCHEE
UTVERZHDENIE INDUKCIEJ PO~$n$, ZAPISAV~$Ax\cdot Ax$ V
VIDE~$\alpha(x_1+\beta_2x_2+\cdots+\beta_n x_n)^2+g(x_2,~\ldots, x_n)$,
GDE $g$~SOOTVETSTVUET $(n-1)\times(n-1)\hbox{-MATRICE}$~$A'$.]

\ex[vm30] (kOV|YU I mAKFERSON). pUSTX~$X_0$, $X_1$, $X_2$,
~\dots---POSLEDOVATELXNOSTX CELYH CHISEL, LEZHASHCHIH V PREDELAH~$0\le X_k <m$;
EJ SOOTVETSTVUET PREOBRAZOVANIE fURXE~$f(s_1,~\dots, s_n)$, OPREDELENNOE
FORMULOJ~(4). pUSTX~$U_k=X_k/m$, a~$V_0$, $V_1$, $V_2$,
~\dots---POSLEDOVATELXNOSTX NEZAVISIMYH ISTINNO SLUCHAJNYH DEJSTVITELXNYH
CHISEL, RAVNOMERNO RASPREDELENNYH MEZHDU~$0$ I~$1$;
$\lambda$---CHISLO, MENXSHEE~$1$, I~$W_k=(U_k+\lambda V_k) \bmod 1$.
(tEPERX~$W_k$---|TO SLUCHAJNYM OBRAZOM "RAZMAZANNYE" V PREDELAH~$\lambda$
CHLENY POSLEDOVATELXNOSTI~$U_k$.) oPREDELIM KO|FFICIENTY fURXE LYUBOJ
POSLEDOVATELXNOSTI DEJSTVITELXNYH CHISEL MEZHDU~$0$ I~$1$ KAK
$$
\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})).
$$
vYRAZITE KO|FFICIENTY fURXE POSLEDOVATELXNOSTI~$\<W_k>$ CHEREZ
KO|FFICIENTY fURXE POSLEDOVATELXNOSTI~$\<X_k>$.

\ex[m10] uRAVNENIE~(8) POKAZYVAET, CHTO ZNACHENIE~$c$ V LINEJNOJ
KONGRU|NTNOJ POSLEDOVATELXNOSTI S MAKSIMALXNYM PERIODOM NE VLIYAET NA
KO|FFICIENTY fURXE, A IZMENYAET LISHX "ARGUMENT" KOMPLEKSNOGO CHISLA~$f(s_1,
~\dots, s_n)$. dRUGIMI SLOVAMI, ABSOLYUTNOE ZNACHENIE~$f(s_1,~\ldots, s_n)$
NE ZAVISIT OT~$c$. nO MOZHNO LI VYBRATX~$c$ TAK, CHTOBY NESLUCHAJNYJ |FFEKT
ODNOJ VOLNY~$f(s_1,~\dots, s_n)$ UNICHTOZHALSYA BY "PROTIVOPOLOZHNYM" |FFEKTOM
DRUGOJ VOLNY~$f(s'_1,~\ldots, s'_n)$?

\ex[vm23] dOKAZHITE, NE ISPOLXZUYA GEOMETRICHESKIH ARGUMENTOV, CHTO LYUBOE
RESHENIE "PROBLEMY~(b)", SFORMULIROVANNOJ V PODPUNKTE~C TEKSTA, DOLZHNO BYTX
ODNOVREMENNO RESHENIEM SISTEMY URAVNENIJ~(28).

\ex[vm30] v TEKSTE OSTALSYA V TENI DOVOLXNO VAZHNYJ VOPROS: BYLO SDELANO
MOLCHALIVOE PREDPOLOZHENIE, CHTO, ESLI~$A$---PROIZVOLXNAYA NEVYROZHDENNAYA MATRICA
DEJSTVITELXNYH CHISEL, FUNKCIYA~(18) \emph{IMEET} MINIMUM, KOTORYJ
\emph{DOSTIGAETSYA} NA NEKOTOROM CELOCHISLENNOM VEKTORE~$x$.
\medskip
\item{(a)} dOKAZHITE, CHTO NAIBOLXSHAYA NIZHNYAYA GRANICA VELICHINY~(18),
VZYATAYA PO VSEM NENULEVYM CELOCHISLENNYM VEKTORAM~$x$, DOSTIGAETSYA PRI
NEKOTOROM~$x$, ESLI~$A$---NEVYROZHDENNAYA MATRICA.

\item{(b)}~pOKAZHITE, CHTO, ESLI~$A$---VYROZHDENNAYA MATRICA, TAKOGO
NENULEVOGO CELOCHISLENNOGO VEKTORA, NA KOTOROM DOSTIGAETSYA NAIBOLXSHAYA
NIZHNYAYA GRANICA~(18), MOZHET NE SUSHCHESTVOVATX.

\rex[24] vYPOLNITE VRUCHNUYU ALGORITM~S DLYA~$m=100$, $a=41$, $n=3$.
zAMENITE KONSTANTU~"$1000$" NA SHAGE~S3 CHISLOM~"$3$".

\ex[m18] chTO PROIZOJDET, ESLI OPERACIYU "$k\asg n$" V KONCE
SHAGA~S1 ZAMENITX NA~"$\asg 1$"?

\ex[m25] nE ISKLYUCHENO (HOTYA |TOGO ESHCHE NE NABLYUDALOSX), CHTO
ALGORITM~S MOZHET ZACIKLITXSYA, POVTORYAYA BESKONECHNOE CHISLO RAZ SHAGI~S2--S5.
pOKAZHITE, CHTO |TO MOZHET PROIZOJTI TOGDA I TOLXKO TOGDA, KOGDA PRI
POSLEDOVATELXNOM VYPOLNENII $n$~RAZ SHAGA~S4 NE PROISHODIT PREOBRAZOVANIJ
(T.~E.\ NET OPERACIJ~|TRANS|).

\rex[m28] mODIFICIRUJTE ALGORITM~S TAK, CHTOBY KROME VYCHISLENIYA~$q$ V NEM
OPREDELYALSYA BY NABOR CELYH CHISEL~$s_1$,~\dots, $s_n$,
UDOVLETVORYAYUSHCHIH~(11) PRI~$s_1^2+\cdots+s_n^2=q$. [\emph{uKAZANIE.}
aLGORITM~S SOHRANYAET TOLXKO ZNACHENIYA~$Q$ I~$R$ IZ~(19), NO NE~$A$ I~$B$.
eSLI SOHRANITX ZNACHENIYA~$A$ I/ILI~$B$ PRI VYPOLNENII ALGORITMA,
PO-VIDIMOMU, NE SLISHKOM TRUDNO BUDET POLUCHITX ZNACHENIYA~$s_1$,~\dots, $s_n$.]

\ex[m25] nAJDITE $3\times 3\hbox{-MATRICU}$~$A$, TAKUYU, CHTO ESLI~$Q=A^TA$
I~$R=Q^{-1}$, TO SHAGI~S2--S5 ALGORITMA~S NIKOGDA NE ZAKONCHATSYA PEREHODOM K
SHAGU~S6
%% 124
(TAK CHTO VYCHISLENIYA NIKOGDA NE PREKRATYATSYA). [\emph{uKAZANIE.} rASSMOTRETX
"KOMBINATORNYE MATRICY", T.~E.\ MATRICY, |LEMENTY KOTORYH IMEYUT
VID~$a+b\delta_{ij}$; SR.~S~UPR.~1.2.3-39.]

\ex[m20] pOKAZHITE, CHTO POSLEDOVATELXNOSTX fIBONACHCHI${}\bmod m$
SLUZHIT PLOHIM ISTOCHNIKOM SLUCHAJNYH CHISEL, UBEDIVSHISX, CHTO SOOTVETSTVUYUSHCHAYA
FUNKCIYA~$f(s_1, s_2, s_3)$, OPREDELENNAYA V~(4), IMEET BOLXSHIE
NIZKOCHASTOTNYE KOMPONENTY.

\rex[m24] vYCHISLITE KO|FFICIENTY fURXE~$f(s_1,~\dots, s_n)$ DLYA
LINEJNOJ KONGRU|NTNOJ POSLEDOVATELXNOSTI, OPREDELENNOJ VELICHINAMI~$X_0=1$,
$c=0$, $m=2^e\ge 8$ I~$a \bmod 8=5$. oBSUDITE, KAK OBOBSHCHITX SPEKTRALXNYJ
TEST DLYA |TOGO TIPA DATCHIKOV SLUCHAJNYH CHISEL (OPREDELENNYJ V TEKSTE TOLXKO
DLYA LINEJNYH KONGRU|NTNYH POSLEDOVATELXNOSTEJ S \emph{MAKSIMALXNYM}
PERIODOM, TOGDA KAK U OPREDELENNOJ ZDESX POSLEDOVATELXNOSTI DLINA PERIODA RAVNA~$m/4$).

\ex[m25] pRODELAJTE PREDYDUSHCHEE UPRAZHNENIE, SCHITAYA, CHTO~$a\bmod 8=3$.

\rex[m30] pOSTROJTE ALGORITM, PODOBNYJ ALGORITMU~S, ZA ISKLYUCHENIEM TOGO,
CHTO V NEM ISPOLXZUETSYA PREOBRAZOVANIE~$U$, DLYA KOTOROGO VSE
NENULEVYE NEDIAGONALXNYE |LEMENTY NAHODYATSYA V \emph{STOLBCE}~$k$, A NE V
\emph{STROKE}~$k$, KAK V~(25). sRAVNITE |TOT METOD S ALGORITMOM~S.
pOKAZHITE, CHTO V |TOM ALGORITME VELICHINA~$\prod (2c_j+1)$  V SHAGE~S3
NIKOGDA NE UVELICHIVAETSYA OT ODNOJ ITERACII K DRUGOJ.

\ex[m50] nESMOTRYA NA TO CHTO V PRIMERE IZ UPR.~18 OSNOVNOJ CIKL
ALGORITMA~S VYNUZHDEN BESKONECHNO POVTORYATXSYA, DLYA "DVOJSTVENNOGO"
ALGORITMA IZ UPR.~22 TOT ZHE PRIMER NE PREDSTAVLYAET NIKAKOJ PROBLEMY. dLYA
UDOBSTVA BUDEM NAZYVATX POSLEDNIJ METOD ALGORITMOM~$S'$. tAK KAK
ALGORITM~$S'$ V SUSHCHNOSTI YAVLYAETSYA ALGORITMOM~S, V KOTOROM POMENYALISX
ROLYAMI MATRICY~$Q$ I~$R$, TAKZHE SUSHCHESTVUYUT MATRICY, ZASTAVLYAYUSHCHIE
ZACIKLIVATXSYA I |TOT ALGORITM. oTSYUDA VYTEKAET IDEYA KOMBINACII DVUH
METODOV. nAPRIMER, MY MOZHEM ISPOLXZOVATX ALGORITM~S, POKA ON NE
ZASTRYANET, ZATEM PEREKLYUCHITXSYA NA ALGORITM~$S'$ DO TEH POR, POKA
\emph{|TOT} NE ZASTRYANET, VERNUTXSYA ZATEM SNOVA K ALGORITMU~S I T. D.

pOLXZUYASX TAKIM KOMBINIROVANNYM ALGORITMOM I IGNORIRUYA VETVLENIE
NA SHAGE~S3, MY MOZHEM PRI REALIZACII VYCHISLITELXNOJ PROCEDURY OKAZATXSYA V
ODNOJ IZ DVUH SITUACIJ: (a)~USTANAVLIVAETSYA CIKL, V KOTOROM, KAZHDYJ
IZ ALGORITMOV~S I~$S'$ NEKOTORYM OBRAZOM POPEREMENNO PREOBRAZUYUT~$Q$ I~$R$,
 TAK CHTO VYCHISLENIYA NIKOGDA NE SMOGUT PREKRATITXSYA, ILI (b)~MY POLUCHAEM
MATRICY~$Q$ I~$R$, NA KOTORYE NE VLIYAYUT NI ALGORITM~S, NI ALGORITM~$S'$.

eTI NABLYUDENIYA, ESTESTVENNO, PRIVODYAT K POSTANOVKE SLEDUYUSHCHIH TREH
VOPROSOV, NA KOTORYE DOLZHEN BYTX DAN OTVET, ESLI NAM NUZHNO IMETX
POLNOSTXYU UDOVLETVORITELXNOE RESHENIE VYCHISLITELXNOJ PROBLEMY,
SFORMULIROVANNOJ V |TOM RAZDELE. mOZHET LI REALIZOVATXSYA SLUCHAJ~(a)? kAK
DOLGO MOZHNO ISKATX KONSTANTY~$\prod (2c_j+1)$ NA SHAGE~S3 V SLUCHAE~(b)?
sUSHCHESTVUET LI OBSHCHAYA PROCEDURA
VYCHISLENIYA~$\min\{\, x^TQx \mid \hbox{CELYE~$x\ne 0$}\,\}$ DLYA POLOZHITELXNO
OPREDELENNOJ MATRICY~$Q$, KOTORAYA BYLA BY LUCHSHE, CHEM TOLXKO CHTO OPISANNAYA
KOMBINACIYA ALGORITMOV~$S$ I~$S'$?

\emph{zAMECHANIE.} vTOROJ IZ POSTAVLENNYH VYSHE VOPROSOV MOZHNO SVESTI K
SLEDUYUSHCHEMU: \emph{pUSTX~$Q$---SIMMETRICHNAYA POLOZHITELXNO OPREDELENNAYA
$n\times n\hbox{-MATRICA}$ DEJSTVITELXNYH CHISEL, U KOTOROJ DIAGONALXNYE
|LEMENTY RAVNY~$1$, A~$\abs{q_{ij}}\le 1/2$ DLYA~$i\ne j$. pUSTX~$R=Q^{-1}$,
a~$\abs{r_{ij}}\le (1/2) r_{jj}$ DLYA~$i\ne j$. kAK. VELIKO MOZHET BYTX PRI
|TIH USLOVIYAH CHISLO~$r_{11}$?} dO SIH POR NE VSTRECHALISX PODOBNYE MATRICY,
DLYA KOTORYH~$r_{11}\ge 2$. eSLI PRINYATX VSE NEDIAGONALXNYE
|LEMENTY MATRICY~$Q$ RAVNYMI~$-1/n$, TO MOZHNO NAJTI, CHTO~$r_{11}=2n/(n+1)$.
eTOT PRIMER POKAZYVAET, CHTO NIKOGDA NELXZYA PREDPOLAGATX, CHTO KONSTANTA NA
SHAGE~S3 PRIMET ZNACHENIE, MENXSHEE~$3^n$, DLYA PROIZVOLXNOJ POLOZHITELXNO
OPREDELENNOJ MATRICY, DAZHE V SLUCHAE KOMBINACII ALGORITMOV~S I~$S'$. v
PRIMERE DOSTIGAETSYA~$\max r_{11}$ DLYA~$n=2$, NO NE DLYA~$n=3$.

\ex[m20] sRAVNITE PREOBRAZOVANIE fURXE~$f(s_1,~\ldots, s_n)$, ZADANNOE
FORMULOJ~(1), S \emph{PROIZVODSHCEJ FUNKCIEJ} OT $n$~PEREMENNYH
DLYA~$F(t_1,~\ldots, t_n)$, onpeDELENNOJ
%% 125
OBYCHNYM OBRAZOM:
$$
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[vm28] (r.~kOV|YU.) pROANALIZIRUJTE DVUMERNOE PREOBRAZOVANIE
fURXE~$f(s_1, s_2)$ DLYA POSLEDOVATELXNOSTI~(3.2.2-4) V MODIFICIROVANNOM
METODE SEREDINY KVADRATA. [\emph{uKAZANIE:} RASSMOTRETX DVOJNUYU SUMMU
DLYA~$\abs{f(s_1, s_2)}^2=f(s_1, s_2)\times f(-s_1, -s_2)$.]

\rex[m26] chEMU RAVNO ZNACHENIE TREHMERNOGO PREOBRAZOVANIYA fURXE~$f(s_1, s_2, s_3)$
POSLEDOVATELXNOSTI~(3.2.2-8), IMEYUSHCHEJ DLINU PERIODA~$p^2-1$, V SLUCHAE~$k=2$?

\rex[vm24] (dZH.~mARSALXYA.) pUSTX~$X_0$, $a$, $m$, $c$ POROZHDAYUT LINEJNUYU
KONGRU|NTNUYU POSLEDOVATELXNOSTX, I~$U_0$, $U_1$, $U_2$,~$\ldots=X_0/m$,
$X_1/m$, $X_2/m~\ldots\,$. pREDPOLOZHIV, CHTO~$s_1$, $s_2$,~\dots,
$s_n$---CELYE" CHISLA, UDOVLETVORYAYUSHCHIE~(11), DOKAZHITE SLEDUYUSHCHIE UTVERZHDENIYA:
(a)~KAZHDYJ NABOR $n$~CHISEL $(U_k, U_{k+1},~\ldots, U_{k+n-1})$ OPREDELYAET
V $n\hbox{-MERNOM}$ PROSTRANSTVE TOCHKU, LEZHASHCHUYU NA ODNOJ IZ
GIPERPLOSKOSTEJ, ZADAVAEMYH URAVNENIEM
$$
s_1 x_1 + s_2 x_2 +\cdots + s_n x_n=N+(s(a)-s(1))c/(a-1)m,
$$
GDE~$N$---CELOE, A $s(a)$~OPREDELYAETSYA FORMULOJ~(7). (b)~rASSTOYANIE MEZHDU
SOSEDNIMI PLOSKOSTYAMI RAVNO~$1/\sqrt{s_1^2+\cdots+s_n^2}$. (c)~chISLO
TAKIH GIPERPLOSKOSTEJ, PERESEKAYUSHCHIH $n\hbox{-MERNYJ}$
KUB~$0\le x_1,~\ldots, x_n<1$, RAVNO~$\abs{s_1}+\cdots+\abs{s_n}-\delta$,
GDE~$\delta=1$, ESLI~$s_i s_j < 0$ DLYA NEKOTORYH~$i$, $j$, V PROTIVNOM
SLUCHAE~$\delta=0$.

\emph{zAMECHANIE.} pO SLOVAM gIVENSA, POSLEDOVATELXNYE SLUCHAJNYE VEKTORY,
VYRABATYVAEMYE LINEJNYMI KONGRU|NTNYMI METODAMI, "OSTAYUTSYA GLAVNYM
OBRAZOM V PLOSKOSTYAH". eTO UPRAZHNENIE UBEDITELXNO DEMONSTRIRUET NEUDOBSTVO
LINEJNYH KONGRU|NTNYH POSLEDOVATELXNOSTEJ DLYA PRIMENENIJ V METODE
mONTE-kARLO, ESLI TREBUETSYA VYSOKOE RAZRESHENIE. nAPRIMER, TREHMERNYE
VEKTORY~$(U_k, U_{k+1}, U_{k+2})$, VYRABATYVAEMYE DATCHIKOM~(14), VSE LEZHAT
V PARALLELXNYH PLOSKOSTYAH, OTSTOYASHCHIH DRUG OT DRUGA NA $1/\nu_3\approx 0.001$~EDINIC.

%% 126
\subchap{drugie vidy sluchajnyh velichin } % 3.4
mY UZHE ZNAEM, KAK S POMOSHCHXYU VYCHISLITELXNOJ MASHINY VYRABATYVATX
POSLEDOVATELXNOSTX CHISEL~$U_0$, $U_1$, $U_2$,~\dots, KOTORYE VEDUT SEBYA
TAK, KAK ESLI BY IH VYBIRALI SLUCHAJNO I NEZAVISIMO IZ MNOZHESTVA CHISEL,
RAVNOMERNO RASPREDELENNYH MEZHDU NULEM I EDINICEJ. dLYA PRAKTICHESKIH
PRIMENENIJ CHASTO BYVAYUT NUZHNY SLUCHAJNYE VELICHINY S DRUGIMI RASPREDELENIYAMI.
nAPRIMER, ESLI MY HOTIM SDELATX VYBOR MEZHDU $k$~VOZMOZHNYMI ALXTERNATIVAMI,
NAM MOGUT PONADOBITXSYA SLUCHAJNYE \emph{CELYE CHISLA} OT~$1$ DO~$k$. eSLI
DLYA NEKOTOROGO MODELIROVANIYA TREBUYUTSYA SLUCHAJNYE PROMEZHUTKI VREMENI MEZHDU
KAKIMI-TO NEZAVISIMYMI SOBYTIYAMI, POLXZUYUTSYA SLUCHAJNYMI VELICHINAMI S
"|KSPONENCIALXNYM RASPREDELENIEM". iNOGDA MY VOOBSHCHE NE NUZHDAEMSYA V
SLUCHAJNYH \emph{CHISLAH,} A INTERESUEMSYA SLUCHAJNYMI PERESTANOVKAMI
(RASSTANOVKOJ $n$~|LEMENTOV V SLUCHAJNOM PORYADKE) ILI SLUCHAJNYMI
SOCHETANIYAMI (T.~E.~SLUCHAJNYM VYBOROM $k$~|LEMENTOV IZ $n$~VOZMOZHNYH).

v PRINCIPE LYUBUYU IZ |TIH SLUCHAJNYH VELICHIN MOZHNO POLUCHITX S POMOSHCHXYU
SLUCHAJNYH RAVNOMERNO RASPREDELENNYH CHISEL~$U_0$, $U_1$, $U_2$,~\dots%
\note{1}{
nIZHE VEZDE, GDE GOVORITSYA PROSTO O SLUCHAJNYH CHISLAH,
PODRAZUMEVAYUTSYA SLUCHAJNYE CHISLA S RAVNOMERNYM RASPREDELENIEM V
INTERVALE~$(0, 1)$.---{\sl pRIM. PEREV.\/}}. dLYA |TOGO SUSHCHESTVUET RYAD VAZHNYH
PRIEMOV, |FFEKTIVNO ISPOLXZUEMYH PRI RABOTE NA VYCHISLITELXNYH MASHINAH,
iZUCHENIE |TIH PRIEMOV POZVOLYAET PONYATX, KAK MOZHNO PRIMENYATX SLUCHAJNYE
CHISLA V LYUBYH PRILOZHENIYAH METODA mONTE-kARLO.

mOZHNO DOPUSTITX, CHTO KOGDA-NIBUDX KTO-NIBUDX IZOBRETET DATCHIK,
VYRABATYVAYUSHCHIJ |TI DRUGIE SLUCHAJNYE VELICHINY \emph{NEPOSREDSTVENNO,} A
NE S POMOSHCHXYU SLUCHAJNYH CHISEL S RAVNOMERNYM RASPREDELENIEM. kROME SLUCHAYA
DATCHIKA "SLUCHAJNYH BITOV", OPISANNOGO V P.~3.2.2, DO SIH POR NE BYLO
DOKAZANO, CHTO KAKOJ-LIBO PODOBNYJ PRYAMOJ METOD MOZHET OKAZATXSYA BOLEE VYGODNYM.

v SLEDUYUSHCHEM RAZDELE BUDEM PREDPOLAGATX, CHTO~$U_0$, $U_1$,
$U_2$,~\dots---SLUCHAJNAYA POSLEDOVATELXNOSTX DEJSTVITELXNYH CHISEL, RAVNOMERNO
RASPREDELENNYH MEZHDU NULEM I EDINICEJ. bUKVOJ~$U$ BEZ INDEKSA BUDEM
OBOZNACHATX TEKUSHCHIJ |LEMENT |TOJ POSLEDOVATELXNOSTI. bUDEM SCHITATX, CHTO
NOVOE~$U$ VYRABATYVAETSYA NEZAVISIMO OT TOGO, PONADOBITSYA LI ONO NAM ILI
NET. oBYCHNO SLUCHAJNYE CHISLA PREDSTAVLYAYUTSYA SODERZHIMYM VSEGO SLOVA
VYCHISLITELXNOJ MASHINY,
%% 127
V PREDPOLOZHENII, CHTO DESYATICHNAYA TOCHKA RASPOLOZHENA SLEVA. kONECHNO, NA
SAMOM DELE CHISLO V MASHINE PREDSTAVLYAETSYA S OGRANICHENNOJ TOCHNOSTXYU. i
ESLI |TA TOCHNOSTX PO KAKOJ-LIBO PRICHINE OKAZHETSYA NEDOSTATOCHNOJ, VSEGDA
MOZHNO OB�EDINITX NESKOLXKO~$U$ VODNO CHISLO S BOLEE VYSOKOJ TOCHNOSTXYU.

\subsubchap{chISLOVYE RASPREDELENIYA}
v |TOM RAZDELE RASSKAZYVAETSYA O NAIBOLEE IZVESTNYH
METODAH POLUCHENIYA SLUCHAJNYH VELICHIN DLYA RAZLICHNYH VAZHNYH RASPREDELENIJ.
mNOGIE IZ |TIH METODOV PERVONACHALXNO BYLI PREDLOZHENY dZHONOM FON nEJMANOM V
NACHALE 50-H GODOV, A ZATEM POSTEPENNO ULUCHSHALISX DRUGIMI LYUDXMI, OSOBENNO
dZHORDZHEM mARSALXEJ.

\section{A.~sLUCHAJNYJ VYBOR IZ KONECHNOGO MNOZHESTVA}. pROSTEJSHIM I NAIBOLEE
OBSHCHIM TIPOM RASPREDELENIJ, NEOBHODIMYH DLYA PRAKTIKI, YAVLYAYUTSYA
RASPREDELENIYA \emph{CELOCHISLENNYH} SLUCHAJNYH VELICHIN. cELOE CHISLO OT~$0$
DO~$7$ MOZHNO IZVLECHX IZ 3~BITOV SLOVA~$U$ V DVOICHNOJ VYCHISLITELXNOJ MASHINE.
 v |TOM SLUCHAE EGO SLEDUET BRATX IZ \emph{SAMYH STARSHIH} (LEVYH) RAZRYADOV
SLOVA, TAK KAK U MNOGIH DATCHIKOV MLADSHIE RAZRYADY NEDOSTATOCHNO SLUCHAJNY.
(eTO OBSUZHDALOSX V~P.~3.2.1.1.)

vOOBSHCHE, CHTOBY POLUCHITX SLUCHAJNOE CHISLO~$X$ MEZHDU~$0$ I~$k-1$, MY MOZHEM
\emph{UMNOZHITX}~$U$ NA~$k$ I POLOZHITX~$X=\floor{kU}$. dLYA~\MIX{} MOZHNO NAPISATX
$$
\vcenter{
\mixcode
LDA & U
MUL & K
\endmixcode
}
\eqno(1)
$$

pOSLE TOGO KAK |TI DVE KOMANDY BUDUT VYPOLNENY, ISKOMOE CELOE CHISLO
OKAZHETSYA V REGISTRE~$A$. eSLI TREBUETSYA SLUCHAJNOE CELOE MEZHDU~$1$ I~$k$, MY
DOBAVLYAEM K REZULXTATU EDINICU. [zA~(1) POSLEDUET KOMANDA~"|INCA~1|".]

eTOT METOD DAET KAZHDOE CELOE CHISLO S RAVNOJ VEROYATNOSTXYU. [nEBOLXSHOJ
OSHIBKOJ, VYZVANNOJ KONECHNOSTXYU RAZMERA MASHINNOGO SLOVA (SM.~UPR.~2),
VPOLNE MOZHNO PRENEBRECHX, ESLI $k$~MALO, NAPRIMER ESLI~$k/m<1/10000$.] v
BOLEE OBSHCHEM SLUCHAE MY MOGLI BY ZAHOTETX PRIPISATX RAZLICHNYM CELYM CHISLAM
RAZNYE VESA. pREDPOLOZHIM, CHTO ZNACHENIE~$X=x_1$ DOLZHNO POLUCHATXSYA S
VEROYATNOSTXYU~$p_1$, $X=x_2$ S VEROYATNOSTXYU~$p_2$,~\dots, I~$X=x_k$ S
VEROYATNOSTXYU~$p_k$. mY MOZHEM VYRABOTATX RAVNOMERNO RASPREDELENNOE
CHISLO~$U$ I PRINYATX
$$
X=\cases{
x_1, & ESLI~$0\le U < p_1$;\cr
x_2, & ESLI~$p_1\le U<p_1+p_2$;\cr
\ldots\cr
x_k, & ESLI~$p_1+p_2+\cdots+p_{k-1}\le U < 1$.\cr
}
\eqno(2)
$$
(zAMETIM, CHTO~$p_1+p_2+\cdots+p_k=1$.)
%% 128

sUSHCHESTVUET OPTIMALXNYJ SPOSOB SRAVNENIYA~$U$ S
RAZLICHNYMI ZNACHENIYAMI~$p_1+p_2+\cdots+p_s$, KAK |TO TREBUETSYA DLYA
VYCHISLENIJ~(2); |TO OBSUZHDAETSYA V P.~2.3.4.5. mOZHNO
VOSPOLXZOVATXSYA TAKZHE KOMANDOJ "POISK V TABLICE", IMEYUSHCHEJSYA V NEKOTORYH
MASHINAH. k CHASTNYM SLUCHAYAM PRIMENIMY BOLEE |FFEKTIVNYE METODY. nAPRIMER,
CHTOBY POLUCHITX ODNO IZ ODINNADCATI ZNACHENIJ~$2$, $3$,~\dots, $12$ S
SOOTVETSTVUYUSHCHIMI VEROYATNOSTYAMI~$1\over 36$, $2\over 36$,~\dots, $6\over
36$,~\dots, $2\over 36$, $1\over 36$, MOGLI BY VYCHISLITX DVA NEZAVISIMYH
SLUCHAJNYH CELYH CHISLA OT~$1$ DO~$6$, A ZATEM IH SLOZHITX.

oDNAKO NI ODIN IZ PERECHISLENNYH VYSHE SPOSOBOV NE POZVOLYAET MAKSIMALXNO
BYSTRO VYBRATX~$x_1$,~\dots, $x_k$ S PRAVILXNYMI VEROYATNOSTYAMI.
zNACHITELXNO BOLEE |FFEKTIVNYJ DLYA BOLXSHINSTVA SLUCHAEV METOD, TREBUYUSHCHIJ
NEBOLXSHOGO UVELICHENIYA PAMYATI, RASSMATRIVAETSYA V UPR.~20 I~21.

\section{B.~oBSHCHIE METODY DLYA NEPRERYVNYH RASPREDELENIJ}. sAMOE OBSHCHEE
RASPREDELENIE DEJSTVITELXNYH SLUCHAJNYH VELICHIN OPISYVAETSYA V TERMINAH
"FUNKCII RASPREDELENIYA"~$F(x)$; MY TREBUEM, CHTOBY SLUCHAJNAYA VELICHINA~$X$
PRINIMALA ZNACHENIE, MENXSHEE ILI RAVNOE~$x$, S VEROYATNOSTXYU~$F(x)$:
$$
F(x)= \hbox{VEROYATNOSTX} (X\le x).
\eqno (3)
$$
eTA FUNKCIYA VSEGDA MONOTONNO UVELICHIVAETSYA OT NULYA DO EDINICY:
$$
F(x_1) \le F(x_2), \rem{ESLI~$x_1\le x_2$; $F(-\infty)=0$, $F(+\infty)=1$.}
\eqno (4)
$$
pRIMERY FUNKCIJ RASPREDELENIYA PRIVODYATSYA V P.~3.3.1, RIS.~3. eSLI~$F(x)$
NEPRERYVNA I STROGO VOZRASTAET (TAK CHTO~$F(x_1)<F(x_2)$, ESLI~$x_1<x_2$),
ONA PRINIMAET VSE ZNACHENIYA MEZHDU NULEM I EDINICEJ, I SUSHCHESTVUET OBRATNAYA
FUNKCIYA~$F^{-1}(y)$, TAKAYA, CHTO ESLI~$0<y<1$, TO
$$
y=F(x) \hbox{ TOGDA I TOLXKO TOGDA, KOGDA } x=F^{-1}(y).
\eqno (5)
$$
oBSHCHIJ SPOSOB VYCHISLENIYA SLUCHAJNOJ VELICHINY~$X$ S NEPRERYVNOJ STROGO
VOZRASTAYUSHCHEJ FUNKCIEJ RASPREDELENIYA~$F(x)$ ZAKLYUCHAETSYA V TOM, CHTO POLAGAYUT
$$
X=F^{-1}(U).
\eqno(6)
$$

v SAMOM DELE, VEROYATNOSTX TOGO, CHTO~$X\le x$, YAVLYAETSYA VEROYATNOSTXYU TOGO,
 CHTO~$F^{-1}(U)\le x$, T.~E.\ VEROYATNOSTXYU SOBYTIYA~$U\le F(x)$, A ONA RAVNA~$F(x)$.

tEPERX ZADACHA SVODITSYA K ODNOJ IZ PROBLEM CHISLENNOGO ANALIZA DLYA
OPREDELENIYA HOROSHIH METODOV VYCHISLENIYA~$F^{-1}(U)$ S TREBUYUSHCHEJSYA TOCHNOSTXYU.
chISLENNYJ ANALIZ VYHODIT ZA RAMKI |TOJ KNIGI. oDNAKO SUSHCHESTVUET RYAD
VAZHNYH RACIONALXNYH PRIEMOV,
%% 129
PRIGODNYH DLYA USKORENIYA |TOGO OBSHCHEGO METODA, I MY IH ZDESX RASSMOTRIM.

pREZHDE VSEGO, ESLI~$X_1$ I~$X_2$---NEZAVISIMYE SLUCHAJNYE VELICHINY S
FUNKCIYAMI RASPREDELENIYA~$F_1(x)$ I~$F_2(x)$, TO
$$
\eqalign{
\max(X_1, X_2) & \rem{IMEET RASPREDELENIE~$F_1(x)F_2(x)$,}\cr
\min(X_1, X_2) & \rem{IMEET RASPREDELENIE~$F_1(x)+F_2(x)-F_1(x)F_2(x)$.}\cr
}
\eqno(7)
$$
(sM.~UPR.~4.) nAPRIMER, SLUCHAJNOE CHISLO~$U$ IMEET FUNKCIYU
RASPREDELENIYA~$F(x)=x$ DLYA~$0\le x < 1$. eSLI~$U_1$, $U_2$,~\dots,
$U_t$---NEZAVISIMYE SLUCHAJNYE CHISLA, TO~$\max(U_1, U_2,~\ldots, U_t)$ IMEET
FUNKCIYU RASPREDELENIYA~$F(x)=x^t$, $0\le x < 1$. eTO LEZHIT V OSNOVE TESTA
"NAIBOLXSHEE IZ~$t$", OPISANNOGO V~P.~3.3.2. zAMETIM, CHTO OBRATNAYA FUNKCIYA
V |TOM SLUCHAE ESTX~$F^{-1}(y)=\root t \of{y}$. tAKIM OBRAZOM, V CHASTNOM
SLUCHAE~$t=2$ MY VIDIM, CHTO DVE FORMULY
$$
X=\sqrt{U} \hbox{ I } X=\max(U_1, U_2)
\eqno (8)
$$
PRIVODYAT K |KVIVALENTNYM RASPREDELENIYAM SLUCHAJNOJ VELICHINY~$X$, HOTYA NA
PERVYJ VZGLYAD |TO NE OCHEVIDNO. mY IZBAVLENY OT NEOBHODIMOSTI VYCHISLYATX
KVADRATNYJ KORENX IZ SLUCHAJNOJ VELICHINY.

tAKIH PRIEMOV BESKONECHNO MNOGO. lYUBOJ ALGORITM, KOTOROMU NA VHODE ZADAYUTSYA
SLUCHAJNYE CHISLA, NA VYHODE VYDAET SLUCHAJNUYU VELICHINU S \emph{NEKOTORYM}
RASPREDELENIEM. zADACHA ZAKLYUCHAETSYA V OPREDELENII OBSHCHIH METODOV POSTROENIYA
ALGORITMA, IMEYA ZADANNUYU FUNKCIYU RASPREDELENIYA NA VYHODE.

pOLXZUYASX SOOTNOSHENIEM~(7), MOZHNO POLUCHITX \emph{PROIZVEDENIE} DVUH
FUNKCIJ RASPREDELENIYA. sUSHCHESTVUET TAKZHE METOD \emph{SMESHIVANIYA} DVUH
RASPREDELENIJ: PREDPOLOZHIM, CHTO
$$
F(x)=pF_1(x)+(1-p)F_2(x), \rem{$0<p<1$.}
\eqno (9)
$$
mY MOZHEM VYCHISLITX ZNACHENIE SLUCHAJNOJ VELICHINY~$X$ S
RASPREDELENIEM~$F(x)$, OPREDELIV SNACHALA SLUCHAJNOE CHISLO~$U$. eSLI~$U<p$,
 SCHITAEM, CHTO $X$~IMEET RASPREDELENIE~$F_1(x)$, ESLI ZHE~$U\ge p$,
TO~$X$---SLUCHAJNAYA VELICHINA S RASPREDELENIEM~$F_2(x)$.

eTA PROCEDURA MOZHET BYTX OCHENX POLEZNA, ESLI $p$~BLIZKO K EDINICE,
A~$F_1(x)$---RASPREDELENIE, KOTOROE LEGKO MODELIROVATX. tOGDA, NESMOTRYA NA
TO CHTO VYRABOTKA SLUCHAJNYH ZNACHENIJ PO RASPREDELENIYU~$F_2(x)$ MOZHET BYTX
BOLEE TRUDOEMKOJ, CHEM DLYA TREBUYUSHCHEGOSYA POLNOGO RASPREDELENIYA~$F(x)$,
BOLEE TRUDNYE VYCHISLENIYA DOLZHNY BUDUT PROVODITXSYA REDKO, S
VEROYATNOSTXYU~$(1-p)$. nIZHE MY UVIDIM, CHTO |TA IDEYA S USPEHOM ISPOLXZUETSYA
DLYA NESKOLXKIH VAZHNYH SLUCHAEV.

\section{C.~nORMALXNOE RASPREDELENIE}. \dfn{nORMALXNOE RASPREDELENIE SO
SREDNIM ZNACHENIEM, RAVNYM NULYU, I STANDARTNYM OTKLONENIEM, RAVNYM
%% 129
EDINICE,} YAVLYAETSYA, VOZMOZHNO, VAZHNEJSHIM IZ NERAVNOMERNYH NEPRERYVNYH RASPREDELENIJ:
$$
F(x)={1\over \sqrt{2\pi}}\int_{-\infty}^x e^{-t^2/2}\,dt.
\eqno(10)
$$
dLYA VYRABOTKI NORMALXNO RASPREDELENNYH SLUCHAJNYH VELICHIN SUSHCHESTVUET
NESKOLXKO PRIEMOV.

{\sl (1)~mETOD POLYARNYH KOORDINAT.\/}

\alg r.(mETOD POLYARNYH KOORDINAT DLYA NORMALXNOGO RASPREDELENIYA.) eTOT
ALGORITM VYCHISLYAET DVE NEZAVISIMYE NORMALXNO RASPREDELENNYE SLUCHAJNYE
VELICHINY~$X_1$ I~$X_2$ PO DVUM ZADANNYM NEZAVISIMYM SLUCHAJNYM CHISLAM~$U_1$ I~$U_2$.

\st[pOLUCHITX SLUCHAJNYE CHISLA.] vYRABOTATX DVA NEZAVISIMYH SLUCHAJNYH
CHISLA~$U_1$, $U_2$, RAVNOMERNO RASPREDELENNYH MEZHDU NULEM I EDINICEJ.
uSTANOVITX~$V_1\asg 2U_1-1$, $V_2\asg 2U_2-1$. (tEPERX~$V_1$ I~$V_2$
RAVNOMERNO RASPREDELENY MEZHDU~$-1$ I~$+1$. dLYA BOLXSHINSTVA MASHIN V |TOT
MOMENT PREDPOCHTITELXNEJ PREDSTAVITX~$V_1$ I~$V_2$ V FORME S PLAVAYUSHCHEJ TOCHKOJ.)

\st[vYCHISLITX~$S$.] uSTANOVITX~$S\asg V_1^2+V_2^2$.

\st[$S\ge 1$?] eSLI~$S\ge1$, VERNUTXSYA K SHAGU~\stp{1}. (shAGI S~\stp{1}
PO~\stp{3} V SREDNEM VYPOLNYAYUTSYA $1.27$~RAZ PRI STANDARTNOM
OTKLONENII~$0.587$; SM.~UPR.~6).

\st[vYCHISLITX~$X_1$, $X_2$.] pRISVOITX~$X_1$, $X_2$ ZNACHENIYA, VYCHISLENNYE
PO FORMULAM
$$
X_1=V_1\sqrt{-2\ln S\over S}, \qquad
X_2=V_2\sqrt{-2\ln S\over S}.
\eqno(11)
$$

eTO I ESTX TREBUYUSHCHIESYA ZNACHENIYA NORMALXNO RASPREDELENNYH SLUCHAJNYH VELICHIN.
\algend

chTOBY DOKAZATX, CHTO METOD TOCHEN, VOSPOLXZUEMSYA |LEMENTARNOJ ANALITICHESKOJ
GEOMETRIEJ. eSLI NA SHAGE~P3 $S<1$, TOCHKA PLOSKOSTI S DEKARTOVYMI
KOORDINATAMI~$(V_1, V_2)$ YAVLYAETSYA \emph{SLUCHAJNOJ TOCHKOJ, RAVNOMERNO
RASPREDELENNOJ VNUTRI EDINICHNOGO KRUGA.} pEREHODYA K POLYARNYM
KOORDINATAM~$V_1=R\cos\Theta$, $V_2=R\sin\Theta$, NAHODIM~$S=R^2$,
$X_1=\sqrt{-2\ln S}\cos\Theta$, $X_2=\sqrt{-2\ln S}\sin\Theta$. iSPOLXZUYA
TAKZHE POLYARNYE KOORDINATY~$X_1=R'\cos\Theta'$, $X_2=R'\sin\Theta'$, MY
VIDIM, CHTO~$\theta'=\theta$ I~$R'=\sqrt{-2\ln S}$. yaSNO, CHTO~$R'$
I~$\Theta'$ NEZAVISIMY, TAK KAK~$R$ I~$\Theta$ NEZAVISIMY VNUTRI EDINICHNOGO
KRUGA. kROME TOGO, $\Theta'$~RAVNOMERNO RASPREDELENA MEZHDU~$0$ I~$2\pi$, A
VEROYATNOSTX TOGO, CHTO~$R'\le r$, RAVNA VEROYATNOSTI SOBYTIYA---$2\ln S \le
r^2$, T.~E.\ VEROYATNOSTI SOBYTIYA~$S\ge e^{-r^2/2}$. pOSLEDNYAYA
RAVNA~$1-e^{-r^2/2}$, POSKOLXKU~$S=R^2$ RAVNOMERNO RASPREDELENA MEZHDU
NULEM I EDINICEJ.
%% 131
vEROYATNOSTX TOGO, CHTO $R'$~LEZHIT MEZHDU~$r$ I~$r+dr$, RAVNA PO|TOMU
PROIZVODNOJ OT~$1-e^{-r^2/2}$, A IMENNO~$re^{-r^2/2}dr$. pODOBNYM ZHE
OBRAZOM VEROYATNOSTX POPADANIYA~$\Theta'$ V INTERVAL MEZHDU~$\theta$
I~$\theta+d\theta$ ESTX~$(1/2\pi)d\theta$. pO|TOMU VEROYATNOSTX TOGO,
CHTO~$X_1\le x_1$, A~$X_2\le x_2$, RAVNA
$$
\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
}
$$

eTO DOKAZYVAET, CHTO~$X_1$ I~$X_2$ NEZAVISIMY I NORMALXNO RASPREDELENY, KAK
I TREBOVALOSX. aLGORITM~P PREDLOZHILI dZH.~bOKS, m.~mALLER I~dZH.~mARSALXYA.

{\sl (2)~mETOD mARSALXI (METOD PRYAMOUGOLXNIKA---KLINA---HVOSTA).\/}

v |TOM METODE MY ISPOLXZUEM RASPREDELENIE
$$
F(x)=\sqrt{2\over\pi}\int_0^x e^{-t^2/2}\,dt \rem{$x\ge0$,}
\eqno(12)
$$
TAK CHTO $F(x)$~YAVLYAETSYA FUNKCIEJ RASPREDELENIYA \emph{MODULYA} NORMALXNOJ
SLUCHAJNOJ VELICHINY. pOSLE VYCHISLENIYA~$X$ V SOOTVETSTVII S |TIM
RASPREDELENIEM EE ZNACHENIYU PRIPISYVAETSYA SLUCHAJNYJ ZNAK, V REZULXTATE MY
POLUCHAEM PRAVILXNOE ZNACHENIE NORMALXNOJ SLUCHAJNOJ VELICHINY.

oBSHCHIJ PODHOD mARSALXI, POZVOLYAYUSHCHIJ |FFEKTIVNO ISPOLXZOVATX SLUCHAJNYE
CHISLA, BUDET PROILLYUSTRIROVAN NA PRIMERE RASPREDELENIYA~(12). iZUCHAYA |TOT
CHASTNYJ PRIMER, MY ODNOVREMENNO UZNAEM NESKOLXKO OBSHCHIH METODOV.

zA OSNOVU PRINIMAETSYA SLEDUYUSHCHEE PREDSTAVLENIE:
$$
F(x)=p_1F_1(x)+p_2F_2(x)+\cdots+p_nF_n(x),
\eqno(13)
$$
GDE~$F_1$, $F_2$,~\dots, $F_n$---NEKOTORYE RASPREDELENIYA. sLUCHAJNAYA
VELICHINA~$X$ TOGDA OPREDELYAETSYA PO RASPREDELENIYU~$F_j$ S
VEROYATNOSTXYU~$p_j$. nEKOTORYE IZ RASPREDELENIJ~$F_j(x)$ MOGUT OKAZATXSYA
DOVOLXNO TRUDNYMI DLYA VYCHISLENIJ, NO MY OBYCHNO PODBIRAEM IH TAK, CHTOBY V
|TOM SLUCHAE VEROYATNOSTX~$p_j$ BYLA OCHENX MALA. bOLXSHINSTVO FUNKCIJ
RASPREDELENIYA~$F_j(x)$ OKAZHUTSYA OCHENX PROSTYMI, BUDUCHI TRIVIALXNYMI
MODIFIKACIYAMI RAVNOMERNOGO RASPREDELENIYA. mETOD V CELOM POZVOLYAET
SOZDAVATX CHREZVYCHAJNO |FFEKTIVNYE PROGRAMMY, TAK KAK \emph{SREDNEE} VREMYA
VYCHISLENIJ OCHENX MALO.

%% 132

mETOD LEGCHE PONYATX, ESLI IMETX DELO S \emph{PROIZVODNYMI} FUNKCIJ
RASPREDELENIYA VMESTO SAMIH RASPREDELENIJ. oBOZNACHIM
$$
f(x)=F'(x), \qquad f_j(x)=F'_j(x).
$$
fUNKCII~$f(x)$ I~$f_j(x)$ NAZYVAYUTSYA \dfn{PLOTNOSTYAMI} |TIH VEROYATNOSTNYH
RASPREDELENIJ. uRAVNENIE~(13) PREOBRAZUETSYA V
$$
f(x)=p_1f_1(x)+p_2f_2(x)+\cdots+p_nf_n(x).
\eqno(14)
$$
kAZHDAYA~$f_j(x)\ge0$, A POLNAYA PLOSHCHADX POD KRIVOJ~$f_j(x)$
RAVNA~$1$. pO|TOMU SUSHCHESTVUET PROSTAYA GRAFICHESKAYA INTERPRETACIYA
SOOTNOSHENIYA~(14). pLOSHCHADX POD GRAFIKOM~$f(x)$ DELITSYA NA $n$~CHASTEJ,
KAZHDAYA IZ KOTORYH IMEET PLOSHCHADX~$p_j$ I SOOTVETSTVUET~$f_j(x)$. pOSMOTRITE
NA RIS.~9, PROYASNYAYUSHCHIJ SITUACIYU DLYA SLUCHAYA, KOTORYM MY SEJCHAS INTERESUEMSYA,
KOGDA~$f(x)=F'(x)=\sqrt{(2/\pi)}e^{-x^2/2}$. pLOSHCHADX POD KRIVOJ NA RISUNKE
RAZDELENA NA $n=37$~CHASTEJ: $12$~DOVOLXNO
\picture{rIS.~9. chASTOTNAYA FUNKCIYA, SOSTOYASHCHAYA IZ 37~CHASTEJ. sLUCHAJNAYA
VELICHINA VYCHISLYAETSYA V SREDNEM STOLXKO RAZ KAKOVA PLOSHCHADX CHASTI,
SOOTVETSTVUYUSHCHEJ EE CHASTOTE.}
BOLXSHIH PRYAMOUGOLXNIKOV,  KOTORYE SOOTVETSTVUYUT~$p_1f_1(x)$,~\dots,
$p_{12}f_{12}(x)$, $12$~UZKIH NEBOLXSHIH PRYAMOUGOLXNIKOV, PRIMYKAYUSHCHIH
SVERHU K PREDYDUSHCHIM I SOOTVETSTVUYUSHCHIH~$p_{13}f_{13}(x)$,~\dots,
$p_{24}f_{24}(x)$, $12$~KLINOOBRAZNYH FIGUR, PREDSTAVLYAYUSHCHIH
FUNKCII~$p_{25}f_{25}(x)$,~\dots, $p_{36}f_{36}(x)$, I OSTAVSHAYASYA
CHASTX~$p_{37}f_{37}(x)$, SOVPADAYUSHCHAYA S~$f(x)$ PRI~$x\ge3$.

sTUPENXKI~$f_1(x)$,~\dots, $f_{12}(x)$ OPISYVAYUT \emph{RAVNOMERNYE
RASPREDELENIYA.} nAPRIMER,  $f_3(x)$ OTVECHAET SLUCHAJNOJ VELICHINE, RAVNO-
%% 133
MERNO RASPREDELENNOJ MEZHDU~$1/2$ I~$3/4$. mY HOTIM OPREDELITX~$p_1$, $p_2$,~\dots,
$p_{12}$ TAK, CHTOBY |FFEKTIVNO VYRABATYVATX NORMALXNYE SLUCHAJNYE
VELICHINY. (pREDPOLOZHIM, CHTO MY IMEEM DELO S DVOICHNOJ MASHINOJ; DLYA
DESYATICHNOJ PRIMENYAETSYA ANALOGICHNAYA PROCEDURA.) vYBEREM IH KRATNYMI, SKAZHEM,
$1/256$. eTO OZNACHAET, CHTO PLOSHCHADX POD~$p_j f_j(x)$ BUDET KRATNA~$1/256$.
pRIMEM VYSOTU~$f_j(x)$ RAVNOJ
$$
\floor{64 f(j/4)}/64 \rem{$1\le j \le 12$.}
$$

v TABLICE PRIVODYATSYA POLUCHAYUSHCHIESYA PRI |TOM ZNACHENIYA VEROYATNOSTEJ:
$$
\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)
$$

oTSYUDA SLEDUET, CHTO REALIZACIYA RAVNOMERNYH RASPREDELENIJ~$F_1$,~\dots,
$F_{12}$ ZAJMET~$p_1+p_2+\cdots+p_{12}=88\%$~VREMENI (88\%~PLOSHCHADI
POD~$f(x)$ ZANIMAYUT BOLXSHIE PRYAMOUGOLXNIKI).

mARSALXEJ BYL PREDLOZHEN |FFEKTIVNYJ SPOSOB VYBORA IZ 13~VOZMOZHNOSTEJ,
PREDSTAVLENNYH V~(15). pRI ZADANNOM SLUCHAJNOM DVOICHNOM CELOM CHISLE V
PROMEZHUTKE OT~$0$ DO~$255$, DVOICHNOE PREDSTAVLENIE KOTOROGO
ESTX~$b_1b_2b_3b_4b_5b_6b_7b_8$, MY POSTUPAEM SLEDUYUSHCHIM OBRAZOM:
$$
\vcenter{\halign{
#\bskip&\hfill$#$&${}#\quad$\hfill&{\vtop{\hsize=0.5\hsize\noindent#\par}}\cr
ESLI&   0&\le b_1b_2b_3b_4 < 10,            & POLAGAEM~$X=A[b_1b_2b_3b_4]+{1\over4}U$;\cr
ESLI&  40&\le b_1b_2b_3b_4b_5b_6<52,        & POLAGAEM~$X=B[b_1b_2b_3b_4b_5b_6]+{1\over4}U$;\cr
ESLI& 208&\le b_1b_2b_3b_4b_5b_6b_7b_8<225, & POLAGAEM~$X=C[b_1b_2b_3b_4b_5b_6b_7b_8]+{1\over4}U$;\cr
ESLI& 225&\le b_1b_2b_3b_4b_5b_6b_7b_8,     & VYRABATYVAEM~$X$, ISPOLXZUYA RASPREDELENIYA~$F_{13}$,~\dots, $F_{37}$, KAK OPISYVAETSYA NIZHE.\cr
}}
\eqno (16)
$$

zDESX~$A$, $B$, $C$---VSPOMOGATELXNYE MASSIVY, PRIVEDENNYE V TABL.~1,
a~$U$---SLUCHAJNOE CHISLO (OT~$0$ DO~$1$).

chTOBY PONYATX, POCHEMU |TA PROCEDURA RABOTAET, RASSMOTRIM, NAPRIMER,
SLUCHAJ~$j=4$. fUNKCIYA~$F_4(x)$---|TO RAVNOMERNOE RASPREDELENIE SLUCHAJNOJ
VELICHINY (MEZHDU~$3/4$ I~$1$), KOTOROE IMEET
SLUCHAJNAYA VELICHINA~$X={3\over4}+{1\over4}U$. vEROYATNOSTX TOGO, CHTO
|TO RASPREDELENIE REALIZUETSYA V OPISANNOM VYSHE METODE, TAKOVA:
${1\over16}\times\left(\hbox{CHISLO RAZ, KOTOROE "}{3\over4}\hbox{"VSTRECHAETSYA
V MASSIVE}~A\right)+{1\over 64}\times
(\hbox{ANALOGICHNOE CHISLO "POYAVLENIJ" V MASSIVE}~$B$)+
{1\over 256}\times  (\hbox{CHISLO "POYAVLENIJ" V MASSIVE}~C)$.
%% 134
\htable{tABLICA~1}%
{tABLICY DLYA |FFEKTIVNOGO VYBORA IZ 12 ALXTERNATIV V METODE~(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
}
oNA RAVNA~${1\over16}+{3\over 64}+{2\over 256}={30\over 256}=p_4$, TAK
CHTO $F_4(x)$~MODELIRUETSYA S PRAVILXNOJ VEROYATNOSTXYU. kONECHNO, BYLO BY ESHCHE
BYSTREE VOSPOLXZOVATXSYA DRUGIM METODOM:
$$
\displaylines{
\hbox{"ESLI}~0\le b_1b_2b_3b_4b_5b_6b_7b_8 < 225, \hbox{ POLAGAEM }\cr
X=T[b_1b_2b_3b_4b_5b_6b_7b_8]+{1\over4}U\hbox{"}\cr
}
$$
VMESTO PERVYH TREH PROVEROK~(16). zDESX $T$~ZADAVALOSX BY TABLICEJ IZ
225~CHISEL, 49 IZ KOTORYH RAVNYALISX BY~"$0$", 45~CHISEL
RAVNYALISX BY~$1\over4$, 38~RAZ POVTORYALOSX BY~$1\over2$ I~T.~D. dLYA
SRAVNENIYA V PREDYDUSHCHEM METODE ISPOLXZUETSYA TOLXKO TABLICA, SODERZHASHCHAYA
39~VELICHIN, I ON NENAMNOGO MEDLENNEJ, TAK KAK
PROVERKA~"$b_1b_2b_3b_4b_5b_6<52$?", ZANIMAET NE BOLEE~$3/8$ VSEGO VREMENI,
A PROVERKA~"$b_1b_2b_3b_4b_5b_6b_7b_8<225$?" TREBUET TOLXKO
$3/16$~VREMENI. eKONOMIYA PAMYATI V METODE, PODOBNOM~(16), ESHCHE ZNACHITELXNEJ
V OBSHCHEM SLUCHAE, KOGDA IMEETSYA BOLXSHE 256~VOZMOZHNOSTEJ.

chITATELYU SLEDUET V |TOM MESTE SDELATX PAUZU, CHTOBY TSHCHATELXNO IZUCHITX
VESX METOD, POKA ON NE POJMET, IZ-ZA CHEGO PO FORMULAM~(16)
RASPREDELENIYA~$F_j$ VYBIRAYUTSYA S VEROYATNOSTYAMI~$p_j$ DLYA~$1\le j \le 12$.

rASPREDELENIYA~$F_{13}(x)$,~\dots, $F_{24}(x)$---TAKZHE RAVNOMERNYE, I S NIMI
MOZHNO POSTUPATX ANALOGICHNO. oNI IMEYUT DOVOLXNO MALUYU VEROYATNOSTX
%% 135
$\bigl($NEKOTOROE CHISLO MEZHDU~$0$ I~${1\over256}\bigr)$, PO|TOMU
NAIBOLEE |FFEKTIVNO PROVERYATX |TI VEROYATNOSTI S POMOSHCHXYU CHASTI
NASHEGO ALGORITMA DLYA VYRABOTKI NORMALXNYH SLUCHAJNYH VELICHIN, KOTORYJ
BUDET ISPOLXZOVATXSYA NE SLISHKOM CHASTO (SM.~SHAG~M4 V ALGORITME~M, NIZHE).
eTI RASPREDELENIYA PREDSTAVLYAYUT SOBOJ POPRAVKI K BOLXSHIM PRYAMOUGOLXNIKAM,
VOZNIKAYUSHCHIE PRI OKRUGLENII VEROYATNOSTEJ DLYA~(15). mY IMEEM
$$
p_j+p_{j+12}={1\over4}f(j/4), \rem{$1\le j \le 12$}.
\eqno(12)
$$

tEPERX VERNEMSYA K VOPROSU O VYCHISLENII SLUCHAJNYH VELICHIN DLYA KLINOOBRAZNYH
RASPREDELENIJ~$F_{25}(x)$,~\dots, $F_{36}(x)$. tIPICHNYJ SLUCHAJ IZOBRAZHEN
NA RIS.~10. kOGDA~$x<1$, KRIVAYA VYPUKLA
\picture{
 rIS.~10. fUNKCII PLOTNOSTI VEROYATNOSTI, DLYA KOTORYH PRI VYRABOTKE
 SLUCHAJNYH CHISEL MOZHET BYTX ISPOLXZOVAN ALGORITM~L.
}
VVERH, A PRI~$x>1$---VNIZ, NO V OBOIH SLUCHAYAH KRIVAYA OCHENX BLIZKA K PRYAMOJ
LINII I MOZHET BYTX VLOZHENA, KAK POKAZANO NA RISUNKE, MEZHDU DVUMYA PRYAMYMI.

\alg L.(pOCHTI LINEJNYE PLOTNOSTI.) eTOT ALGORITM MOZHNO ISPOLXZOVATX DLYA
VYRABOTKI ZNACHENIYA SLUCHAJNOJ VELICHINY~$X$ DLYA LYUBOJ PLOTNOSTI
RASPREDELENIYA~$f(x)$, UDOVLETVORYAYUSHCHEJ SLEDUYUSHCHIM USLOVIYAM (SR.~S~RIS.~10):
$$
\displaynarrow{
 f(x)=0 \rem{DLYA~$x<s$ I~$x>s+h$;}\cr
 a-b(x-s)/h \le f(x) \le b-b(x-s)/h \rem{DLYA~$s\le x \le s+h$.}\cr
}
\eqno(18)
$$

\st[pOLUCHITX~$U\le V$.] vYRABOTATX DVA NEZAVISIMYH SLUCHAJNYH CHISLA~$U$,
$V$, RAVNOMERNO RASPREDELENNYH MEZHDU NULEM I EDINICEJ. eSLI~$U>V$,
POMENYATX MESTAMI~$U\xchg V$.

\st[pROSTOJ SLUCHAJ?] eSLI~$V\le a/b$, PEREJTI K~\stp{4}.

%% 136

\st[pOPYTATXSYA ESHCHE RAZ?] eSLI~$V>U+(1/b)f(s+hU)$, VERNUTXSYA OBRATNO K
SHAGU~\stp{1}. (eSLI~$a/b$ BLIZKO K~$1$, |TOT SHAG ALGORITMA BUDET
ISPOLXZOVATXSYA NE SLISHKOM CHASTO.)

\st[vYCHISLITX~$X$.] uSTANOVITX~$X\asg s+hU$.
\algend

dLYA DOKAZATELXSTVA PRAVILXNOSTI ALGORITMA ZAMETIM, CHTO, KOGDA MY PRIHODIM
K SHAGU~L4, TOCHKA~$(U, V)$---|TO SLUCHAJNAYA
\picture{rIS. 11. oBLASTX "PRINYATIYA REZULXTATA" V ALGORITME L.}
TOCHKA V KVADRATE, IZOBRAZHENNOM NA RIS.~11, A IMENNO~$0\le U\le V \le U+(1/b)f(s+hU)$.

uSLOVIYA~(18) GARANTIRUYUT, CHTO
$$
{a\over b}\le U+{1\over b}f(s+hU)\le 1.
$$
tEPERX VEROYATNOSTX TOGO, CHTO~$X\le s+hx$ DLYA~$0\le x \le 1$,
RAVNA OTNESHENIYU PLOSHCHADI SLEVA OT VERTIKALXNOJ LINII~$U=x$ NA RIS.~11 KO
VSEJ PLOSHCHADI, T.~E.\
$$
\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;
$$
PO|TOMU $X$~IMEET NUZHNOE RASPREDELENIE.

chTOBY ISPOLXZOVATX |TOT ALGORITM, NAM NEOBHODIMO OPREDELITX~$a_j$, $b_j$,
$s_j$, $h$ DLYA PLOTNOSTEJ VEROYATNOSTEJ~$f_{j+24}(x)$ (RIS.~9). nETRUDNO
VIDETX, CHTO PRI~$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
kROME TOGO,
$$
\eqalignter{
 a_j&=f_{j+24}(s_j)                & \rem{PRI~$1\le j \le 4$,}\cr
 b_j&=f_{j+24}(s_j)                & \rem{PRI~$5\le j \le 12$;}\cr
 b_j&=-hf'_{j+24}(s_j+h)           & \rem{PRI~$1\le j \le 4$,}\cr
 a_j&=f_{j+24}(x_j)+(x_j-s_j)b_j/h & \rem{PRI~$5\le j \le 12$,}\cr
}
\eqno(20)
$$
GDE~$x_j$---KORENX URAVNENIYA~$f'_{j+24}(x_j)=-b_j/h$.

pOSLEDNEE RASPREDELENIE~$F_{37}(x)$ DOLZHNO MODELIROVATXSYA TOLXKO ODIN RAZ
IZ CHETYREHSOT. oNO ISPOLXZUETSYA VSEGDA, KOGDA DOLZHEN
\picture{
 rIS.~12. aLGORITM "PRYAMOUGOLXNIK-KLIN-HVOST" DLYA VYRABOTKI NORMALXNO
 RASPREDELENNYH SLUCHAJNYH VELICHIN.
}
POLUCHITXSYA REZULXTAT~$X\ge 3$. v |TOM SLUCHAE MOZHNO PRIMENITX MODIFIKACIYU
ALGORITMA~P, KAK POKAZANO NIZHE (SHAGI~m8---m9). pREDOSTAVLYAEM CHITATELYU
VOZMOZHNOSTX DOKAZATX, CHTO PRIVEDENNYJ METOD TOCHEN.

tEPERX PRIVODIM PROCEDURU POLNOSTXYU.

\alg M.(mETOD mARSALXI---mAKLARENA DLYA NORMALXNYH SLUCHAJNYH VELICHIN.) v |TOM
ALGORITME ISPOLXZUYUTSYA NEKOTORYE VSPOMOGATELXNYE TABLICY, USTROENNYE, KAK
OB�YASNYALOSX V TEKSTE (PRIMERY PRIVEDENY V TABL.~1 I~2). aLGORITM
PRIVODITSYA DLYA DVOICHNOJ MASHINY, DLYA DESYATICHNOJ MASHINY ON STROITSYA ANALOGICHNO.
%% 138
\htable{tABLICA 2}%
{pRIMERY TABLIC, ISPOLXZUEMYH V ALGORITME~M%
\note{1}{nA PRAKTIKE DANNYE DLYA TABLIC~$P$, $Q$, $D$, $E$ SLEDUET DAVATX S BOLXSHEJ TOCHNOSTXYU.}
}%
{\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[pOLUCHITX~$U$.] vYRABOTATX SLUCHAJNOE CHISLO~$U=.b_0b_1b_2\ldots{} b_t$.
(zDESX~$b$---BITY V DVOICHNOM PREDSTAVLENII~$U$. dLYA HOROSHEJ TOCHNOSTI~$t$
DOLZHNO BYTX NE MENXSHE~24.) uSTANOVITX~$\psi\asg b_0$. (pOZZHE
$\psi$~PONADOBITSYA DLYA OPREDELENIYA ZNAKA REZULXTATA.)

\st[bOLXSHOJ PRYAMOUGOLXNIK?] eSLI~$b_1b_2b_3b_4<10$, GDE
"$b_1b_2b_3b_4$"~OBOZNACHAET DVOICHNOE CELOE CHISLO~$8b_1+4b_2+2b_3+b_4$, USTANOVITX
$$
X\asg A[b_1b_2b_3b_4]+.00b_5b_6\ldots{} b_t
$$
I PEREJTI K~\stp{10}. iNACHE, ESLI~$b_1b_2b_3b_4b_5b_6<52$, USTANOVITX
$$
X\asg B[b_1b_2b_3b_4b_5b_6]+.00b_7b_8\ldots{}b_t
$$
I PEREJTI K~\stp{10}. iNACHE, ESLI~$b_1b_2b_3b_4b_5b_6b_7b_8<225$, USTANOVITX
$$
X\asg C[b_1b_2b_3b_4b_5b_6b_7b_8]+.00b_9b_{10}\ldots{}b_t
$$
I PEREJTI K~\stp{10}.

\st[kLIN ILI HVOST?] nAJTI \emph{NAIMENXSHEE} ZNACHENIE~$j$, $1\le j \le 13$,
 DLYA KOTOROGO~$b_1b_2\ldots{}b_t<P[j]$. eSLI~$j=13$, PEREJTI K SHAGU~\stp{8}.

\st[uZKIJ PRYAMOUGOLXNIK?] eSLI~$.b_1b_2\ldots{}b_t<Q[j]$, VYRABOTATX
NOVOE SLUCHAJNOE CHISLO~$U$, USTANOVITX~$X\asg S[j]+{1\over 4}U$ I PEREJTI K~\stp{10}.

%% 139

\st[pOLUCHITX~$U\le V$.] vYRABOTATX DVA NOVYH SLUCHAJNYH CHISLA~$U$, $V$;
ESLI~$U>V$, POMENYATX IH MESTAMI~$U\xchg V$. (tEPERX VYPOLNYAETSYA
ALGORITM~L.) uSTANOVITX~$X\asg S[j]+{1\over4}U$.

\st[pROSTOJ SLUCHAJ?] eSLI~$V\le D[j]$, PEREJTI K~\stp{10}.

\st[eSHCHE ODNA POPYTKA?] eSLI~$V>U+E[j](e^{-(X^2-S[j+1]^2)/2}-1)$, VERNUTXSYA
K SHAGU~\stp{5}; V PROTIVNOM SLUCHAE PEREJTI K~\stp{10}. (eTOT SHAG
VYPOLNYAETSYA S MALOJ VEROYATNOSTXYU.)

\st[pOLUCHITX~$U^2+V^2<1$.] vYRABOTATX DVA NOVYH SLUCHAJNYH CHISLA~$U$, $V$.
uSTANOVITX~$W\asg U^2+V^2$. eSLI~$W\ge1$, POVTORITX |TOT SHAG.

\st[vYCHISLITX~$X\ge 3$.] uSTANOVITX~$T\asg\sqrt{(9-2\ln W)/W}$.
uSTANOVITX~$X\asg U\times T$. eSLI~$X>3$, PEREJTI K~\stp{10}; V PROTIVNOM
SLUCHAE USTANOVITX~$X\asg V\times T$. eSLI~$X\ge3$, PEREJTI K~\stp{10};
INACHE VERNUTXSYA K SHAGU~\stp{8}. (pOSLEDNEE PROISHODIT V POLOVINE VSEH
SLUCHAEV, KOGDA VYPOLNYAETSYA DANNYJ SHAG.)

\st[pRISVOITX ZNAK.] eSLI~$\psi=1$, USTANOVITX~$X\asg -X$.
\algend

vESX ALGORITM YAVLYAET SOBOJ VESXMA PRIYATNYJ PRIMER MATEMATICHESKOJ TEORII,
GUSTO SDOBRENNOJ IZOBRETATELXNOSTXYU PROGRAMMISTA. eTO PREKRASNAYA
ILLYUSTRACIYA ISKUSSTVA PROGRAMMIROVANIYA.

tABLICY~$A$, $B$ I~$C$ UZHE BYLI OPISANY. oSTALXNYE TABLICY, NEOBHODIMYE
DLYA ALGORITMA~$M$, STROYATSYA SLEDUYUSHCHIM OBRAZOM;
$$
\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)
$$
[vELICHINY~$a_j$, $b_j$, $p_{j+24}$ OPREDELYAYUTSYA V~(19) I~(20).]

v TABL.~2 ZNACHENIYA PRIVODYATSYA TOLXKO S NESKOLXKIMI ZNACHASHCHIMI CIFRAMI, NO
V NASTOYASHCHEJ PROGRAMME ONI DOLZHNY IMETX TOCHNOSTX, SOOTVETSTVUYUSHCHUYU POLNOMU
MASHINNOMU SLOVU. dLYA VSEH VSPOMOGATELXNYH TABLIC ALGORITMA~M TREBUETSYA 101~MASHINNOE SLOVO.

eTOT METOD CHREZVYCHAJNO BYSTRYJ, TAK KAK 88\%~VREMENI RABOTAYUT TOLXKO
SHAGI~M1, M2 I~M10, OSTALXNYE ZHE SHAGI TAKZHE NE SLISHKOM MEDLENNYE. nA RIS.~9
MY RAZDELILI INTERVAL OT~$0$ DO~$3$ NA 12~CHASTEJ. eSLI BY MY RAZDELILI EGO
NA BOLXSHEE CHISLO CHASTEJ, SKAZHEM~48, PONADOBILISX BY BOLEE DLINNYE TABLICY,
NO ZATO PRI  |TOM V 97\%~SLUCHAEV VYCHISLENIYA OGRANICHIVALISX TOLXKO
%%140
SHAGAMI~M1, M2, M10. pOLNYE TABLICY KAK DLYA DVOICHNYH, TAK I DLYA DESYATICHNYH
MASHIN PRIVODYATSYA V STATXE mARSALXI, mAKLARENA I bR|YA ({\sl CACM,\/} {\bf 7}
(1964), 4--10). tAM DLYA |KONOMII PAMYATI RAZRABOTAN DOPOLNITELXNYJ PRIEM,
SVYAZANNYJ S PEREKRYVANIEM CHASTEJ TABLIC~$A$, $B$, $C$ I~$S$.)

{\sl (3)~mETOD tEJCHROEVA.\/} nORMALXNYE SLUCHAJNYE VELICHINY MOZHNO POLUCHITX
TAKZHE SLEDUYUSHCHIM OBRAZOM. vYRABOTAEM 12~NEZAVISIMYH SLUCHAJNYH CHISEL~$U_1$,
$U_2$,~\dots, $U_{12}$, RAVNOMERNO RASPREDELENNYH MEZHDU NULEM I EDINICEJ.
pOLOZHIM~$R=(U_1+U_2+\cdots+U_{12}-6)/4$. vYCHISLIM
$$
X=((((a_9R^2+a_7)R^2+a_5)R^2+a_3)R^2+a_1)R,
\eqno (22)
$$
GDE
$$
\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)
$$
tAKOE~$X$ BUDET HOROSHIM PRIBLIZHENIEM DLYA NORMALXNOJ SLUCHAJNOJ VELICHINY.
nIKOGDA NE POLUCHAETSYA SLISHKOM BOLXSHIH ZNACHENIJ~$X$, NO S VEROYATNOSTXYU,
MENXSHEJ~$1/50000$, VYRABATYVAYUTSYA ZNACHENIYA, PREVYSHAYUSHCHIE TE, GDE METOD
RABOTAET PRAVILXNO.

mETOD OSNOVAN NA TOM, CHTO $R$~IMEET \emph{PRIBLIZITELXNO} NORMALXNOE
RASPREDELENIE SO SREDNIM ZNACHENIEM NULX I STANDARTNYM
OTKLONENIEM~${1\over4}$. pUSTX~$F_1(x)$---ISTINNOE RASPREDELENIE DLYA~$R$,
a~$F(x)$---NORMALXNOE RASPREDELENIE, OPREDELYAEMOE FORMULOJ~(10).
pOLOZHIM~$X=F^{-1}(F_1(R))$; TAK KAK~$F_1(R)$---RAVNOMERNO RASPREDELENNAYA
SLUCHAJNAYA VELICHINA, $X$~BUDET RASPREDELENA NORMALXNO. fORMULA~(22)
PREDSTAVLYAET PRIBLIZHENIE FUNKCII~$F^{-1}(F_1(R))$ POLINOMOM V
PROMEZHUTKE~$\abs{R}\le 1$.

{\sl (4)~sRAVNENIE METODOV.\/} mY PRIVELI TRI METODA DLYA
VYRABOTKI NORMALXNYH SLUCHAJNYH VELICHIN. mETOD POLYARNYH KOORDINAT DOVOLXNO
MEDLENNYJ, NO OBESPECHIVAET ABSOLYUTNUYU TOCHNOSTX. eGO LEGKO
ZAPROGRAMMIROVATX, ESLI ESTX STANDARTNYE PROGRAMMY DLYA VYCHISLENIYA
KVADRATNOGO KORNYA I LOGARIFMA. mETOD tEJCHROEVA TAKZHE LEGKO PROGRAMMIRUETSYA,
DLYA NEGO NE NUZHNO DRUGIH PODPROGRAMM. pO|TOMU ON NUZHDAETSYA V MENXSHEJ
PAMYATI. mETOD |TOT PRIBLIZHENNYJ, HOTYA DLYA BOLXSHINSTVA PRILOZHENIJ DAET
DOSTATOCHNUYU TOCHNOSTX (OSHIBKA NE PREVYSHAET~$2\times 10^{-4}$
PRI~$\abs{R}\le 1$). mETOD mARSALXI ZNACHITELXNO BYSTREE LYUBYH DRUGIH I
PODOBNO METODU POLYARNYH KOORDINAT IMEET ABSOLYUTNUYU TOCHNOSTX. dLYA NEGO
NEOBHODIMY PODPROGRAMMY KVADRATNOGO KORNYA, LOGARIFMA I POKAZATELXNOJ
FUNKCII I, KROME TOGO, VSPOMOGATELXNYE TABLICY DLYA 100--400~KONSTANT.
pO|TOMU TREBOVANIYA K PAMYATI DOVOLXNO VYSOKIE. oDNAKO NA BOLXSHIH MASHINAH
SKOROSTX METODA
%% 141
\bye
