\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_n0$ 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 $ CHEREZ KO|FFICIENTY fURXE POSLEDOVATELXNOSTI~$\$. \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_n1$---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~$xs+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_tV$, 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