\input style
\chapnotrue\chapno=3\subchno=3\subsubchno=3
МЕНЬШЕЙ ЧЕМ~$(a+6)/m$. тОЧНОЕ ЗНАЧЕНИЕ МОЖНО ЭФФЕКТИВНО ВЫЧИСЛИТЬ С
ПОМОЩЬЮ ВЫРАЖЕНИЯ~(17), ИСПОЛЬЗУЯ ЛЕММЫ~B И~C.
\proofend
иЗ СООТНОШЕНИЯ~(40) ВЫТЕКАЮТ НЕКОТОРЫЕ ЗАСЛУЖИВАЮЩИЕ УПОМИНАНИЯ СЛЕДСТВИЯ.
вО-ПЕРВЫХ, ОНО ДОКАЗЫВАЕТ, ЧТО НАДО ИЗБЕГАТЬ МАЛЫХ ЗНАЧЕНИЙ~$a$. с ДРУГОЙ
СТОРОНЫ, БОЛЬШИЕ ЗНАЧЕНИЯ~$a$ ЕЩЕ НЕ ГАРАНТИРУЮТ ТОГО, ЧТО КОРРЕЛЯЦИЯ
БУДЕТ МАЛА, КАК БЫЛО ПОКАЗАНО В ПРИМЕРЕ~1; ОШИБКА ВЫРАЖЕНИЯ~(40)
МОЖЕТ ДОСТИГАТЬ~$a/m$, И ТОГДА ПРИ БОЛЬШИХ ЗНАЧЕНИЯХ~$a/m$ ПРИБЛИЖЕНИЕ
СТАНОВИТСЯ ПЛОХИМ. еСЛИ~$a\approx\sqrt{m}$, ЗНАЧЕНИЯ КОЭФФИЦИЕНТА
ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ ОГРАНИЧЕНЫ ВЕЛИЧИНОЙ~$2/\sqrt{m}$.

сООТНОШЕНИЕ~(40) ПОМОГАЕТ И ПРИ ВЫБОРЕ ЗНАЧЕНИЯ~$c$. дО СИХ ПОР МЫ ЗНАЛИ
ОТНОСИТЕЛЬНО~$c$ ТОЛЬКО ОДНО: ЧИСЛА~$c$ И~$m$ ДОЛЖНЫ БЫТЬ, ВЗАИМНО
ПРОСТЫМИ. еСЛИ, КРОМЕ ТОГО,
$$
\eqalign{
{c\over m} \approx {1\over 2}-{1\over 6}\sqrt{3}&\approx 0.21132\,48654\,051871 \approx \cr
                                                &\approx {\it (0.15414\,54272\,33746\,34354\,55716)}_8, \cr
}
\eqno(41)
$$
КОЭФФИЦИЕНТ ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ БУДЕТ НЕБОЛЬШИМ, ТАК КАК КОРНИ
УРАВНЕНИЯ~$1-6x+6x^2=0$ РАВНЫ~${1\over 2}\pm{1\over 6}\sqrt{3}$. эТИМ
КРИТЕРИЕМ МОЖНО ПОЛЬЗОВАТЬСЯ, ЕСЛИ ОТСУТСТВУЮТ ДРУГИЕ СООБРАЖЕНИЯ
ОТНОСИТЕЛЬНО ВЫБОРА~$c$.

дО СИХ ПОР РЕЧЬ ШЛА О КОРРЕЛЯЦИИ МЕЖДУ~$X_n$ И~$X_{n+1}$. жЕЛАТЕЛЬНО ТАКЖЕ
ИМЕТЬ НИЗКУЮ КОРРЕЛЯЦИЮ МЕЖДУ~$X_n$ И~$X_{n+2}$, И ВООБЩЕ БЫЛО БЫ НЕПЛОХО,
ЕСЛИ БЫ КОРРЕЛЯЦИЯ МЕЖДУ~$X_n$ И~$X_{n+t}$ БЫЛА НИЗКОЙ, СКАЖЕМ,
ДЛЯ~$1\le t \le 10$. рАНЕЕ БЫЛО ПОКАЗАНО (СМ.\ ФОРМУЛУ~(3.2.1-6)), ЧТО
$$
X_{n+t}=(a_t X_n+c_t) \bmod m,
\eqno(42)
$$
ГДЕ
$$
a_t=a^t \bmod m, \qquad c_t=(a^t-1)c/(a-1)\bmod m.
\eqno(43)
$$
\emph{с ПОМОЩЬЮ ПОДВЕДЕННЫХ ВЫШЕ ФОРМУЛ МОЖНО ВЫЧИСЛИТЬ КОЭФФИЦИЕНТ
КОРРЕЛЯЦИИ МЕЖДУ~$X_n$ И~$X_{n+t}$, ЕСЛИ ВМЕСТО~$a$  И~$c$
ПОДСТАВИТЬ~$a_t$ И~$c_t$.} кОНЕЧНО, $c_t$ УЖЕ НЕ БУДЕТ УДОВЛЕТВОРЯТЬ
УСЛОВИЮ~(41), НО С ЭТИМ ПРИДЕТСЯ СМИРИТЬСЯ.

пРИБЛИЖЕННОЕ ВЫРАЖЕНИЕ~(40) ВПЕРВЫЕ ПОЛУЧИЛ р.~кОВЭЮ ({\sl JACM,\/} {\bf 7}
(1960), 72--74) В РЕЗУЛЬТАТЕ УСРЕДНЕНИЯ ПО ВСЕМ \emph{ДЕЙСТВИТЕЛЬНЫМ
ЧИСЛАМ}~$x$ МЕЖДУ~$0$ И~$m$, А НЕ ТОЛЬКО ПО ЦЕЛЫМ ЗНАЧЕНИЯМ (СМ.~УПР.~21).
мЕТОДЫ, ПОЗВОЛЯЮЩИЕ ПОЛУЧИТЬ ТОЧНЫЙ РЕЗУЛЬТАТ, БЫЛИ ПОЗДНЕЕ РАЗВИТЫ
м.~гРИНБЕРГЕРОМ
({\sl Math. Comp.,\/} {\bf 15} (1961), 383--389) И б.~яНССОНОМ
({\sl BIT,\/} {\bf 4} (1964), 6--27). в ИХ ФОРМУЛАХ СУММЫ дЕДЕКИНДА НЕ
ИСПОЛЬЗОВАЛИСЬ. яНССОН СОСТАВИЛ ТАБЛИЦЫ ДЛЯ КОЭФФИЦИЕНТА ПОСЛЕДОВАТЕЛЬНОЙ
КОРРЕЛЯЦИИ, НО, К СОЖАЛЕНИЮ, ОН РАССМАТРИВАЛ СЛИШКОМ ПРОСТЫЕ МНОЖИТЕЛИ,
%%102
ПОЛЬЗОВАТЬСЯ КОТОРЫМИ НЕ РЕКОМЕНДУЕТСЯ. оН ПОКАЗАЛ НАПРИМЕР, ЧТО
КОЭФФИЦИЕНТ КОРРЕЛЯЦИИ МЕЖДУ~$X_n$ И~$X_{n+t}$ МЕНЬШЕ~$0.000003$ ДЛЯ
ДАТЧИКА С~$m=2^{35}$, $a=2^{24}+5$, $c=1$ ПРИ ВСЕХ~$t\le 2500$. с ПОМОЩЬЮ
СПЕКТРАЛЬНОГО ТЕСТА (СМ.~П.~3.3.4) МОЖНО ПОКАЗАТЬ, ЧТО ПОЛЬЗОВАТЬСЯ ЭТИМ
ДАТЧИКОМ НЕ СЛЕДУЕТ; ТЕМ НЕ МЕНЕЕ РЕЗУЛЬТАТ яНССОНА---ХОРОШЕЕ СВИДЕТЕЛЬСТВО
ТОГО, ЧТО У ВЫБРАННОГО НАУГАД ДАТЧИКА, ОСНОВАННОГО НА ЛИНЕЙНОМ
КОНГРУЭНТНОМ МЕТОДЕ И ОБЛАДАЮЩЕГО ВЫСОКОЙ МОЩНОСТЬЮ, МОЖНО
ОЖИДАТЬ НИЗКУЮ ПОСЛЕДОВАТЕЛЬНУЮ КОРРЕЛЯЦИЮ. [\emph{зАМЕЧАНИЕ.} яНССОН
ТАКЖЕ ПОЛУЧИЛ ФОРМУЛЫ ДЛЯ КОЭФФИЦИЕНТА ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ В
ПОСЛЕДОВАТЕЛЬНОСТЯХ С~$c=0$ И МНОЖИТЕЛЕМ, ОБЕСПЕЧИВАЮЩИМ МАКСИМАЛЬНЫЙ
ПЕРИОД ПРИ~$m=2^e$. эТИ РЕЗУЛЬТАТЫ В СУЩНОСТИ АНАЛОГИЧНЫ РАССМОТРЕННЫМ
В ЭТОЙ КНИГЕ; СМ.~УПР.~3.2.1 2-9.]

сУММЫ дЕДЕКИНДА~$\sigma(h, k, c)$ И ЗАКОН ВЗАИМНОСТИ (ДЛЯ
ЧАСТНОГО СЛУЧАЯ~$c=0$) БЫЛИ ВПЕРВЫЕ РАССМОТРЕНЫ р.~дЕДЕКИНДОМ В~1892~Г.\
В ЕГО РАБОТЕ, ПОСВЯЩЕННОЙ ЭЛЛИПТИЧЕСКИМ ФУНКЦИЯМ. эТА ФУНКЦИЯ
ИСПОЛЬЗОВАЛАСЬ МНОГИМИ АВТОРАМИ; СПИСОК ЛИТЕРАТУРЫ ПО ДАННОМУ ВОПРОСУ
МОЖНО НАЙТИ В РАБОТАХ у.~дИТЕРА
[{\sl Journal f\"ur die reine und angewandte Mathematik,\/} {\bf 201}
(1959), 37--70], А ТАКЖЕ г.~рАДЕМАХЕРА И~э.~уАЙТМЭНА
[{\sl American Journal of Mathematics,\/} {\bf 63} (1941), 377--407].

еЩЕ НЕСКОЛЬКО \emph{АПРИОРНЫХ} ТЕСТОВ БУДЕТ ОПИСАНО В УПРАЖНЕНИЯХ К
ЭТОМУ РАЗДЕЛУ. гЛАВНЫЙ ВЫВОД, КОТОРЫЙ СЛЕДУЕТ ИЗ НИХ, ЗАКЛЮЧАЕТСЯ В
СЛЕДУЮЩЕМ: \emph{МНОЖИТЕЛЬ В ЛИНЕЙНОМ КОНГРУЭНТНОМ МЕТОДЕ ДОЛЖЕН БЫТЬ
ДОСТАТОЧНО ВЕЛИК.} сМ. ТАКЖЕ УПР.~3.3.4-7, ГДЕ ПРИВОДИТСЯ ДАЛЬНЕЙШЕЕ
РАЗВИТИЕ ТЕОРЕМЫ~P.

\excercises (первая часть)
\ex[м07] оБЎЯСНИТЕ, ПОЧЕМУ ВЫРАЖЕНИЕ~(7) РАВНО ЧИСЛУ ЗНАЧЕНИЙ~$x$,
ДЛЯ КОТОРЫХ~$s(x)<x$, $0\le x < m$.

\ex[м24] дОКАЖИТЕ СПРАВЕДЛИВОСТЬ СООТНОШЕНИЯ~(12)

\ex[вм22] рАЗЛОЖИТЕ В РЯД фУРЬЕ (ВЫРАЗИТЕ ЧЕРЕЗ СИНУСЫ И КОСИНУСЫ)
ФУНКЦИЮ~$f(x)=\dlp x \drp$.

\rex[м18] кАКОВО НАИБОЛЬШЕЕ ВОЗМОЖНОЕ ЗНАЧЕНИЕ~$d$ (В ОБОЗНАЧЕНИЯХ
ТЕОРЕМЫ~P), ЕСЛИ~$m=10^{10}$, А МОЩНОСТЬ ДАТЧИКА РАВНА~$10$?

\ex[M21] вЫВЕДИТЕ ФОРМУЛУ~(17).

\ex[м27] пУСТЬ~$hh'+kk'=1$ (a)~пОКАЖИТЕ, НЕ ПОЛЬЗУЯСЬ ЛЕММАМИ~B И~C, ЧТО
$$
\sigma(h, k, c)=\sigma(h, k, 0)+12\sum_{0\le j < c}\dlp{h' j \over k} \drp + 6 \dlp {h' c \over k} \drp
$$
ДЛЯ ВСЕХ~$c\ge 0$. (b)~пОКАЖИТЕ, ЧТО ПРИ~$0 \le c < h$ И~$0 \le c < k$
$$
\dlp {h' c \over k} \drp + \dlp {k' c \over h} \drp = {c \over hk}.
$$
(c)~в ПРЕДПОЛОЖЕНИЯХ ЛЕММЫ~B ПОКАЖИТЕ СПРАВЕДЛИВОСТЬ РАВЕНСТВА~(20).

\rex[м24] пРЕДЛОЖИТЕ ДОКАЗАТЕЛЬСТВО ЗАКОНА ВЗАИМНОСТИ~(19) ПРИ~$c=0$,
ОСНОВАННОЕ НА ИДЕЯХ УПР.~1.2.4-45.

%% 103
\rex[M34] пУСТЬ
$$
\rho(p, q, r)=12 \sum_{0\le j < r} \dlp{jp\over r}\drp \dlp{jq\over r}\drp.
$$
оБОБЩАЯ МЕТОД, ИСПОЛЬЗОВАННЫЙ ПРИ ДОКАЗАТЕЛЬСТВЕ ЛЕММЫ~B, ДОКАЖИТЕ
СЛЕДУЮЩЕЕ КРАСИВОЕ СООТНОШЕНИЕ (ПОЛУЧЕННОЕ рАДЕМАХЕРОМ): "еСЛИ~$p$, $q$
И~$r$ ПОПАРНО ВЗАИМНО ПРОСТЫ, ТО
$$
\rho(p, q, r)+\rho(q, r, p)+\rho(r, p, q)={p\over qr}+{q\over rp}+{r\over pq}=3."
$$
(зАКОН ВЗАИМНОСТИ ДЛЯ СУММ  дЕДЕКИНДА ПРИ~$c=0$ ЯВЛЯЕТСЯ ЧАСТНЫМ
СЛУЧАЕМ ЭТОГО РАВЕНСТВА ПРИ~$r=1$.)

\ex[M40] сУЩЕСТВУЕТ ЛИ ПРОСТОЕ ДОКАЗАТЕЛЬСТВО СООТНОШЕНИЯ
рАДЕМАХЕРА (СМ.~УПР.~8), КОТОРОЕ ЯВЛЯЕТСЯ ЧАСТНЫМ СЛУЧАЕМ ДОКАЗАТЕЛЬСТВА,
РАССМОТРЕННОГО В УПР.~7?

\ex[м20] дОКАЖИТЕ СООТНОШЕНИЯ~(34) ОБ ИЗМЕНЕНИИ ЗНАКА ПАРАМЕТРОВ, ВХОДЯЩИХ
В~$\sigma(h, k, c)$.

\ex[M30] фОРМУЛЫ В ТЕКСТЕ ДАЮТ ВОЗМОЖНОСТЬ ВЫЧИСЛИТЬ~$\sigma(h, k, c)$,
КОГДА~$h$ И~$k$ ВЗАИМНО ПРОСТЫ. в ОБЩЕМ СЛУЧАЕ ПОЛОЖИМ~$hh'\equiv d \pmod{k}$,
ГДЕ~$d$---НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ~$h$ И~$k$. пОКАЖИТЕ, ЧТО
$$
\sigma(h, k, c)=\sigma(h/d, k/d, \floor{c/d})+\delta,
$$
ГДЕ~$\delta=0$ ПРИ~$c \bmod d =0$ И
$$
\delta=6\dlp{\floor{c/d} h'd \over k}\drp
$$
ПРИ~$c\bmod d\ne 0$.

\ex[м24] пОКАЖИТЕ, ЧТО ЕСЛИ~$h$ И~$k$ ВЗАИМНО ПРОСТЫ,
ТО~$\abs{\sigma(h, k, c)}<(k-1)(k-2)/k$.

\ex[м22] в~(37) ПРИВЕДЕНО \emph{ПРИБЛИЖЕННОЕ} ЗНАЧЕНИЕ ДЛЯ КОЭФФИЦИЕНТА
ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ ПРИ~$m=2^{35}$, $a=2^{34}+1$, $c=1$. чЕМУ
РАВНО ТОЧНОЕ ЗНАЧЕНИЕ?

\rex[м24] пРИ ПРОВЕРКЕ ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ У ЛИНЕЙНОГО
КОНГРУЭНТНОГО ДАТЧИКА С~$m=2^{35}$, $a=2^{18}+1$, $c=1$ БЫЛИ ИССЛЕДОВАНЫ
ТРИ ОТРЕЗКА ПОСЛЕДОВАТЕЛЬНОСТИ ПО 1000~ЧИСЕЛ В КАЖДОМ; ВО ВСЕХ СЛУЧАЯХ
КОЭФФИЦИЕНТ КОРРЕЛЯЦИИ ПОЛУЧИЛСЯ ДОВОЛЬНО БОЛЬШИМ: ОТ~$0.2$ ДО~$0.3$.
кАКИМ БУДЕТ КОЭФФИЦИЕНТ ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ ДЛЯ ЭТОГО ДАТЧИКА ПО
ВСЕМУ ПЕРИОДУ В $2^{35}$~ЧИСЕЛ?

\ex[м22] оПРЕДЕЛИТЕ ТОЧНОЕ ЗНАЧЕНИЕ КОЭФФИЦИЕНТА
ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ В ЧАСТНОМ СЛУЧАЕ~$a=1$.

\ex[м24] кАК МЫ УЖЕ ЗНАЕМ, ЛИНЕЙНЫЙ, КОНГРУЭНТНЫЙ МЕТОД ДАЕТ
ПЛОХИЕ СЛУЧАЙНЫЕ ЧИСЛА ПРИ~$a=1$. пОКАЖИТЕ С ПОМОЩЬЮ ТЕОРЕМЫ~P, ЧТО,
НЕСМОТРЯ НА ЭТО, МОЖНО ПОДОБРАТЬ ТАКОЕ С, ЧТО ВЕРОЯТНОСТЬ ВЫПОЛНЕНИЯ
НЕРАВЕНСТВА~$(X_{n+1}<X_n)$ БУДЕТ ОЧЕНЬ БЛИЗКА К~$1/2$ ДАЖЕ ПРИ~$a=1$.
мОЖНО ТАКЖЕ ПОДОБРАТЬ ТАКОЕ~$c$, ЧТО КОЭФФИЦИЕНТ ПОСЛЕДОВАТЕЛЬНОЙ
КОРРЕЛЯЦИЯ БУДЕТ ОЧЕНЬ НИЗКИМ. мОЖНО ЛИ ВЫБРАТЬ ЗНАЧЕНИЕ~$c$ ТАК, ЧТОБЫ
ВЫПОЛНЯЛИСЬ ОБА ЭТИ УСЛОВИЯ ОДНОВРЕМЕННО?

\ex[M21] оБЎЯСНИТЕ, КАК ВЫБРАТЬ ТАКОЕ ЗНАЧЕНИЕ~$a$, ЧТОБЫ КАК~$c$, ТАК
И~$c_2$ УДОВЛЕТВОРЯЛИ ПРИБЛИЖЕННОМУ СООТНОШЕНИЮ~(41), ГДЕ~$c_2$---ПРИРАЩЕНИЕ
ПОСЛЕДОВАТЕЛЬНОСТИ, ЗАДАННОЕ~(43).

\rex[M35] пОЛОЖИМ
$$
S(h, k, c, z)=\sum_{0\le j <z}\dlp{hj+c\over k}\drp.
$$
пРИ ВЗАИМНО ПРОСТЫХ~$h$ И~$k$ ПОЛУЧИТЕ "ФОРМУЛЫ ВЗАИМНОСТИ", КОТОРЫЕ
ПОМОГУТ ЭФФЕКТИВНО ВЫЧИСЛЯТЬ ЗНАЧЕНИЯ ЭТОЙ ФУНКЦИИ, ПОДОБНО ТОМУ, КАК С
ПОМОЩЬЮ ЛЕММ~B И~C ВЫЧИСЛЯЮТСЯ ЗНАЧЕНИЯ~$\sigma(h, k, c)$.
[\emph{уКАЗАНИЕ:} СМ.~УПР.~6.]

%% 104
\rex[M35] \emph{пРОВЕРКУ СЕРИЙ,} ОПИСАННУЮ В ПРЕДЫДУЩЕМ РАЗДЕТО МОЖНО
ПРОВОДИТЬ НА ПОЛНОМ ПЕРИОДЕ. пУСТЬ~$\alpha$, $\beta$, $\gamma$,
$\delta$---ЦЕЛЫЕ ЧИСЛА, ПРИЧЕМ~$0\le\alpha<\beta\le m$,
$0\le\gamma<\delta\le m$. вЫВЕДИТЕ СООТНОШЕНИЕ ДЛЯ ВЕРОЯТНОСТИ ТОГО,
ЧТО~$\alpha\le X_n<\beta$ И~$\gamma\le X_{n+1}<\delta$.

\ex[M24] оБОБЩИТЕ~(26) ТАКИМ oБРАЗОМ, ЧТОБЫ ПОЛУЧАЛОСЬ ВЫРАЖЕНИЕ ДЛЯ~$\sigma(h, k, c)$.

\excercises (вторая часть)
вО МНОГИХ СЛУЧАЯХ ТОЧНЫЕ РАСЧЕТЫ С ЦЕЛЫМИ ЧИСЛАМИ СЛИШКОМ СЛОЖНЫ, ОДНАКО
МОЖНО ПОПЫТАТЬСЯ ПРИ ОПРЕДЕЛЕНИИ ВЕРОЯТНОСТЕЙ ПРОВОДИТЬ УСРЕДНЕНИЕ НЕ ПО
ЦЕЛЫМ ЗНАЧЕНИЯМ, А ПО ВСЕМУ ИНТЕРВАЛУ ИЗМЕНЕНИЯ~$x$. хОТЯ ТАКИЕ РЕЗУЛЬТАТЫ
БУДУТ ПРИБЛИЖЕННЫМИ, ОНИ ПРОЛЬЮТ СВЕТ НА ОБСУЖДАЕМЫЙ ПРЕДМЕТ.

уДОБНЕЕ ВСЕГО ИМЕТЬ ДЕЛО С ЧИСЛАМИ~$U_n$, ЗАКЛЮЧЕННЫМИ МЕЖДУ НУЛЕМ
И ЕДИНИЦЕЙ; ДЛЯ ЛИНЕЙНЫХ КОНГРУЭНТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ~$U_n=X_n/m$, ТАК
ЧТО~$U_{n+1}=\{aU_n+\theta\}$, ГДЕ~$\theta=c/m$, А~$\{x\}$ ОЗНАЧАЕТ~$x\bmod 1$.
нАПРИМЕР, ФОРМУЛА ДЛЯ КОЭФФИЦИЕНТА ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ
ПРИНИМАЕТ ВИД
$$
C=\left(\int_0^1 x\{ax+\theta\}\,dx-\left(\int_0^1 x\, dx\right)^2\right)
\bigg/ \left(\int_0^1 x^2\, dx-\left(\int_0^1 x\,dx\right)^2\right).
$$

\rex[BM23] (р. кОВЭЮ.) чЕМУ РАВНО~$C$ В ТОЛЬКО ЧТО ПРИВЕДЕННОЙ ФОРМУЛЕ?

\rex[M22] пУСТЬ~$a$---ЦЕЛОЕ ЧИСЛО И~$0\le\theta<1$.
еСЛИ~$x$---ДЕЙСТВИТЕЛЬНОЕ ЧИСЛО, НАХОДЯЩЕЕСЯ МЕЖДУ~$0$ И~$1$,
А~$s(x)=\{ax+\theta\}$, ТО КАКОВА ВЕРОЯТНОСТЬ, ЧТО~$s(x)<x$? (эТО АНАЛОГ
ТЕОРЕМЫ~P ДЛЯ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ.)

\ex[M28] пРЕДЫДУЩЕЕ УПРАЖНЕНИЕ ДАЕТ ВЕРОЯТНОСТЬ ТОГО, ЧТО~$U_{n+1}<U_n$.
кАКОВА ВЕРОЯТНОСТЬ ТОГО, ЧТО~$U_{n+2}<U_{n+1}<U_n$, ЕСЛИ~$U_n$---СЛУЧАЙНЫЕ
ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА,  ЗАКЛЮЧЕННЫЕ МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ?

\ex[M29] сОХРАНЯЯ УСЛОВИЯ ПРЕДЫДУЩЕЙ ЗАДАЧИ И ПОЛОЖИВ~$\theta=0$, ПОКАЖИТЕ,
 ЧТО ВЕРОЯТНОСТЬ ВЫПОЛНЕНИЯ НЕРАВЕНСТВ~$U_n>U_{n+1}>\cdots>U_{n+t-1}$ В
ТОЧНОСТИ РАВНА
$$
{1\over t!}\left(1+{1\over a}\right)\ldots\left(1+{t-2\over a}\right).
$$
кАКОВА СРЕДНЯЯ ДЛИНА УБЫВАЮЩЕГО РЯДА ЧИСЕЛ, НАЧИНАЮЩЕГОСЯ СО
СЛУЧАЙНО ВЫБРАННОГО МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ ЧИСЛА~$U_n$?

\rex[M25] пУСТЬ~$\alpha$, $\beta$, $\gamma$, $\delta$---ДЕЙСТВИТЕЛЬНЫЕ
ЧИСЛА, ПРИЧЕМ~$0\le\alpha<\beta\le1$, $0\le \gamma<\delta\le 1$. кАКОВА
ВЕРОЯТНОСТЬ ТОГО, ЧТО~$\alpha\le x < \beta$ И~$\gamma\le s(x)<\delta$,
ЕСЛИ ВЫПОЛНЕНЫ ПРЕДПОЛОЖЕНИЯ УПР.~22?  (эТО АНАЛОГ УПР.~19 ДЛЯ
ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ.)

\ex[M21] рАССМОТРИМ ДАТЧИК, ОСНОВАННЫЙ НА МЕТОДЕ фИБОНАЧЧИ
С~$U_{n+1}=\{U_n+U_{n-1}\}$. пРЕДПОЛАГАЯ, ЧТО~$U_1$ И~$U_2$ ВЫБИРАЮТСЯ
НЕЗАВИСИМО СЛУЧАЙНЫМ ОБРАЗОМ МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ, НАЙДИТЕ ВЕРОЯТНОСТЬ
ТОГО, ЧТО~$U_1<U_2<U_3$, $U_1<U_3<U_2$, $U_2<U_1<U_3$ И~Т.~Д.
[\emph{уКАЗАНИЕ:} РАЗДЕЛИТЬ "ЕДИНИЧНЫЙ КВАДРАТ", Т.~Е.\ ТОЧКИ НА
ПЛОСКОСТИ~$\{\,(x, y) \mid 0\le x, y<1\,\}$, НА ШЕСТЬ ЧАСТЕЙ, В
ЗАВИСИМОСТИ ОТ СООТНОШЕНИЯ МЕЖДУ~$x$, $y$ И~$\{x+y\}$, И ОПРЕДЕЛИТЬ
ПЛОЩАДЬ КАЖДОЙ ЧАСТИ.]

\ex[M27] пУСТЬ ИСХОДНЫЕ ЧИСЛА ДЛЯ ДАТЧИКА, ОПИСАННОГО В ПРЕДЫДУЩЕМ
УПРАЖНЕНИИ, ВЫБИРАЮТСЯ НЕЗАВИСИМО В ЕДИНИЧНОМ КВАДРАТЕ, ПОСЛЕ ЧЕГО БОЛЬШЕЕ
ИЗ НИХ БЕРЕТСЯ В КАЧЕСТВЕ~$U_0$, А МЕНЬШЕЕ---$U_1$. оПРЕДЕЛИТЕ ВЕРОЯТНОСТЬ
ТОГО, ЧТО~$U_1$ ОКАЖЕТСЯ НАЧАЛЬНОЙ ТОЧКОЙ ВОЗРАСТАЮЩЕГО РЯДА ДЛИНЫ~$k$,
Т.~Е.~$U_0>U_1<\ldots<U_k>U_{k+1}$. сРАВНИТЕ РЕЗУЛЬТАТ С СООТВЕТСТВУЮЩИМИ
ВЕРОЯТНОСТЯМИ ДЛЯ СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ.

\rex[M35] дЛЯ ЛИНЕЙНОГО КОНГРУЭНТНОГО ДАТЧИКА МОЩНОСТИ~$2$ ВЫПОЛНЯЕТСЯ
УСЛОВИЕ~$X_{n-1}-2X_n+X_{n+1}\equiv (a-1)c \pmod{m}$
(СМ.~ФОРМУЛУ~(3.2.1.3-5)). рАССМОТРИТЕ ДАТЧИК, КОТОРЫЙ ЯВЛЯЕТСЯ
НЕПРЕРЫВНЫМ АНАЛОГОМ, ПОЛОЖИВ~$U_{n+1}=\{\alpha+2U_n-U_{n-1}\}$. тАК ЖЕ
КАК В УПР.~26, РАЗДЕЛИТЕ ЕДИНИЧНЫЙ КВАДРАТ
%% 105
НА ЧАСТИ, ДОКАЗЫВАЮЩИЕ ВОЗМОЖНЫЕ СООТНОШЕНИЯ МЕЖДУ~$U_{n-1}$,
$U_n$И~$U_{n+1}$ ДЛЯ КАЖДОЙ ПАРЫ~$(U_{n-1}, U_n)$. сУЩЕСТВУЕТ ЛИ
ЗНАЧЕНИЕ~$\alpha$, ПРИ КОТОРОМ КАЖДОЕ ИЗ ШЕСТИ ВОЗМОЖНЫХ СООТНОШЕНИЙ МЕЖДУ
ЭТИМИ ЧИСЛАМИ ОСУЩЕСТВЛЯЕТСЯ С ВЕРОЯТНОСТЬЮ~$1/6$, ЕСЛИ~$U_{n-1}$ И~$U_n$
ВЫБИРАЮТСЯ СЛУЧАЙНО В ЕДИНИЧНОМ
КВАДРАТЕ?

\subsubchap{сПЕКТРАЛЬНЫЙ ТЕСТ} % 3.3.4
вАЖНЫЙ ТЕСТ ДЛЯ ПРОВЕРКИ СЛУЧАЙНОСТИ ПОЛУЧЕННЫХ НА эвм ЧИСЛОВЫХ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ СФОРМУЛИРОВАЛИ В 1965~Г.\ р.~кОВЭЮ И~р.~мАКФЕРСОН.
эТОТ ТЕСТ ЗАМЕЧАТЕЛЕН ТЕМ, ЧТО ВСЕ ИЗВЕСТНЫЕ ПЛОХИЕ ДАТЧИКИ, ОСНОВАННЫЕ
НА ЛИНЕЙНОМ КОНГРУЭНТНОМ МЕТОДЕ, БЫЛИ ИМ \emph{ЗАБРАКОВАНЫ,} В ТО ВРЕМЯ,
КАК ВСЕ ХОРОШИЕ ДАТЧИКИ ПРОШЛИ УДОВЛЕТВОРИТЕЛЬНО! бЕЗУСЛОВНО, ЭТО НАИБОЛЕЕ
СОВЕРШЕННЫЙ ИЗ ИМЕЮЩИХСЯ ТЕСТОВ, В СВЯЗИ С ЧЕМ ОН ЗАСЛУЖИВАЕТ ОСОБОГО ВНИМАНИЯ.

сПЕКТРАЛЬНЫЙ ТЕСТ ОБЛАДАЕТ СВОЙСТВАМИ КАК "ЭМПИРИЧЕСКИХ", ТАК И
"ТЕОРЕТИЧЕСКИХ" ТЕСТОВ, РАССМОТРЕННЫХ В ПРЕДЫДУЩИХ РАЗДЕЛАХ. кАК И В
ТЕОРЕТИЧЕСКИХ ТЕСТАХ, В НЕМ РАССМАТРИВАЮТСЯ ВЕЛИЧИНЫ, УСРЕДНЕННЫЕ ПО ВСЕМУ
ПЕРИОДУ. с ДРУГОЙ СТОРОНЫ, ДЛЯ ПОЛУЧЕНИЯ РЕЗУЛЬТАТОВ ИСПЫТАНИЙ ТРЕБУЮТСЯ
МАШИННЫЕ РАСЧЕТЫ, ЧТО ДЕЛАЕТ ЕГО ПОХОЖИМ НА ЭМПИРИЧЕСКИЕ ТЕСТЫ.

оБОСНОВАНИЕ ЭТОГО ТЕСТА ТРЕБУЕТ ИСПОЛЬЗОВАНИЯ МАТЕМАТИКИ В ЗНАЧИТЕЛЬНЫХ
ДОЗАХ. чИТАТЕЛЮ БЕЗ ОСОБОЙ СКЛОННОСТИ К МАТЕМАТИКЕ РЕКОМЕНДУЕТСЯ ПЕРЕЙТИ
ПРЯМО К ПОДПУНКТУ~D ДАННОГО ПУНКТА, ГДЕ ПРИВОДИТСЯ ОПИСАНИЕ ВПОЛНЕ
КОНКРЕТНОГО СПЕКТРАЛЬНОГО ТЕСТА.

\section{A.~тЕОРИЯ, ЛЕЖАЩАЯ В ОСНОВЕ ТЕСТА}. мАТЕМАТИЧЕСКИМ ОБОСНОВАНИЕМ
СПЕКТРАЛЬНОГО ТЕСТА СЛУЖИТ "КОНЕЧНОЕ ПРЕОБРАЗОВАНИЕ фУРЬЕ" ФУНКЦИИ,
ОПРЕДЕЛЕННОЙ НА КОНЕЧНОМ МНОЖЕСТВЕ. оДНОМЕРНЫЙ СЛУЧАЙ КОНЕЧНОГО
ПРЕОБРАЗОВАНИЯ фУРЬЕ УЖЕ ИСПОЛЬЗОВАЛСЯ В ПРЕДЫДУЩЕМ РАЗДЕЛЕ ПРИ
ДОКАЗАТЕЛЬСТВЕ ЛЕММЫ~3.3.3~B; РАССМОТРИМ ТЕПЕРЬ ТЕХНИКУ ПРЕОБРАЗОВАНИЯ
фУРЬЕ В ОБЩЕМ СЛУЧАЕ.

дЛЯ ЛЮБОЙ ПРИНИМАЮЩЕЙ КОМПЛЕКСНЫЕ ЗНАЧЕНИЯ
ФУНКЦИИ~$F(t_1, t_2,~\ldots, t_n)$, ОПРЕДЕЛЕННОЙ ДЛЯ ВСЕХ КОМБИНАЦИЙ ЦЕЛЫХ
ЧИСЕЛ~$t_k$, ГДЕ~$0\le t_k < m$ ПРИ~$1\le k \le n$, ВВЕДЕМ
\dfn{ПРЕОБРАЗОВАНИЕ фУРЬЕ}
$$
f(s_1, s_2, \ldots, s_n)=
\sum_{0\le t_1,\ldots, t_n<m} \exp\left({-2\pi i \over m}
(s_1t_1+\cdots+s_nt_n)\right) F(t_1, \ldots, t_n).
\eqno(1)
$$

фУНКЦИЯ~$f$ ОПРЕДЕЛЕНА ДЛЯ ВСЕХ КОМБИНАЦИЙ ЦЕЛЫХ~$s_k$; ЭТО ПЕРИОДИЧЕСКАЯ
ФУНКЦИЯ В ТОМ СМЫСЛЕ,
ЧТО~$f(s_1,~\ldots, s_n)=f(s_1 \bmod m,~\ldots, s_n \bmod m)$. чТОБЫ
СВЯЗАТЬ ЭТО ОПРЕДЕЛЕНИЕ С
%% 106
ФОРМУЛАМИ ПРЕДЫДУЩЕГО РАЗДЕЛА, ОТМЕТИМ, ЧТО
$$
\exp\left({-2\pi i \over m} (s_1 t_1 + s_2 t_2 + \cdots + s_n t_n)\right)
=\omega^{-(s_1t_1+s_2t_2+\cdots+s_nt_n)},
$$
ЕСЛИ~$\omega=e^{2\pi i/m}$---КОРЕНЬ $m\hbox{-Й}$~СТЕПЕНИ ИЗ ЕДИНИЦЫ.
тЕРМИН "ПРЕОБРАЗОВАНИЕ" В ДАННОМ СЛУЧАЕ ОПРАВДАН, ТАК КАК ИСХОДНУЮ
ФУНКЦИЮ~$F(t_1,~\ldots, t_n)$ МОЖНО ВОССТАНОВИТЬ ПО ЕЕ
ПРЕОБРАЗОВАНИЮ~$f(s_1,~\ldots, s_n)$ И ПРЕДСТАВИТЬ В СЛЕДУЮЩЕМ ВИДЕ (СМ.~УПР.~1):
$$
F(t_1,~\ldots, t_n)={1\over m^n}\sum_{0\le s_1, \ldots, s_n<m}
\exp\left({2\pi i\over m} (s_1t_1+\cdots+s_nt_n)\right) f(s_1,~\ldots, s_n).
\eqno(2)
$$
эТУ ФОРМУЛУ МОЖНО ЗАПИСАТЬ, ИСПОЛЬЗУЯ СИНУСЫ И КОСИНУСЫ ДЛЯ БОЛЬШЕГО
СХОДСТВА С БЕСКОНЕЧНЫМИ РЯДАМИ фУРЬЕ. вЕЛИЧИНА~$(1/m^n)f(s_1,~\ldots, s_n)$
ЯВЛЯЕТСЯ АМПЛИТУДОЙ $n\hbox{-МЕРНОЙ}$ КОМПЛЕКСНОЙ ПЛОСКОЙ ВОЛНЫ С
ЧАСТОТАМИ~$s_1/m$,~\dots, $s_n/m$, ЕСЛИ~$F(t_1,~\ldots, t_n)$ ПРЕДСТАВЛЕНА
В ВИДЕ~(2).

иЗ СООТНОШЕНИЙ~(1) И~(2) СЛЕДУЕТ, ЧТО ТЕОРЕТИЧЕСКИ МОЖНО ОПРЕДЕЛИТЬ ЛЮБЫЕ
СВОЙСТВА~$F$ ПО ЕЕ ПРЕОБРАЗОВАНИЮ~$f$, И НАОБОРОТ. чАСТО БЫВАЕТ УДОБНЕЕ
РАБОТАТЬ С ПРЕОБРАЗОВАНИЕМ фУРЬЕ ФУНКЦИИ, А ЗАТЕМ ПРОИЗВЕСТИ ОБРАТНОЕ
ПРЕОБРАЗОВАНИЕ, ЧТОБЫ ВЫВЕСТИ НЕОЧЕВИДНЫЕ СВОЙСТВА ИСХОДНОЙ ФУНКЦИИ.

пОПРОБУЕМ ПРИМЕНИТЬ ЭТУ КОНЦЕПЦИЮ К ПРОБЛЕМЕ ВЫРАБОТКИ СЛУЧАЙНЫХ ЧИСЕЛ.
пУСТЬ ЗАДАНА БЕСКОНЕЧНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ЦЕЛЫХ ЧИСЕЛ $X_0$, $X_1$,
$X_2$,~\dots, ПРИЧЕМ~$0\le X_k < m$, И ПУСТЬ~$n$---ФИКСИРОВАННОЕ (ОБЫЧНО
НЕБОЛЬШОЕ) ПОЛОЖИТЕЛЬНОЕ ЦЕЛОЕ ЧИСЛО. оПРЕДЕЛИМ
$$
F(t_1, \ldots, t_n)=\lim_{N\to\infty} {1\over N}
\sum_{0\le k <N} \delta_{X_k t_1} \delta_{X_{k+1}t_2} \ldots\delta_{X_{k+n-1}t_n}.
\eqno(3)
$$
эТА ФУНКЦИЯ РАВНА ПРЕДЕЛЬНОЙ ПЛОТНОСТИ ЧИСЛА ПОЯВЛЕНИЙ
КОМБИНАЦИИ~$(t_1,~\ldots, t_n)$ В ВИДЕ $n$~СЛЕДУЮЩИХ ДРУГ ЗА ДРУГОМ ЭЛЕМЕНТОВ
ПОСЛЕДОВАТЕЛЬНОСТИ~$X_0$, $X_1$, $X_2$,~$\ldots\,$. тАК КАК НАС ИНТЕРЕСУЮТ
ПЕРИОДИЧЕСКИЕ ПОСЛЕДОВАТЕЛЬНОСТИ~$X_0$, $X_1$, $X_2$,~\dots, МОЖНО СЧИТАТЬ,
ЧТО ПРЕДЕЛ В~(3) СУЩЕСТВУЕТ, ПРИЧЕМ ДЛЯ ВЫЧИСЛЕНИЯ ПРЕДЕЛА МОЖНО
ВЗЯТЬ~$N$ РАВНЫМ ДЛИНЕ ПЕРИОДА. в ДЕЙСТВИТЕЛЬНО СЛУЧАЙНОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ С РАВНОМЕРНЫМ РАСПРЕДЕЛЕНИЕМ ЛЮБЫЕ КОМБИНАЦИИ ИЗ
$t$~ЧИСЕЛ ДОЛЖНЫ ПОЯВЛЯТЬСЯ С ОДИНАКОВОЙ ЧАСТОТОЙ, ТАК ЧТО
$F(t_1,~\ldots, t_n)$~ДОЛЖНО БЫТЬ РАВНО~$1/m^n$ ДЛЯ ЛЮБЫХ~$t_1$,~\dots, $t_n$.

пРОИЗВОДЯ ПРЕОБРАЗОВАНИЕ фУРЬЕ ФУНКЦИИ~(3), ПОЛУЧИМ
$$
f(s_1,~\ldots, s_n)=\lim_{N\to\infty}{1\over N}\sum_{0\le k < N}
\exp\left({-2\pi i \over m}(s_1 X_k+s_2X_{k+1}+\cdots+s_n X_{k+n-1})\right).
\eqno(4)
$$
%% 107
кОГДА МЫ ИМЕЕМ ДЕЛО С ДЕЙСТВИТЕЛЬНО СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТЬЮ, ДОЛЖЕН
ПОЛУЧИТЬСЯ ОБРАЗ КОНСТАНТЫ~$1/m^n$; ТАК ЧТО \emph{ДЛЯ СЛУЧАЙНОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ МЫ ДОЛЖНЫ ПОЛУЧИТЬ}
$$
f(s_1,~\ldots, s_n)=\cases{
 1, & ЕСЛИ $s_1\equiv \cdots \equiv s_n \equiv 0 \pmod{m}$; \cr
 0 & В ПРОТИВНОМ СЛУЧАЕ.\cr
}
\eqno(5)
$$

в ТЕОРЕТИЧЕСКИХ ТЕСТАХ, РАССМОТРЕННЫХ РАНЕЕ, ИСПОЛЬЗУЮТСЯ СРЕДНИЕ ЗНАЧЕНИЯ
ПО ПОЛНОМУ ПЕРИОДУ. дЛЯ ОПРЕДЕЛЕНИЯ СРЕДНЕГО ОТ КАКОЙ-ЛИБО ФУНКЦИИ,
ЗАВИСЯЩЕЙ ОТ~$n$ СЛЕДУЮЩИХ ДРУГ ЗА ДРУГОМ ЭЛЕМЕНТОВ, ДОСТАТОЧНО В
ПРИНЦИПЕ ЗНАТЬ~$F(t_1,~\ldots, t_n)$. нАПРИМЕР, ВЕРОЯТНОСТЬ ТОГО,
ЧТО~$X_k<X_{k+1}$, РАВНА ВЕЛИЧИНЕ~$F(t_1, t_2)$, ПРОСУММИРОВАННОЙ ПО
ВСЕМ~$0\le t_1 < t_2 < m$; ТОЧНО ТАК ЖЕ СЛУЧАЙ~$n=2$ ПОЗВОЛЯЕТ ОПРЕДЕЛИТЬ
КОЭФФИЦИЕНТ ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ (СМ.~УПР.~5).

тАК КАК ОБРАЗ~$f(s_1,~\ldots, s_n)$ СОДЕРЖИТ В СЕБЕ ВСЮ
ИНФОРМАЦИЮ ОБ~$F(t_1,~\ldots, t_n)$, ЕГО ТАКЖЕ МОЖНО ИСПОЛЬЗОВАТЬ В
\emph{ЛЮБОМ} ТЕОРЕТИЧЕСКОМ ТЕСТЕ. сЛЕДОВАТЕЛЬНО, МОЖНО ОЖИДАТЬ, ЧТО
ВЕЛИЧИНУ ОТКЛОНЕНИЯ~$f(s_1,~\ldots, s_n)$ ОТ ЗНАЧЕНИЙ~(5), ОТВЕЧАЮЩИХ
ДЕЙСТВИТЕЛЬНО СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ, МОЖНО ИСПОЛЬЗОВАТЬ
ДЛЯ ПРОВЕРКИ СЛУЧАЙНОСТИ.

дЛЯ ЛИНЕЙНЫХ КОНГРУЭНТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ~$f(s_1,~\ldots, s_n)$ ИМЕЕТ
ОЧЕНЬ ПРОСТОЙ ВИД, ЧЕГО НЕЛЬЗЯ СКАЗАТЬ ОБ~$F(t_1,~\ldots, t_n)$.
рАССМОТРИМ ЛИНЕЙНУЮ КОНГРУЭНТНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ С ПАРАМЕТРАМИ~$a$,
$m$, $c$ И~$X_0$, ИМЕЮЩУЮ \emph{МАКСИМАЛЬНУЮ ДЛИНУ ПЕРИОДА} В СООТВЕТСТВИИ
С ТЕОРЕМОЙ~3.2.1.2а. дЛЯ ТАКОЙ ПОСЛЕДОВАТЕЛЬНОСТИ
$$
\eqalignno{
f(s_1,~\ldots, s_n)&={1\over m}
 \sum_{0\le k < m} \exp\left({-2\pi i \over m} (s_1 X_k+s_2 X_{k+1}+\cdots+s_n X_{k+n-1})\right)=\cr
&={1\over m}
 \sum_{0\le k < m} \exp\left({-2\pi i \over m}\left(s(a)X_k+{s(a)-s(1)\over a-1} c \right) \right), & (6) \cr
}
$$
ГДЕ
$$
s(a)=s_1+s_2 a+ s_3 a^2+\cdots+s_n a^{n-1},
\eqno(7)
$$
ТАК КАК
$$
X_{k+r}\equiv a^r X_k+{a^r-1\over a-1} c \pmod{m}
$$
СОГЛАСНО ФОРМУЛЕ~(3.2.1-6). мЫ ПРЕДПОЛОЖИЛИ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ ИМЕЕТ
МАКСИМАЛЬНЫЙ ПЕРИОД, ТАК ЧТО В НЕЙ ВСТРЕЧАЮТСЯ ВСЕ ЗНАЧЕНИЯ~$X_k$;
СЛЕДОВАТЕЛЬНО, (6) СВОДИТСЯ К
$$
{1\over m} \sum_{0\le k <m}
 \exp\left({-2\pi i \over m}\left(s(a)k+{s(a)-s(1)\over a-1} c\right)\right).
$$
%% 108
эТО СУММА ГЕОМЕТРИЧЕСКОЙ ПРОГРЕССИИ, ПОЭТОМУ МОЖНО ЗАПИСАТЬ СЛЕДУЮЩУЮ
ОСНОВНУЮ ФОРМУЛУ:
$$
f(s_1, \ldots, s_n)=\exp \left({-2\pi i c \over m} \left({s(a)-s(1) \over a-1}\right )\right) \delta\left({s(a)\over m}\right),
\eqno(8)
$$
ГДЕ~$\delta(x)=1$, ЕСЛИ~$x$---ЦЕЛОЕ, И~$\delta(x)=0$ В ПРОТИВНОМ СЛУЧАЕ.

нАПОМНИМ, ЧТО ФОРМУЛА~(2) ПОЗВОЛЯЕТ
ИНТЕРПРЕТИРОВАТЬ~$f(s_1, s_2,~\dots, s_n)/m^n$ ФИЗИЧЕСКИ КАК АМПЛИТУДУ
$n\hbox{-МЕРНОЙ}$  КОМПЛЕКСНОЙ ПЛОСКОЙ ВОЛНЫ
$$
\omega(t_1, \ldots, t_n)=\exp\left(2\pi i \left({s_1\over m}t_1+\cdots+{s_n \over m} t_n\right)\right).
\eqno(9)
$$
"вОЛНОВОЕ ЧИСЛО"~$\nu$, СООТВЕТСТВУЮЩЕЕ "ЧАСТОТЕ" ЭТОЙ ВОЛНЫ,
ОПРЕДЕЛЯЕТСЯ ПО ФОРМУЛЕ
$$
\nu=\sqrt{s_1^2+\cdots+s_n^2}
\rem {ПРИ~$\abs{s_k}\le {m \over 2}$ ДЛЯ~$1\le k < n$.}
\eqno (10)
$$

сОГЛАСНО~(5), НИКАКИХ ВОЛН, КРОМЕ ПОСТОЯННОЙ ВОЛНЫ (С НУЛЕВОЙ ЧАСТОТОЙ),
НЕ ДОЛЖНО ПОЯВЛЯТЬСЯ, ЕСЛИ ПОСЛЕДОВАТЕЛЬНОСТЬ $X_0$, $X_1$, $X_2$,~\dots{}
ДЕЙСТВИТЕЛЬНО СЛУЧАЙНАЯ. пОЭТОМУ СУЩЕСТВОВАНИЕ КОМПОНЕНТ С НЕНУЛЕВОЙ
ЧАСТОТОЙ ГОВОРИТ ОБ ОТКЛОНЕНИИ ОТ СЛУЧАЙНОСТИ. оЧЕНЬ МАЛЫЕ
ЗНАЧЕНИЯ~$f(s_1,~\ldots, s_n)$ МАЛО ВЛИЯЮТ НА СЛУЧАЙНОСТЬ. нАПРИМЕР, ЕСЛИ ВЗЯТЬ
ДЕЙСТВИТЕЛЬНО СЛУЧАЙНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ И ИЗМЕНИТЬ ТОЛЬКО КАЖДЫЙ ЕЕ
$N\hbox{-Й}$~ЧЛЕН (ПРИ БОЛЬШОМ~$N$), ПОСЛЕДОВАТЕЛЬНОСТЬ ОСТАНЕТСЯ
СЛУЧАЙНОЙ, А ЗНАЧЕНИЯ~$f(s_1,~\ldots, s_n)$ БУДУТ ПОРЯДКА~$1/N$; ТАКИМИ
ЗНАЧЕНИЯМИ МОЖНО ПРЕНЕБРЕЧЬ. оТМЕТИМ, ОДНАКО, ЧТО, СОГЛАСНО~(8),
ЗНАЧЕНИЯ~$f(s_1,~\ldots,  s_n)$ РАВНЫ ЛИБО~$0$, ЛИБО~$1$, А
ПРИ~$\abs{f(s_1,~\ldots, s_n)}=1$ О СЛУЧАЙНОСТИ НЕ МОЖЕТ БЫТЬ И РЕЧИ. в
СВЕТЕ ЭТОГО ИНТЕРЕСНО ОТМЕТИТЬ, ЧТО \emph{НИЗКОЧАСТОТНЫЕ КОМПОНЕНТЫ
СИЛЬНЕЕ ВЛИЯЮТ НА СЛУЧАЙНОСТЬ, ЧЕМ ВЫСОКОЧАСТОТНЫЕ.} пОСМОТРИМ, НАПРИМЕР,
ЧТО ПРОИЗОЙДЕТ, ЕСЛИ ЗАМЕНИТЬ~$X_k$ НА~$2X_k$ И~$m$ НА~$2m$. сОГЛАСНО~(4),
$f(s_1,~\ldots, s_n)$ НЕ ИЗМЕНИТСЯ, НО ТЕПЕРЬ БУДУТ ИГРАТЬ РОЛЬ
КОМПОНЕНТЫ С~$\abs{s_k}\le m$, А НЕ С~$\abs{s_k}\le m/2$. иЗУЧЕНИЕ ЭТОЙ
СИТУАЦИИ ПОКАЗЫВАЕТ, ЧТО ЕСЛИ ВЗЯТЬ СЛУЧАЙНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ ЦЕЛЫХ
ЧИСЕЛ~$X_0$, $X_1$, $X_2$,~\dots{} С~$m=2^e$ И НАЧАТЬ ОТБРАСЫВАТЬ МЛАДШИЕ
РАЗРЯДЫ В ДВОИЧНОМ ПРЕДСТАВЛЕНИИ КАЖДОГО ЧЛЕНА ПОСЛЕДОВАТЕЛЬНОСТИ, ТО ПРИ
ОТБРАСЫВАНИИ ОДНОГО, ДВУХ, ТРЕХ И Т.~Д.\ ДВОИЧНЫХ РАЗРЯДОВ БУДУТ
ПОЯВЛЯТЬСЯ КОМПОНЕНТЫ С ВОЛНОВЫМИ ЧИСЛАМИ~$2^{e-1}$, $2^{e-2}$,
$2^{e-3}$ И~Т.~Д. эТОТ ФАКТ, А ТАКЖЕ ПРИМЕР, ПРИВЕДЕННЫЙ В УПР.~(10),
ПРИВОДЯТ К СЛЕДУЮЩЕМУ ИНТУИТИВНОМУ ЗАКЛЮЧЕНИЮ.
\emph{еСЛИ~$\nu_n$---НАИМЕНЬШЕЕ НЕНУЛЕВОЕ ЗНАЧЕНИЕ ВОЛНОВОГО ЧИСЛА~(10), ДЛЯ
КОТОРОГО~$f(s_1,~\ldots, s_n)\ne 0$ В ЛИНЕЙНОЙ КОНГРУЭНТНОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ С МАКСИМАЛЬНЫМ ПЕРИОДОМ, ТО ПОСЛЕДОВАТЕЛЬНОСТЬ~$X_0/m$,
$X_1/m$, $X_2/m$,~\dots{} МОЖНО СЧИТАТЬ ПОСЛЕДОВАТЕЛЬНОСТЬЮ СЛУЧАЙНЫХ
ЧИСЕЛ, РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ МЕЖДУ~$0$ И~$1$
%% 109
И ПРЕДСТАВЛЕННЫХ С "ТОЧНОСТЬЮ" ИЛИ С "ОШИБКОЙ ОКРУГЛЕНИЯ"~$1/\nu_n$,
ПРИЧЕМ РЕЧЬ ИДЕТ О НЕЗАВИСИМОСТИ $n$~ПОСЛЕДОВАТЕЛЬНЫХ ЗНАЧЕНИЙ С
УСРЕДНЕНИЕМ ПО ПОЛНОМУ ПЕРИОДУ.} в УПР.~27 СОДЕРЖИТСЯ ЕЩЕ ОДНО
ПОДТВЕРЖДЕНИЕ ЭТОГО ПРИНЦИПА ВМЕСТЕ С ГЕОМЕТРИЧЕСКОЙ ИНТЕРПРЕТАЦИЕЙ,
ПОКАЗЫВАЮЩЕЙ БОЛЕЕ ОТЧЕТЛИВО ВАЖНОСТЬ ЗНАЧЕНИЯ~$\nu_n$.

фОРМУЛА~(8) ДАЕТ "СПЕКТР" ЛИНЕЙНОЙ КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ,
Т.~Е.\ ПОКАЗЫВАЕТ, КАКИЕ ТИПЫ ВОЛН ИМЕЮТСЯ В ПРЕОБРАЗОВАНИИ фУРЬЕ
ФУНКЦИИ~$F(t_1, \ldots, t_n)$. мЫ ВИДИМ, ЧТО~$f(s_1,~\ldots, s_n)=0$
ВСЕГДА, КРОМЕ СЛУЧАЕВ, КОГДА
$$
s_1+s_2 a+s_3 a^2 + \cdots + s_n a^{n-1} \equiv 0\pmod{m},
\eqno (11)
$$
И ПРИ ЭТОМ~$\abs{f(s_1,~\ldots, s_n)}=1$. сЛЕДОВАТЕЛЬНО, \emph{ДЛЯ
ЛИНЕЙНЫХ КОНГРУЭНТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ С МАКСИМАЛЬНЫМ ПЕРИОДОМ
НАИМЕНЬШЕЕ НЕНУЛЕВОЕ ВОЛНОВОЕ ЧИСЛО В СПЕКТРЕ РАВНО
$$
\nu_n=\min\sqrt{s_1^2+s_2^2+\cdots+s_n^2},
\eqno(12)
$$
ГДЕ МИНИМИМ БЕРЕТСЯ ПО ВСЕМ $n\hbox{-НАБОРАМ}$ ЦЕЛЫХ ЧИСЕЛ
$(s_1, s_2,~\ldots, s_n) \ne (0, 0,~\ldots, 0)$, УДОВЛЕТВОРЯЮЩИМ~(11).}
оТМЕТИМ, ЧТО ЭТО УСЛОВИЕ НЕ ЗАВИСИТ ОТ ПРИРАЩЕНИЯ~$c$ ЛИНЕЙНОЙ
КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ.

оДНИМ ИЗ СЛЕДСТВИЙ ВСЕГО СКАЗАННОГО ЯВЛЯЕТСЯ ВОЗМОЖНОСТЬ
ОПРЕДЕЛЕНИЯ ВЕРХНЕГО ПРЕДЕЛА СЛУЧАЙНОСТИ ЛЮБОЙ ЛИНЕЙНОЙ КОНГРУЭНТНОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ. иСПОЛЬЗУЯ ДОВОЛЬНО ГЛУБОКИЕ ТЕОРЕТИКО-ЧИСЛОВЫЕ МЕТОДЫ,
МОЖНО ПОКАЗАТЬ, ЧТО
$$
\nu_n \le \gamma_n m^{1/n},
\eqno(13)
$$
ГДЕ~$\gamma_n$ ПРИНИМАЕТ ЗНАЧЕНИЯ
$$
1,  (4/3)^{1/4}, 2^{1/6}, 2^{1/4}, 2^{3/10}, (64/3)^{1/12}, 2^{3/7}, 2^{1/2}
$$
ДЛЯ~$n=1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$ [СМ.~УПР.~9, А ТАКЖЕ СТР.~332
В КНИГЕ J.~W.~S.~Cassels, An Introduction to the Geometry of
Numbers, Springer, Berlin (1959)]. дЛЯ ЛЮБОЙ ПЕРИОДИЧЕСКОЙ (С
ПЕРИОДОМ~$m$) ПОСЛЕДОВАТЕЛЬНОСТИ~$U_0$, $U_1$, $U_2$,~\dots{} ЧИСЕЛ,
ЛЕЖАЩИХ МЕЖДУ~$0$ И~$1$, СЛЕДОВАЛО БЫ ОЖИДАТЬ ГРАНИЦЫ, ИЗМЕНЯЮЩЕЙСЯ
КАК~$m^{1/n}$. дЕЛО В ТОМ, ЧТО, СОГЛАСНО СФОРМУЛИРОВАННОМУ ВЫШЕ ПРАВИЛУ,
ВЫПОЛНЕНИЕ С ТОЧНОСТЬЮ~$1/\nu$ ПРЕДПОЛОЖЕНИЯ О НЕЗАВИСИМОСТИ
ПОСЛЕДОВАТЕЛЬНЫХ ЗНАЧЕНИЙ ЭКВИВАЛЕНТНО (ПРИ ЦЕЛОМ~$\nu$) ТОМУ, ЧТО КАЖДОЕ
ИЗ~$\nu^n$ ВОЗМОЖНЫХ ЗНАЧЕНИЙ ($\floor{\nu U_{k+1}}$,
$\floor{\nu U_{k+2}}$,~\dots, $\floor{\nu U_{k+n}}$) ДОЛЖНО ПОЯВЛЯТЬСЯ
ПРИБЛИЗИТЕЛЬНО С ОДИНАКОВОЙ ЧАСТОТОЙ В ПРЕДЕЛАХ ПЕРИОДА; СЛЕДОВАТЕЛЬНО, ИЗ
ИНТУИТИВНЫХ СООБРАЖЕНИЙ МЫ ПОЛУЧАЕМ ПРИБЛИЖЕННОЕ НЕРАВЕНСТВО~$\nu^n \le m$.

\section{B. пРИМЕРЫ}. дЛЯ БОЛЬШЕЙ ЯСНОСТИ ПРОИЛЛЮСТРИРУЕМ ВЫШЕСКАЗАННОЕ
НА ПРИМЕРЕ. вОЗЬМЕМ ЛИНЕЙНУЮ КОНГРУЭНТНУЮ
%% 110
ПОСЛЕДОВАТЕЛЬНОСТЬ С
$$
X_0=0, \qquad a=3141592621, \qquad c=1, \qquad m=10^{10}.
\eqno (14)
$$
мИНИМАЛЬНОЕ НЕНУЛЕВОЕ ЗНАЧЕНИЕ~$s_1^2+s_2^2$, ДЛЯ КОТОРОГО
$$
s_1+3141592621s_2 \equiv 0 \pmod{10^{10}},
$$
СООТВЕТСТВУЕТ~$s_1=67654$, $s_2=226$, ТАК ЧТО
$$
\nu_2=\sqrt{67654^2+226^2} \approx 67654.4.
$$
эТО ОЗНАЧАЕТ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ
$$
U_0, U_1, U_2, \ldots = X_0/m, X_1/m, X_2/m, \ldots
$$
МОЖНО СЧИТАТЬ СЛУЧАЙНОЙ В СМЫСЛЕ НЕЗАВИСИМОСТИ ПАР СЛЕДУЮЩИХ ДРУГ ЗА
ДРУГОМ ЧИСЕЛ~$(U_k, U_{k+1})$ НА ПОЛНОМ ПЕРИОДЕ, ЕСЛИ ОГРАНИЧИТЬСЯ
ТОЧНОСТЬЮ~$1/67654$; Т.~Е.\ ПЕРВЫЕ 16~РАЗРЯДОВ В ДВОИЧНОМ ПРЕДСТАВЛЕНИИ
ЧИСЕЛ МОЖНО СЧИТАТЬ СЛУЧАЙНЫМИ В УКАЗАННОМ СМЫСЛЕ. аНАЛОГИЧНО, МИНИМАЛЬНОЕ
НЕНУЛЕВОЕ ЗНАЧЕНИЕ~$s_1^2+s_2^2+s_3^2$, ДЛЯ КОТОРОГО
$$
s_1+3141592621s_2+3141592621^2s_3 \equiv 0 \pmod{10^{10}},
$$
СООТВЕТСТВУЕТ~$s_1=227$, $s_2=983$, $s_3=130$; СЛЕДОВАТЕЛЬНО,
$$
\nu_3=\sqrt{1034718}\approx 1017.2.
$$
тАКИМ ОБРАЗОМ, ЕСЛИ РАССМАТРИВАЕТСЯ НЕЗАВИСИМОСТЬ ТРОЕК~$(U_k, U_{k+1},
U_{k+2})$, МЫ ИМЕЕМ ТОЧНОСТЬ ВСЕГО В 10~ДВОИЧНЫХ РАЗРЯДОВ. вЕРОЯТНО,
$3141592621$---НЕ ОЧЕНЬ ХОРОШИЙ МНОЖИТЕЛЬ;
ПОЗДНЕЕ МЫ УВИДИМ, ЧТО ОН ЯВЛЯЕТСЯ ПРИЕМЛЕМЫМ, НО НЕ ЛУЧШИМ (НАПРИМЕР,
ПОХОЖИЙ МНОЖИТЕЛЬ~$3141592821$ ДАЕТ~$\nu_3\approx 1912$, НО МЕНЬШЕЕ
ЗНАЧЕНИЕ~$\nu_2$). сОГЛАСНО~(13), ПРИ~$m=10^{10}$ НЕВОЗМОЖНО ПОЛУЧИТЬ~$\nu_3>2425$.

мИНИМАЛЬНОЕ НЕНУЛЕВОЕ ЗНАЧЕНИЕ~$s_1^2+s_2^2+s_3^2+s_4^2$, ДЛЯ КОТОРОГО
$$
s_1+3141592621s_2+3141592621^2s_3+3141592621^3s_4 \equiv 0 \pmod{10^{10}},
$$
ИМЕЕТ МЕСТО ПРИ~$s_1=52$, $s_2=-203$, $s_3=-54$, $s_4=125$, ТАК ЧТО
$$
\nu_4=\sqrt{62454} \approx 249.9.
$$

тРЕБОВАНИЕ НЕЗАВИСИМОСТИ \emph{ЧЕТВЕРОК} ПОНИЖАЕТ ТОЧНОСТЬ ДО 8~ДВОИЧНЫХ
ЗНАКОВ (ДЛЯ БОЛЬШИНСТВА ПРИЛОЖЕНИЙ ЭТОГО ВПОЛНЕ ДОСТАТОЧНО).

зНАЧЕНИЯ~$\nu_n$ ДЛЯ~$n=5$, $6$,~\dots{} МЕНЕЕ ВАЖНЫ, ТАК КАК ВРЯД ЛИ
НЕЗАВИСИМОСТЬ ПЯТЕРОК ВСЕГДА ДЕЙСТВИТЕЛЬНО НЕОБХОДИМА. нАПРИМЕР, ПРИ
ПРОВЕРКЕ СЕРИЙ (СМ.~П.~3.3.2) РЕДКО УЧИТЫВАЮТСЯ ДАЖЕ ЧЕТВЕРКИ. (пРИ
РАССМОТРЕНИИ СРЕДНИХ ПО ВСЕМУ ПЕРИОДУ, КАК В НАШЕМ СЛУЧАЕ, СЛЕДУЕТ
СОБЛЮДАТЬ ОСТОРОЖНОСТЬ, ПОЭТОМУ ПРЕНЕБРЕГАТЬ ЧЕТВЕРКАМИ В СПЕКТРАЛЬНОМ
ТЕСТЕ НЕ СТОИТ; ОДНАКО РАСПРЕДЕЛЕНИЕ
%% 111
ПЯТЕРОК ВРЯД ЛИ МОЖЕТ ПОНАДОБИТЬСЯ, ВО ВСЯКОМ СЛУЧАЕ
ПРИ~$m<2^{40}$.) дЛЯ РАССМАТРИВАЕМОГО ДАТЧИКА~$s_1=-8$, $s_2=-14$, $s_3=6$,
$s_4=-18$, $s_5=34$ И
$$
\eqalign{
\nu_5 &= \sqrt{1776} \approx 42.2, \cr
\nu_6&=\sqrt{542}\approx 23.3.\cr
}
$$

тАК КАК НИКТО НЕ ЗНАЕТ, КАКОВЫ НАИЛУЧШИЕ ДОСТИЖИМЫЕ ЗНАЧЕНИЯ~$\nu_n$,
ТРУДНО ТОЧНО ОПРЕДЕЛИТЬ, КАКИЕ ЗНАЧЕНИЯ~$\nu_n$ МОЖНО СЧИТАТЬ
УДОВЛЕТВОРИТЕЛЬНЫМИ. пРЕДСТАВЛЯЕТСЯ РАЗУМНЫМ ИСПОЛЬЗОВАТЬ В КАЧЕСТВЕ
МЕРЫ СЛУЧАЙНОСТИ ОБЎЕМ ЭЛЛИПСОИДА В $n\hbox{-МЕРНОМ}$ ПРОСТРАНСТВЕ,
ОПРЕДЕЛЕННОГО СООТНОШЕНИЕМ~$(x_1 m-x_2a-x_3a^2-\cdots-x_na^{n-1})^2+x_2^2+\cdots+x_n^2\le \nu_n^2$,
ТАК КАК ЭТОТ ОБЎЕМ ПРОПОРЦИОНАЛЕН ВЕРОЯТНОСТИ ПОПАДАНИЯ В ЭЛЛИПСОИД
ТОЧЕК~$(x_1, x_2,~\ldots, x_n)$---\emph{ЦЕЛОЧИСЛЕННЫХ} РЕШЕНИЙ
УРАВНЕНИЙ~(11). тАКИМ ОБРАЗОМ, ДЛЯ ОПРЕДЕЛЕНИЯ ЭФФЕКТИВНОСТИ МНОЖИТЕЛЯ~$a$
В ЛИНЕЙНОЙ КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ С МАКСИМАЛЬНЫМ ПЕРИОДОМ МЫ
ПРЕДЛАГАЕМ ВЫЧИСЛЯТЬ ВЕЛИЧИНУ
$$
C_n={\pi^{n/2}\nu_n^n \over (n/2)!m}.
\eqno(15)
$$
$\bigl($~в ЭТОЙ ФОРМУЛЕ
$$
\left({n\over 2}\right)!=\left({n\over2}\right) \left({n\over2}-1\right)
\ldots \left({1\over2}\right)\sqrt{\pi} \rem{ДЛЯ НЕЧЕТНЫХ~$n$.}\bigr)
\eqno(16)
$$
тАКИМ ОБРАЗОМ,
$$
C_1=2\nu_1/m, \quad C_2=\pi\nu_2^2/m, \quad C_3={4\over3}\pi_3^3/m,
C_4={1\over2}\pi^2\nu_4^4/m \rem{И Т. Д.}
$$
бОЛЬШИЕ ЗНАЧЕНИЯ~$C_n$ СООТВЕТСТВУЮТ СЛУЧАЙНОСТИ, МАЛЫЕ---ОТСУТСТВИЮ
СЛУЧАЙНОСТИ. в ТАБЛ.~1 ПРЕДСТАВЛЕНЫ ЗНАЧЕНИЯ ДЛЯ НЕКОТОРЫХ ТИПИЧНЫХ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ ($C_1$ ВСЕГДА РАВНО~$2$). дАТЧИКИ, ПРЕДСТАВЛЕННЫЕ
В СТРОКАХ~1--4 ЭТОЙ ТАБЛИЦЫ, БЫЛИ УЖЕ РАССМОТРЕНЫ В П.~3.3.1 (СМ.~РИС.~2 И~5).
у ДАТЧИКОВ~1 И~2 СЛИШКОМ МАЛ МНОЖИТЕЛЬ. оЧЕНЬ ПЛОХОЙ ДАТЧИК~3 ДАЕТ
ХОРОШЕЕ ЗНАЧЕНИЕ~$C_2$, НО ОЧЕНЬ ПЛОХИЕ~$C_3$ И~$C_4$; ДЛЯ НЕГО~$\nu_3=6$
И~$\nu_4=2$. у ДАТЧИКА~4 "СЛУЧАЙНЫЙ" МНОЖИТЕЛЬ; ЭТОТ ДАТЧИК УСПЕШНО ПРОШЕЛ
ИСПЫТАНИЯ С ИСПОЛЬЗОВАНИЕМ ЭМПИРИЧЕСКИХ ТЕСТОВ, НО ЗНАЧЕНИЯ~$C_2$, $C_3$
И~$C_4$ У НЕГО НЕ ОЧЕНЬ ВЕЛИКИ.

дАТЧИК~7 МЫ ТОЛЬКО ЧТО РАССМАТРИВАЛИ; РЯДОМ С НИМ ПРЕДСТАВЛЕНЫ ДАТЧИКИ С
БЛИЗКИМИ ПАРАМЕТРАМИ. оТМЕТИМ, ЧТО МНОЖИТЕЛЬ~$3141592221$ ПРИВОДИТ К
АНОМАЛЬНО НИЗКОМУ ЗНАЧЕНИЮ~$C_3$ (СМ.~СТРОКУ~5), ОДНАКО ПРИ ТОМ ЖЕ
ЗНАЧЕНИИ~$a$ С~$m=2^{35}$ (СМ. \ СТРОКУ~9) ПОЛУЧАЮТСЯ ХОРОШИЕ РЕЗУЛЬТАТЫ.

%% 112

\htable{тАБЛИЦА 1}%
{нЕКОТОРЫЕ РЕЗУЛЬТАТЫ, ПОЛУЧЕННЫЕ ПРИ ПОМОЩИ СПЕКТРАЛЬНОГО ТЕСТА}%
{\hfil$#$\bskip&&\bskip$#$\bskip\hfil\cr
сТРОКА & a & m & C_2 & C_3 & C_4 \cr
\noalign{\hrule}
 1 & 23              & 10^8+1  & 0.000017 & 0.00051     & 0.014       \cr
 2 & 2^7+1           & 2^{35}  & 0.000002 & 0.00026     & 0.040       \cr
 3 & 2^{18}+1        & 2^{35}  & 3.14     & 0.000000002 & 0.000000003 \cr
 4 & 3141592653      & 2^{35}  & 0.27     & 0.13        & 0.11        \cr
 5 & 3141592221      & 10^{10} & 1.35     & 0.06        & 4.67        \cr
 6 & 3141592421      & 10^{10} & 2.69     & 0.35        & 0.54        \cr
 7 & 3141592621      & 10^{10} & 1.44     & 0.43        & 1.91        \cr
 8 & 3141592821      & 10^{10} & 0.16     & 2.90        & 0.34        \cr
 9 & 3141592221      & 2^{35}  & 1.24     & 1.69        & 1.11        \cr
10 & 3141592621      & 2^{35}  & 3.02     & 0.17        & 1.25        \cr
11 & 2718281821      & 2^{35}  & 2.59     & 1.15        & 1.75        \cr
12 & 2^{23}+2^{12}+5 & 2^{35}  & 0.015    & 2.78        & 0.066       \cr
13 & 2^{23}+2^{13}+5 & 2^{35}  & 0.015    & 1.48        & 0.066       \cr
14 & 2^{23}+2^{14}+5 & 2^{35}  & 1.12     & 1.66        & 0.066       \cr
15 & 2^{22}+2^{13}+5 & 2^{35}  & 0.75     & 0.30        & 0.066       \cr
16 & 2^{24}+2^{13}+5 & 2^{35}  & 0.0008   & 2.92        & 0.066       \cr
17 & 5^{13}          & 2^{35}  & 3.03     & 0.61        & 1.84        \cr
18 & 5^{15}          & 2^{35}  & 2.02     & 4.12        & 4.04        \cr
   & \hbox{\emph{вЕРХНЯЯ ГРАНИЦА СОГЛАСНО}~(13):} \span & 3.63 & 5.90 & 9.86 \cr
}

у ДАТЧИКОВ~12--16 В ДВОИЧНОМ ПРЕДСТАВЛЕНИИ~$a$ ВСЕГО ПО 4~ЕДИНИЦЫ;
ПРИЕМЛЕМЫМ МОЖНО СЧИТАТЬ ТОЛЬКО ДАТЧИК~14, НО И У НЕГО ПОДОЗРИТЕЛЬНО
НИЗКОЕ ЗНАЧЕНИЕ~$C_4$. пО СТРАННОМУ СОВПАДЕНИЮ ВСЕ ЭТИ 5~ДАТЧИКОВ ДАЮТ
ОДИНАКОВОЕ ЗНАЧЕНИЕ~$C_4$; БОЛЕЕ ТОГО, ВО ВСЕХ СЛУЧАЯХ~$s_1=-125$,
$s_2=75$, $s_3=15$, $s_4=1$! кУРЬЕЗНЫМ ЯВЛЯЕТСЯ ТАКЖЕ НАЛИЧИЕ У
ДАТЧИКА~16 ВЫСОКОГО ЗНАЧЕНИЯ~$C_3$ ПРИ НИЗКОМ~$C_2$; В ЭТОМ
СЛУЧАЕ~$\nu_2=\nu_3$, ТАК КАК МИНИМУМ ПРИ~$n=3$ ДОСТИГАЕТСЯ
ПРИ~$s_1=-2043$, $s_2=2047$, $s_3=0$.

в ДАТЧИКАХ~17 И~18 ИСПОЛЬЗОВАНЫ МНОЖИТЕЛИ, КОТОРЫЕ ИНТЕНСИВНО
ПРИМЕНЯЛИСЬ С ТЕХ ПОР, КАК ИХ ПРЕДЛОЖИЛА о.~тАУССКИ В НАЧАЛЕ 50-Х ГОДОВ.
пО СЛУЧАЙНОМУ СОВПАДЕНИЮ НАИБОЛЕЕ ПОПУЛЯРНЫЙ МНОЖИТЕЛЬ~$5^{15}$ ДАЕТ
НАИЛУЧШИЕ РЕЗУЛЬТАТЫ ИЗ ВСЕХ СЛУЧАЕВ, ПОКАЗАННЫХ В ТАБЛ.~1.

рЕЗУЛЬТАТЫ, ПРИВЕДЕННЫЕ В ТАБЛ.~1, И ПОСЛЕДУЮЩИЙ ОПЫТ РАБОТЫ С МНОГИМИ ИЗ
ПРЕДСТАВЛЕННЫХ ЗДЕСЬ ДАТЧИКОВ ПОЗВОЛЯЮТ СКАЗАТЬ, ЧТО МНОЖИТЕЛЬ~$a$
\emph{УСПЕШНО ПРОШЕЛ СПЕКТРАЛЬНЫЙ ТЕСТ}, ЕСЛИ КАЖДОЕ ИЗ~$C_2$, $C_3$
И~$C_4\ge 0.1$; ЕСЛИ ВСЕ ОНИ БОЛЬШЕ (ИЛИ РАВНЫ) ЕДИНИЦЫ, ТО МОЖНО СЧИТАТЬ,
ЧТО СПЕКТРАЛЬНЫЙ ТЕСТ ПРОЙДЕН С БЛЕСКОМ. пРЕЖДЕ ЧЕМ РЕКОМЕНДОВАТЬ ДАТЧИК
ДЛЯ ОБЩЕГО ПОЛЬЗОВАНИЯ, МОЖНО ВЫЧИСЛИТЬ ТАКЖЕ~$C_5$, $C_6$ И~Т.~Д. дЛЯ
ТОГО ЧТОБЫ УБЕДИТЬСЯ,  ЧТО МОДУЛЬ~$m$ ДОСТАТОЧНО ВЕЛИК ДЛЯ ОБЕСПЕЧЕНИЯ
%% 113
ТРЕБУЕМОЙ ТОЧНОСТИ СЛУЧАЙНЫХ ЧИСЕЛ, НАДО АНАЛИЗИРОВАТЬ ЗНАЧЕНИЯ~$\nu_2$,
$\nu_3$  И~$\nu_4$; ПРИ МАЛЫХ~$m$ УДОВЛЕТВОРИТЕЛЬНЫЕ РЕЗУЛЬТАТЫ, ПОЛУЧЕННЫЕ
С ПОМОЩЬЮ СПЕКТРАЛЬНОГО ТЕСТА, ЕЩЕ НЕ ГАРАНТИРУЮТ ПРИГОДНОСТИ ДАТЧИКА ДЛЯ
РАСЧЕТОВ МЕТОДОМ мОНТЕ-кАРЛО С ВЫСОКИМ РАЗРЕШЕНИЕМ.

\section{C.~вЫВОД ВЫЧИСЛИТЕЛЬНОГО МЕТОДА}. пРИВЕДЕННЫЕ ПРИМЕРЫ
ИЛЛЮСТРИРУЮТ СПОСОБЫ ПРИМЕНЕНИЯ СПЕКТРАЛЬНОГО ТЕСТА. оДНАКО В НАШИХ
РАССУЖДЕНИЯХ ОСТАЕТСЯ, КОНЕЧНО, СУЩЕСТВЕННЫЙ ПРОБЕЛ:
СУЩЕСТВУЕТ ЛИ ХОТЬ КАКАЯ-НИБУДЬ ВОЗМОЖНОСТЬ ОПРЕДЕЛИТЬ ЗНАЧЕНИЕ~$\nu_n$,
ЗАТРАЧИВАЯ НЕ СЛИШКОМ МНОГО МАШИННОГО ВРЕМЕНИ? кАК, НАПРИМЕР, МОЖНО
ВЫЯСНИТЬ, ЧТО ИМЕННО ЗНАЧЕНИЯМ~$s_1=227$, $s_2=983$ И~$s_3=130$
СООТВЕТСТВУЕТ МИНИМУМ СУММЫ~$s_1^2+s_2^2+s_3^2$ ПРИ СОБЛЮДЕНИИ
УСЛОВИЯ~$s_1+3141592621s_2+3141592621^2s_3\equiv 0 \pmod{10^{10}}$?
оЧЕВИДНО, ЧТО О ПРОСТОМ ПЕРЕБОРЕ НЕ МОЖЕТ БЫТЬ И РЕЧИ.

пОПЫТАЕМСЯ ОТЫСКАТЬ ПОДХОДЯЩИЙ ВЫЧИСЛИТЕЛЬНЫЙ МЕТОД ДЛЯ РЕШЕНИЯ ЭТОЙ
ЗАДАЧИ. пРЕЖДЕ ВСЕГО ПЕРЕЙДЕМ ОТ ТОЛЬКО ЧТО ПРИВЕДЕННОЙ ФОРМУЛИРОВКИ,
ОПИРАЮЩЕЙСЯ НА ФОРМУЛЫ~(11) И~(12), К СЛЕДУЮЩЕЙ ЭКВИВАЛЕНТНОЙ ЗАДАЧЕ:
ОПРЕДЕЛИТЬ МИНИМУМ СУММЫ
$$
(x_1m-ax_2-a^2x_3-\cdots-a^{n-1}x_n)^2+x_2^2+x_3^2+\cdots+x_n^2
\eqno(17)
$$
ПРИ ЦЕЛЫХ ЗНАЧЕНИЯХ~$x_1$, $x_2$,~\dots, $x_n$, ИЗ КОТОРЫХ ХОТЯ БЫ ОДНО НЕ
РАВНО НУЛЮ.

бУДЕТ ИНТЕРЕСНО И, ВЕРОЯТНО, ПОЛЕЗНЕЕ РАЗРАБОТАТЬ ЧИСЛЕННЫЙ МЕТОД
РЕШЕНИЯ БОЛЕЕ ОБЩЕЙ ЗАДАЧИ: \emph{ОПРЕДЕЛИТЬ МИНИМУМ СУММЫ
$$
(a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n)^2+\cdots+(a_{n1}x_1+a_{n2}x_2+\cdots+a_{nn}x_n)^2
\eqno(18)
$$
ПРИ ЦЕЛЫХ ЗНАЧЕНИЯХ~$x_1$,~\dots, $x_n$, ИЗ КОТОРЫХ ХОТЯ БЫ ОДНО НЕ РАВНО
НУЛЮ,} И ПРИ УСЛОВИИ, ЧТО МАТРИЦА КОЭФФИЦИЕНТОВ~$A=(a_{ij})$ НЕ ВЫРОЖДЕНА.
вЫРАЖЕНИЕ~(18) НАЗЫВАЕТСЯ "ПОЛОЖИТЕЛЬНО ОПРЕДЕЛЕННОЙ КВАДРАТИЧНОЙ ФОРМОЙ".

в ДАЛЬНЕЙШЕМ БУКВАМИ~$x$, $y$,~\dots{} БУДУТ ОБОЗНАЧАТЬСЯ ВЕКТОР-СТОЛБЦЫ
$$
\pmatrix{
 x_1\cr
 x_2\cr
 \vdots\cr
 x_n\cr
},
\pmatrix{
 y_1\cr
 y_2\cr
 \vdots\cr
 y_n\cr
}, \ldots
$$
"сКАЛЯРНОЕ ПРОИЗВЕДЕНИЕ" $x\cdot y = x_1 y_1+\cdots+x_ny_n$ МОЖЕТ БЫТЬ
ЗАПИСАНО В МАТРИЧНЫХ ОБОЗНАЧЕНИЯХ КАК~$x^Ty$, ГДЕ $T$~ОБОЗНАЧАЕТ ЗАМЕНУ
СТОЛБЦОВ НА СТРОКИ, И НАОБОРОТ (ТРАНСПОНИРОВАНИЕ). дЛЯ УДОБСТВА ВВЕДЕМ
СЛЕДУЮЩИЕ ОПРЕДЕЛЕНИЯ:
$$
Q=A^TA, \quad B=A^{-1}, \quad R=Q^{-1}=BB^T.
\eqno(19)
$$
%% 113
пУСТЬ $A_j$~ОБОЗНАЧАЕТ $j\hbox{-Й}$~\emph{СТОЛБЕЦ} МАТРИЦЫ~$A$,
А~$B_i$---$i\hbox{-Ю}$~\emph{СТРОКУ} МАТРИЦЫ~$B$. тОГДА ИМЕЕМ
$$
B_i\cdot A_j=\delta_{ij}, \quad Q_{ij}=A_i\cdot A_j, \quad R_{ij}=B_i\cdot B_j.
\eqno (20)
$$
нАША ЗАДАЧА СОСТОИТ В ТОМ, ЧТОБЫ МИНИМИЗИРОВАТЬ~(18), Т.~Е.\
МИНИМИЗИРОВАТЬ~$(Ax)\cdot(Ax)=x^TA^TAx=x^TQx$ ДЛЯ ЦЕЛЫХ ВЕКТОРОВ~$x\ne0$.

пРЕЖДЕ ВСЕГО СДЕЛАЕМ ЗАДАЧУ КОНЕЧНОЙ, Т.~Е.\ ПОКАЖЕМ, ЧТО НЕ НАДО
ПЕРЕБИРАТЬ ВСЕ БЕСКОНЕЧНОЕ МНОЖЕСТВО ВЕКТОРОВ~$x$, ЧТОБЫ НАЙТИ МИНИМУМ.
пУСТЬ~$e_k$---ВЕКТОР, $k\hbox{-Я}$~КОМПОНЕНТА КОТОРОГО РАВНА~$1$, А
ОСТАЛЬНЫЕ НУЛЮ. тОГДА
$$
x_k = e_k^T x = e_k^T B Ax = (B^T e_k)\cdot(Ax) = B_k\cdot (Ax)
$$
И, СОГЛАСНО НЕРАВЕНСТВУ шВАРЦА,
$$
(B_k\cdot (Ax))^2 \le (B_k\cdot B_k) ((Ax)\cdot(Ax))=R_{kk}(x^TQx).
$$
сЛЕДОВАТЕЛЬНО, ЕСЛИ~$x$---НЕНУЛЕВОЙ ВЕКТОР, МИНИМИЗИРУЮЩИЙ~$x^T Qx$, ТО
$$
x_k^2\le R_{kk}(x^T Qx) \le R_{kk}(e_j^T Qe_j)=R_{kk}Q_{jj},
\rem{$1\le j$, $k\le n$.}
\eqno(21)
$$
эТО ОЗНАЧАЕТ, ЧТО ЧИСЛО ВЕКТОРОВ~$x$, КОТОРЫЕ НАДО РАССМОТРЕТЬ ПРИ ПОИСКЕ
МИНИМУМА, ОГРАНИЧЕНО. нА САМОМ ДЕЛЕ МЫ ПОЛУЧИЛИ СЛЕДУЮЩИЙ БОЛЕЕ ОБЩИЙ РЕЗУЛЬТАТ.

\proclaim лЕММА~A. еСЛИ
$$
x=\pmatrix{
x_1\cr
\vdots\cr
x_n\cr
}
$$
---НЕНУЛЕВОЙ ЦЕЛОЧИСЛЕННЫЙ ВЕКТОР С МИНИМАЛЬНЫМ ЗНАЧЕНИЕМ~$x^TQx$,
a~$q$---ЗНАЧЕНИЕ~$y^TQ$ ДЛЯ НЕКОТОРОГО НЕНУЛЕВОГО ЦЕЛОЧИСЛЕННОГО
ВЕКТОРА~$y$, ТО
$$
x_k^2\le R_{kk}q. \endmark
\eqno(22)
$$

оЧЕВИДНО, ЧТО ПРАВАЯ ЧАСТЬ~(22) МОЖЕТ БЫТЬ ВСЕ ЕЩЕ СЛИШКОМ БОЛЬШОЙ, ЧТОБЫ
ПРОСТОЙ ПЕРЕБОР БЫЛ ПРАКТИЧЕСКИ ОСУЩЕСТВИМ, ТАК ЧТО ТРЕБУЕТСЯ ПРОИЗВЕСТИ
ДАЛЬНЕЙШИЕ УСОВЕРШЕНСТВОВАНИЯ. оБРАТИМСЯ К ОДНОМУ ИЗ НАИБОЛЕЕ ПРОСТЫХ И
ШИРОКО РАСПРОСТРАНЕННЫХ В МАТЕМАТИКЕ ПРИЕМОВ---МЕТОДУ ЗАМЕНЫ ПЕРЕМЕННЫХ.
рАССМОТРИМ ПОДСТАНОВКУ ВИДА
$$
y=Ux,
\eqno(23)
$$
ГДЕ~$U$---ЦЕЛОЧИСЛЕННАЯ МАТРИЦА, ОПРЕДЕЛИТЕЛЬ КОТОРОЙ~$\det U=\pm 1$. эТО
ОЗНАЧАЕТ, ЧТО ЕСЛИ~$x$---ВЕКТОР-СТОЛБЕЦ, СОСТОЯЩИЙ ИЗ ЦЕЛЫХ ЧИСЕЛ, ТО ТАКОВ
ЖЕ И~$y$, И ОБРАТНО, ЕСЛИ ВЕКТОР~$y$ ЗАДАН, ТО~$x$ МОЖНО ОПРЕДЕЛИТЬ ИЗ
СООТНОШЕНИЯ~$x=U^{-1}y$. (эЛЕМЕНТЫ МАТРИЦЫ~$U^{-1}$
%% 115
БУДУТ ЦЕЛЫМИ, ТАК КАК ОНА РАВНА~$\adj (U)/\det(U)$.) сЛЕДОВАТЕЛЬНО, ЕСЛИ В
КАЧЕСТВЕ~$x$ ПЕРЕБРАТЬ ВСЕ ЦЕЛОЧИСЛЕННЫЕ ВЕКТОРЫ, ТО ЭТО ЖЕ МНОЖЕСТВО
ЗНАЧЕНИЙ ПРОБЕЖИТ И~$y=Ux$, И ОБРАТНО; ДАЛЕЕ, $y=0$ ТОЛЬКО ПРИ~$x=0$.
пОЭТОМУ МОЖНО ПЕРЕЙТИ ОТ ЗАДАЧИ О МИНИМИЗАЦИИ~$(Ax)\cdot(Ax)$ ДЛЯ
ЦЕЛЫХ~$x\ne0$ К ЭКВИВАЛЕНТНОЙ ЗАДАЧЕ О НАХОЖДЕНИИ
МИНИМУМА~$(AU^{-1}y)\cdot(AU^{-1}y)$ ДЛЯ ЦЕЛЫХ~$y\ne0$.

\proclaim лЕММА~B. пУСТЬ~$U$---ЛЮБАЯ ЦЕЛОЧИСЛЕННАЯ МАТРИЦА С~$\det U=\pm1$, И ПУСТЬ
$$
A'=AU^{-1}, \quad B'=Ub, \quad Q'=(U^{-1})^T QU^{-1}, \quad R'=URU^T.
\eqno(24)
$$
зАДАЧА МИНИМИЗАЦИИ, ОПРЕДЕЛЕННАЯ МАТРИЦАМИ~$A'$, $B'$, $Q'$, $R'$,  ИМЕЕТ
ТО ЖЕ САМОЕ РЕШЕНИЕ, ЧТО И ЗАДАЧА, ОПРЕДЕЛЕННАЯ МАТРИЦАМИ~$A$, $B$, $Q$, $R$.\endmark

тЕПЕРЬ МОЖНО ОПРЕДЕЛИТЬ ЭФФЕКТИВНЫЙ СПОСОБ ВЫЧИСЛЕНИЯ МИНИМАЛЬНОГО
ЗНАЧЕНИЯ СЛЕДУЮЩИМ ОБРАЗОМ: ПЕРЕЙТИ ОТ ИСХОДНОЙ ЗАДАЧИ К ДРУГОЙ С ПОМОЩЬЮ
ПОДХОДЯЩЕЙ МАТРИЦЫ~$U$ И ПОВТОРЯТЬ ЭТО ДО ТЕХ ПОР, ПОКА НЕ ПОЛУЧИТСЯ
ЗАДАЧА, ДЛЯ КОТОРОЙ НЕРАВЕНСТВО В ЛЕММЕ~A ПОЗВОЛЯЕТ ПРОИЗВЕСТИ ПОЛНЫЙ
ПЕРЕБОР НЕ СЛИШКОМ ДОРОГОЙ ЦЕНОЙ.

дОСТАТОЧНО ПРОСТОЙ И ПРИГОДНОЙ ДЛЯ НАШИХ ЦЕЛЕЙ МАТРИЦЕЙ, ОПРЕДЕЛИТЕЛЬ
КОТОРОЙ РАВЕН~$1$, МОЖЕТ СЛУЖИТЬ МАТРИЦА
$$
\eqalign{
U&=\pmatrix{
1   \cr
    & \ddots \cr
    &        & 1       \cr
c_1 & \ldots & c_{k-1} & 1 & c_{k+1} & \ldots & c_n \cr
    &        &         &   & 1       \cr
    &        &         &   &         & \ddots \cr
    &        &         &   &         &        & 1 \cr
} \cr
U^{-1}&=\pmatrix{
1    \cr
     & \ddots \cr
     &        & 1        \cr
-c_1 & \ldots & -c_{k-1} & 1 & -c_{k+1} & \ldots & -c_n \cr
     &        &          &   & 1        \cr
     &        &          &   &          & \ddots \cr
     &        &          &   &          &        & 1    \cr
} \cr
}
\eqno(25)
$$
ГДЕ~$c_1$,~\dots, $c_n$---ЛЮБЫЕ ЦЕЛЫЕ ЗНАЧЕНИЯ, $k$---ФИКСИРОВАННОЕ ЦЕЛОЕ
ЧИСЛО. вСЕ ЭЛЕМЕНТЫ МАТРИЦ, КРОМЕ УКАЗАННЫХ, РАВНЫ НУЛЮ. в ЭТОМ СЛУЧАЕ
СООТНОШЕНИЕ~$y=Ux$ ОЗНАЧАЕТ ПРОСТО, ЧТО~$y_j=x_j$ ДЛЯ~$j\ne k$
И~$y_k=x_k+\sum_{j\ne k} c_j x_j$; БЕЗУСЛОВНО, ЭТО НАИБОЛЕЕ ЕСТЕСТВЕННЫЙ
СПОСОБ ПОДСТАНОВКИ. вЫЧИСЛИТЬ ПРОИЗВЕДЕНИЯ, ПЕРЕЧИСЛЕННЫЕ
%%116
В~(24), В ЭТОМ СЛУЧАЕ ОЧЕНЬ ЛЕГКО:
$$
\eqalignter{
A'_j&=A_j-c_jA_k & \rem{ДЛЯ~$j\ne k$, $A_k'=A_k$;}\cr
B'_j&=B_j & \rem{ДЛЯ~$j\ne k$, $B'_k=B_k+\sum_{j\ne k} c_j B_j$.}\cr
}
\eqno(26)
$$
тЕПЕРЬ НУЖНО ПОДОБРАТЬ ПОДХОДЯЩИЕ ЦЕЛЫЕ ЗНАЧЕНИЯ~$k$ И~$c_j$. пРИ
ЛЮБЫХ~$c_j$ И ЦЕЛЫХ~$k$ МАТРИЦА~$U$ В~(25) В ПРИНЦИПЕ ЯВЛЯЕТСЯ ВПОЛНЕ
ПРИЕМЛЕМЫМ ПРЕОБРАЗОВАНИЕМ. в СООТВЕТСТВИИ С~(21) ЖЕЛАТЕЛЬНО ВЫБРАТЬ
ЦЕЛЫЕ ЧИСЛА~$c_1$,~\dots, $c_{k-1}$, $c_{k+1}$,~\dots, $c_n$ ТАК, ЧТОБЫ
\emph{ДИАГОНАЛЬНЫЕ ЭЛЕМЕНТЫ} КАК МАТРИЦЫ~$Q'$, ТАК И~$R'$ БЫЛИ КАК МОЖНО
МЕНЬШЕ. в СВЯЗИ С ЭТИМ ЕСТЕСТВЕННО ВОЗНИКАЮТ ДВА СЛЕДУЮЩИХ ВОПРОСА:

\medskip
\item{a)}\emph{кАК ЛУЧШЕ ВСЕГО ВЫБРАТЬ ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА~$c_j$
ПРИ~$j\ne k$, ЧТОБЫ МИНИМИЗИРОВАТЬ ЗНАЧЕНИЯ ДИАГОНАЛЬНЫХ ЭЛЕМЕНТОВ
МАТРИЦЫ~$Q'=(U^{-1})^T Q U^{-1}$?}

\item{b)}\emph{кАК ЛУЧШЕ ВСЕГО ВЫБРАТЬ ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА~$c_j$
ПРИ~$j\ne k$, ЧТОБЫ МИНИМИЗИРОВАТЬ ЗНАЧЕНИЯ ДИАГОНАЛЬНЫХ ЭЛЕМЕНТОВ МАТРИЦЫ~$R'=URU^T$?}
\medskip

в СЛУЧАЕ~(a) ДИАГОНАЛЬНЫЕ ЭЛЕМЕНТЫ МАТРИЦЫ~$Q'$, РАВНЫЕ~$A'_j\cdot A'_j$
СОГЛАСНО~(20), БУДУТ ИЗМЕНЕНЫ ПРЕОБРАЗОВАНИЕМ~$U$ ПРИ ВСЕХ~$j\ne k$. лЕГКО
ВИДЕТЬ, ЧТО МИНИМУМ ВЫРАЖЕНИЯ
$$
\eqalign{
(A_j-c_jA_k)\cdot(A_j-c_jA_k)&=Q_{jj}-2c_jQ_{jk}+c_j^2Q_{kk}=\cr
                             &=Q_{kk}(c_j-Q_{jk}/Q_{kk})^2+Q_{jj}-Q_{jk}^2/Q_{kk}\cr
}
$$
ДОСТИГАЕТСЯ ПРИ
$$
c_j=Q_{jk}/Q_{kk}.
\eqno(27)
$$

гЕОМЕТРИЧЕСКИ (РИС.~8) ЗАДАЧА ЗАКЛЮЧАЕТСЯ В ТАКОМ ВЫБОРЕ КОЭФФИЦИЕНТА ПРИ
ВЕКТОРЕ~$A_k$, ЧТОБЫ ПРИ ВЫЧИТАНИИ~$c_jA_k$ ИЗ ВЕКТОРА~$A_j$
РЕЗУЛЬТИРУЮЩИЙ ВЕКТОР~$A'_j$ ИМЕЛ МИНИМАЛЬНУЮ ДЛИНУ. дЛЯ ЭТОГО НАДО
ВЫБРАТЬ ТАКОЕ~$c_j$, ЧТОБЫ $A'_j$~БЫЛО ПЕРПЕНДИКУЛЯРНО К~$A_k$
(Т.~Е.~$A'_j\cdot A'_k=Q'_{jk}=0$), А ЭТО ДОСТИГАЕТСЯ С ПОМОЩЬЮ~(27).

в СЛУЧАЕ~(b) ДИАГОНАЛЬНЫЕ ЭЛЕМЕНТЫ МАТРИЦ~$R'$ И~$R$ СОВПАДАЮТ,
КРОМЕ~$R'_{kk}=B'_k\cdot B'_k$. зДЕСЬ НАМ НАДО ВЫБРАТЬ~$c_j$ ТАК, ЧТОБЫ
\picture{рИС. 8. гЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ВЫВОДА ФОРМУЛЫ (27).}
%% 117
ВЕКТОР~$B_k+\sum_{j\ne k} c_jB_j$ ИМЕЛ МИНИМАЛЬНУЮ ДЛИНУ. гЕОМЕТРИЧЕСКИ
ЭТО ОЗНАЧАЕТ, ЧТО МЫ ДОБАВЛЯЕМ К ВЕКТОРУ~$B_k$ НЕКОТОРЫЙ ВЕКТОР, ЛЕЖАЩИЙ В
$(n-1)\hbox{-МЕРНОЙ}$ ГИПЕРПЛОСКОСТИ, ОПРЕДЕЛЯЕМОЙ
ВЕКТОРАМИ~$\{\,B_j \mid j\ne k\,\}$. тАК ЖЕ, КАК В СЛУЧАЕ, ПОКАЗАННОМ НА
РИС.~8, МИНИМУМ ДОСТИГАЕТСЯ, КОГДА $B'_k$~ПЕРПЕНДИКУЛЯРЕН ГИПЕРПЛОСКОСТИ,
$B'_k$~ПЕРПЕНДИКУЛЯРЕН ВСЕМ~$B'_j$ ПРИ~$j\ne k$. тАКИМ ОБРАЗОМ,
НЕОБХОДИМО РЕШИТЬ СИСТЕМУ УРАВНЕНИЙ~$B'_kB'_j=0$, Т.~Е.
$$
R_{kj}+\sum_{i\ne k} c_i R_{ij}=0, \rem{$1\le j \le n$, $j \ne k$.}
\eqno(28)
$$
сТРОГОЕ ДОКАЗАТЕЛЬСТВО ТОГО, ЧТО ЗАДАЧА~(b) СВОДИТСЯ К
РЕШЕНИЮ УРАВНЕНИЙ~(28), РАССМОТРЕНО В УПР.~12.

тЕПЕРЬ, КОГДА ОБЕ ЗАДАЧИ~(a) И~(b) РЕШЕНЫ, МЫ ПРЕБЫВАЕМ В НЕКОТОРОМ
НЕДОУМЕНИИ: ВЫБИРАТЬ ЛИ ЗНАЧЕНИЯ~$c$ В СООТВЕТСТВИИ С~(27), ЧТОБЫ
МИНИМИЗИРОВАТЬ ДИАГОНАЛЬНЫЕ ЭЛЕМЕНТЫ МАТРИЦЫ~$Q'$, ИЛИ В СООТВЕТСТВИИ
С~(28), ЧТОБЫ МИНИМИЗИРОВАТЬ ДИАГОНАЛЬНЫЕ ЭЛЕМЕНТЫ~$R'$? в ОБОИХ СЛУЧАЯХ
ПРАВАЯ ЧАСТЬ~(21) УТОЧНЯЕТСЯ, ПОЭТОМУ НЕЯСНО, КАКОЙ ВАРИАНТ
ПРЕДПОЧТИТЕЛЬНЕЕ. к СЧАСТЬЮ, ОТВЕТ ЧРЕЗВЫЧАЙНО ПРОСТ: УСЛОВИЯ~(27) И~(28)
СОВЕРШЕННО ОДИНАКОВЫ! рАВЕНСТВО~$R'=(Q')^{-1}$ ОЗНАЧАЕТ, ЧТО
НЕДИАГОНАЛЬНЫЕ ЭЛЕМЕНТЫ В $k\hbox{-Й}$~СТРОКЕ И
$k\hbox{-М}$~СТОЛБЦЕ~$Q'$ РАВНЫ НУЛЮ ТОГДА И ТОЛЬКО ТОГДА, КОГДА РАВНЫ
НУЛЮ НЕДИАГОНАЛЬНЫЕ ЭЛЕМЕНТЫ В $k\hbox{-Й}$~СТРОКЕ И~$k\hbox{-М}$~СТОЛБЦЕ
МАТРИЦЫ~$R'$. пОЭТОМУ У ЗАДАЧ~(a) И~(b) ОДНО И ТО ЖЕ РЕШЕНИЕ. в РЕЗУЛЬТАТЕ
ОКАЗЫВАЕТСЯ, ЧТО МОЖНО СДЕЛАТЬ МИНИМАЛЬНЫМИ ОДНОВРЕМЕННО ДИАГОНАЛЬНЫЕ
ЭЛЕМЕНТЫ~$Q$ И~$R$. (зАМЕТИМ, ЧТО МЫ ТОЛЬКО ЧТО ОТКРЫЛИ ЗАНОВО ТАК
НАЗЫВАЕМЫЙ "ПРОЦЕСС ОРТОГОНАЛИЗАЦИИ шМИДТА".)

кОНЕЧНО, НА САМОМ ДЕЛЕ УСЛОВИЯ~(a) И~(b) ВЫПОЛНЯЮТСЯ ПРИ НЕЦЕЛЫХ
ЗНАЧЕНИЯХ~$c_j$, А МЫ МОЖЕМ ИСПОЛЬЗОВАТЬ В МАТРИЦЕ~$U$ ТОЛЬКО ЦЕЛЫЕ
ЗНАЧЕНИЯ. пРИ ЭТОМ СДЕЛАТЬ~$A'_j$ В ТОЧНОСТИ ПЕРПЕНДИКУЛЯРНЫМ~$A'_k$
НЕВОЗМОЖНО. еСЛИ, ОДНАКО, ВЫБРАТЬ В КАЧЕСТВЕ~$c_j$ \emph{БЛИЖАЙШИЕ
К~$Q_{jk}/Q_{kk}$ ЦЕЛЫЕ ЧИСЛА,} ТО ЭТО БУДЕТ НАИЛУЧШИМ ЦЕЛЫМ РЕШЕНИЕМ
ЗАДАЧИ~(a) И БЛИЗКИМ К (НО \emph{НЕ} ВСЕГДА РАВНЫМ) НАИЛУЧШЕМУ РЕШЕНИЮ ЗАДАЧИ~(b).

пРОИЗВОДЯ ПРЕОБРАЗОВАНИЯ ВИДА~(25) ПРИ РАЗНЫХ~$k$ И ПРИ~$c_j$, РАВНЫХ
БЛИЖАЙШЕМУ ЦЕЛОМУ К~$Q_{jk}/Q_{kk}$, МОЖНО ОЖИДАТЬ, ЧТО ПОСТЕПЕННО ВЕРХНЯЯ
ГРАНИЦА, ОПРЕДЕЛЯЕМАЯ ВЫРАЖЕНИЕМ~(21), СПУСТИТСЯ ДО УРОВНЯ, ПРИ КОТОРОМ
ВОЗМОЖЕН ПОЛНЫЙ ПЕРЕБОР. нА ЭТОМ ПРЕДПОЛОЖЕНИИ ОСНОВАН ПРИВЕДЕННЫЙ НИЖЕ
АЛГОРИТМ. пРИ НАПИСАНИИ НАСТОЯЩЕЙ ГЛАВЫ АВТОР ПРОВЕЛ НЕСКОЛЬКО СОТЕН
МАШИННЫХ РАСЧЕТОВ ПО ЭТОМУ АЛГОРИТМУ, ПРИЧЕМ СХОДИМОСТЬ
ОКАЗЫВАЛАСЬ ГОРАЗДО БОЛЕЕ БЫСТРОЙ, ЧЕМ ОЖИДАЛОСЬ. дОСТАТОЧНО БЫЛО
ПРИМЕНИТЬ ПРЕОБРАЗОВАНИЕ~(25) ВСЕГО 21~РАЗ, ЧТОБЫ В ВАРИАНТАХ С~$n=6$ И
С ОГРОМНЫМИ ЗНАЧЕНИЯМИ ЭЛЕМЕНТОВ МАТРИЦ~$Q$ И~$R$ ОСТАВАЛОСЬ МЕНЕЕ
500~СЛУЧАЕВ ДЛЯ ПРЯМОГО ПЕРЕБОРА. в РЕЗУЛЬТАТЕ РАСЧЕТЫ НА эвм ЗАНИМАЛИ
ВСЕГО НЕСКОЛЬКО СЕКУНД.

%% 118

\section{D.~рЕАЛИЗАЦИЯ СПЕКТРАЛЬНОГО ТЕСТА}. пРИВЕДЕМ ВЫЧИСЛИТЕЛЬНУЮ
ПРОЦЕДУРУ, ВЫТЕКАЮЩУЮ ИЗ ВСЕГО СКАЗАННОГО ВЫШЕ.

\alg S.(сПЕКТРАЛЬНЫЙ ТЕСТ.) сПЕКТРАЛЬНЫЙ ТЕСТ ПРИМЕНЯЕТСЯ ДЛЯ ОЦЕНКИ ВЫБОРА
МНОЖИТЕЛЯ~$a$ В ЛИНЕЙНОЙ КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ С МАКСИМАЛЬНЫМ
ПЕРИОДОМ. (вОПРОС О РАСПРОСТРАНЕНИИ ЭТОГО ТЕСТА НА ДРУГИЕ ЛИНЕЙНЫЕ
КОНГРУЭНТНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ РАССМОТРЕН В УПР.~20 И~21.) кРОМЕ
ЗНАЧЕНИЯ~$a$ ЗАДАЕТСЯ ТАКЖЕ МОДУЛЬ~$m$. тЕСТ ПРОВЕРЯЕТ СТАТИСТИЧЕСКУЮ
НЕЗАВИСИМОСТЬ ПОСЛЕДОВАТЕЛЬНЫХ ОТРЕЗКОВ ИЗ $n$~ЧИСЕЛ. чАЩЕ ВСЕГО ТЕСТ
ПРИМЕНЯЕТСЯ ПРИ~$n=2$, $3$, $4$ И ИНОГДА ПРИ НЕСКОЛЬКО БОЛЬШИХ ЗНАЧЕНИЯХ~$n$.

в АЛГОРИТМЕ ПРЕДПОЛАГАЕТСЯ, ЧТО НА ВХОДЕ ЗАДАНЫ~$a$, $m$ И~$n$;
ВЫЧИСЛЯЕТСЯ~$q=\nu_n^2$ (СМ.~(12)). иСПОЛЬЗУЮТСЯ
$n\times n\hbox{-МАТРИЦЫ}$~$Q$ И~$R$ И ВСПОМОГАТЕЛЬНЫЕ $n\hbox{-МЕРНЫЕ}$
ВЕКТОРЫ~$X$ И~$c$. вСЕ ОПЕРАЦИИ С ЦЕЛЫМИ ЧИСЛАМИ ДОЛЖНЫ ПРОИЗВОДИТЬСЯ
ТОЧНО; ДЛЯ ЭТОГО МОЖЕТ ПОТРЕБОВАТЬСЯ ПРИВЛЕЧЕНИЕ ОПЕРАЦИЙ С ПОВЫШЕННОЙ
ТОЧНОСТЬЮ. бОЛЕЕ ПОДРОБНО ЭТОТ ВОПРОС БУДЕТ РАССМОТРЕН НИЖЕ.

\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ~$X[1]\asg1$, $X[k+1]\asg (aX[k])\bmod m$
ДЛЯ~$1\le k < n$. еСЛИ КАКОЕ-ЛИБО~$X[k]$ БОЛЬШЕ~$m/2$,
УСТАНОВИТЬ~$X[k]\asg X[k]-m$. зАТЕМ СФОРМИРОВАТЬ МАТРИЦЫ
$$
\eqalign{
Q&=\pmatrix{
   m^2  &  -m X_2 & -m X_3  & \ldots & -m X_n  \cr
 -m X_2 & 1+X_2^2 & X_2 X_3 & \ldots & X_2 X_n \cr
 -m X_3 & X_2 X_3 & 1+X_3^2 & \ldots & X_3 X_n \cr
 \vdots &         &         &        & \vdots  \cr
 -m X_n & X_2 X_n & X_3 X_n & \ldots & 1+X_n^2 \cr
},\cr
R&=\pmatrix{
 \sum X_j^2 & m X_2 & m X_3 & \ldots & m X_n  \cr
      m X_2 & m^2   & 0     & \ldots & 0      \cr
      m X_3 & 0     & m^2   & \ldots & 0      \cr
     \vdots &       &       &        & \vdots \cr
       mX_n & 0     & 0     & \ldots & m^2    \cr
}.\cr
}
\eqno(29)
$$
дЛЯ ЭТОГО УСТАНОВИТЬ~$Q[1, 1]\asg m^2$, $R[1, 1]\asg \sum_{1\le j \le n} X[j]^2$;
ДЛЯ~$1<j\le n$ УСТАНОВИТЬ~$Q[1,j]\asg Q[j,1]\asg -mX[j]$, $R[1,j]\asg R[j,1]\asg mX[j]$,
$Q[j, j]\asg 1+X[j]^2$, $R[j,j]\asg m^2$; И ДЛЯ~$1<j<k\le n$
УСТАНОВИТЬ~$Q[j, k]\asg Q[k, j]\asg X[j]X[k]$, $R[j,k]\asg R[k,j]\asg 0$.
(эТО ТЕ САМЫЕ МАТРИЦЫ~$Q$ И~$R$, КОТОРЫЕ ФИГУРИРУЮТ В~(19), ЗА
ИСКЛЮЧЕНИЕМ ТОГО, ЧТО~$R=m^2Q^{-1}$, А НЕ~$Q^{-1}$, ТАК ЧТО ВСЕ
ПОСЛЕДУЮЩИЕ ВЫЧИСЛЕНИЯ ПРОИЗВОДЯТСЯ С ЦЕЛЫМИ ЧИСЛАМИ.)

дАЛЕЕ ПОЛАГАЕМ~$k\asg n$ И~$q\asg m^2$.

\st[нАЙТИ МИНИМУМ~$Q_{jj}$.] дЛЯ~$1\le j \le n$, ЕСЛИ~$Q[j, j]<q$,
 УСТАНОВИТЬ~$q\asg Q[j, j]$.

%% 119

\st[пЕРЕХОДИТЬ К ПЕРЕБОРУ?] дЛЯ~$1\le j \le n$ УСТАНОВИТЬ~$c[j]\asg \floor{\sqrt{qR[j,j]}/m}$.
еСЛИ ТЕПЕРЬ~$\prod_{1\le j \le n} (2c[j]+1)\le 1000$,
ПЕРЕЙТИ К ШАГУ~\stp{6}. (сОГЛАСНО ЛЕММЕ~A, ДЛЯ МИНИМАЛЬНОГО
РЕШЕНИЯ~$X[1]$,~\dots, $X[n]$ ПРИ ЛЮБОМ~$j$  ВЫПОЛНЯЕТСЯ УСЛОВИЕ---$c[j]\le X[j]\le c[j]$.
сМЫСЛ ДАННОГО ШАГА В ТОМ, ЧТОБЫ ПЕРЕЙТИ НА~\stp{6}, ЕСЛИ
ДЛЯ ПОИСКА ТОЧНОГО МИНИМУМА ТРЕБУЕТСЯ ПЕРЕБРАТЬ НЕ БОЛЕЕ~$1000$,---А НА
САМОМ ДЕЛЕ, КАК БУДЕТ ПОКАЗАНО НИЖЕ,--- МЕНЕЕ $500$~СЛУЧАЕВ. кОНЕЧНО, НЕТ
НЕОБХОДИМОСТИ ВЫЧИСЛЯТЬ ТОЧНОЕ ЗНАЧЕНИЕ~$\prod (2c_j+1)$; ПРИ ЭТОМ, КСТАТИ,
ВОЗМОЖНО ПЕРЕПОЛНЕНИЕ. дОСТАТОЧНО УБЕДИТЬСЯ, ПРЕВЫШАЕТ ЛИ ЭТО ЗНАЧЕНИЕ~$1000$.)

\st[пРЕОБРАЗОВАТЬ.] дЛЯ~$1\le j \le n$, $j\ne k$, ПРИСВОИТЬ~$c[j]$
ЦЕЛЫЕ ЗНАЧЕНИЯ, КАК МОЖНО БОЛЕЕ БЛИЗКИЕ К~$Q[j,k]/Q[k,k]$,
НАПРИМЕР~$\floor{Q[j,k]/Q[k,k]+{1\over2}}$ (СМ.~(27)). зАТЕМ ДЛЯ~$1\le j \le n$,
$j\ne k$ И~$c[j]\ne 0$ ВЫПОЛНИТЬ ОПЕРАЦИИ~$|TRANS|(Q, j, k,-c[j])$ И~$|TRANS|(R, k, j, c[j])$.

оПЕРАЦИЯ~$|TRANS|(P, i, j, t)$ НАД МАТРИЦЕЙ~$P$ ОПРЕДЕЛЯЕТСЯ СЛЕДУЮЩИМ
ОБРАЗОМ. дЛЯ~$1\le r \le n$ УСТАНОВИТЬ~$P[i,r]\asg P[i,r]+tP[j,r]$;
\emph{ЗАТЕМ} ДЛЯ~$1\le r \le n$ УСТАНОВИТЬ~$P[r,i]\asg R[r,i]+tP[r, j]$.
[тАКИМ ОБРАЗОМ, СТРОКА~$j$ УМНОЖАЕТСЯ НА~$t$ И ПРИБАВЛЯЕТСЯ К СТРОКЕ~$i$,
ЗАТЕМ СТОЛБЕЦ~$j$ УМНОЖАЕТСЯ НА~$t$ И ПРИБАВЛЯЕТСЯ К СТОЛБЦУ~$i$. в
РЕЗУЛЬТАТЕ НА ШАГЕ~\stp{4} ПРОИЗВОДИТСЯ ПРЕОБРАЗОВАНИЕ~(24) С
ИСПОЛЬЗОВАНИЕМ МАТРИЦЫ~$U$ ВИДА~(25).]

\st[иЗМЕНИТЬ~$k$.] уМЕНЬШИТЬ~$k$ НА~$1$; ЗАТЕМ, ЕСЛИ~$k=0$,
УСТАНОВИТЬ~$k\asg n$. пЕРЕЙТИ НА~\stp{2}.

\st[пОДГОТОВКА К ПЕРЕБОРУ.] (тЕПЕРЬ БУДЕТ ОПРЕДЕЛЯТЬСЯ АБСОЛЮТНЫЙ
МИНИМУМ С ПОМОЩЬЮ ПРЯМОГО ПЕРЕБОРА.) уСТАНОВИТЬ~$k\asg n$ И~$X[j]\asg 0$
ДЛЯ~$1\le j \le n$.

\st[пЕРЕЙТИ К СЛЕДУЮЩЕМУ ЗНАЧЕНИЮ~$X[k]$.] уСТАНОВИТЬ~$X[k]\asg X[k]+1$.
еСЛИ~$X[k]>c[k]$, ПЕРЕЙТИ НА~\stp{9}.

\st[пЕРЕЙТИ К СЛЕДУЮЩЕМУ~$k$.] уСТАНОВИТЬ~$k\asg k+1$. еСЛИ~$k\le n$,
УСТАНОВИТЬ~$X[k]\asg -c[k]$ И ПОВТОРИТЬ ШАГ~\stp{8}. еСЛИ~$k>n$,
УСТАНОВИТЬ~$q'\asg \sum_{1\le i \le n} \sum_{1\le j \le n} X[i]X[j]Q[i,j]$,
И, ЕСЛИ~$q'<q$, УСТАНОВИТЬ~$q\asg q'$.

\st[уМЕНЬШИТЬ~$k$.] уСТАНОВИТЬ~$k\asg k-1$. еСЛИ~$k\ge 1$,
ВЕРНУТЬСЯ НА~\stp{7}, В ПРОТИВНОМ СЛУЧАЕ ВЫПОЛНЕНИЕ АЛГОРИТМА
ЗАКАНЧИВАЕТСЯ. (зАМЕЧАНИЕ: ШАГИ~\stp{6}--\stp{9} ЯВЛЯЮТСЯ
ПРОСТЕЙШИМ СЛУЧАЕМ МЕТОДА ОБРАТНОГО ПЕРЕБОРА, КОТОРЫЙ ПОДРОБНО ОПИСАН В ГЛ.~7.)
\algend

оПРЕДЕЛЕННАЯ С ПОМОЩЬЮ ЭТОГО АЛГОРИТМА ВЕЛИЧИНА~$q$ ПОЗВОЛЯЕТ
ВЫЧИСЛИТЬ~$\nu_n=\sqrt{q}$ И ОПРЕДЕЛИТЬ~$C_n$ ПО ФОРМУЛЕ~(15). зНАЧЕНИЕ
%%120
ВЕЛИЧИН~$\nu_n$ И~$C_n$ И УСЛОВИЯ, ПРИ ВЫПОЛНЕНИИ КОТОРЫХ МОЖНО
СЧИТАТЬ, ЧТО МНОЖИТЕЛЬ~$a$ ПРОШЕЛ ИСПЫТАНИЕ УДОВЛЕТВОРИТЕЛЬНО,
ОБСУЖДАЛИСЬ ВЫШЕ В ПОДПУНКТЕ~в.

тАК КАК ОБЫЧНО~$m$---ЭТО РАЗМЕР СЛОВА МАШИНЫ, НА КОТОРОЙ ПРОИЗВОДИТСЯ
РЕАЛИЗАЦИЯ АЛГОРИТМА~S, НЕОБХОДИМО ПРИ РАСЧЕТАХ ПО ЭТОМУ АЛГОРИТМУ
ПОЛЬЗОВАТЬСЯ АРИФМЕТИКОЙ НАД ЦЕЛЫМИ ЧИСЛАМИ С УВЕЛИЧЕННОЙ ТОЧНОСТЬЮ.
оПЫТ ПОКАЗЫВАЕТ, ЧТО ДОСТАТОЧНО ТРОЙНОЙ ТОЧНОСТИ (КОГДА КАЖДОЕ ЦЕЛОЕ ЧИСЛО
РАЗМЕЩАЕТСЯ В ТРЕХ ЯЧЕЙКАХ). нАПРИМЕР, ПРИ ПОДГОТОВКЕ ТАБЛ.~1 АВТОР
ИСПОЛЬЗОВАЛ 76-РАЗРЯДНУЮ АРИФМЕТИКУ. эТОГО БЫЛО ДОСТАТОЧНО ПРИ~$m=10^{10}$
И~$n\ge 6$, ОДНАКО ПРИ~$m=2^{35}$ ВО МНОГИХ СЛУЧАЯХ
ПРОИСХОДИЛО ПЕРЕПОЛНЕНИЕ. пО-ВИДИМОМУ, ПОЧТИ ДЛЯ ВСЕХ ВАРИАНТОВ
С~$m=2^{35}$ БУДЕТ ДОСТАТОЧНО ПРИМЕРНО 90~ДВОИЧНЫХ РАЗРЯДОВ.
кАКИХ-ЛИБО ТЕОРЕТИЧЕСКИХ ДАННЫХ ОТНОСИТЕЛЬНО ВЕЛИЧИНЫ
ПРОМЕЖУТОЧНЫХ РЕЗУЛЬТАТОВ ПОКА НЕ СУЩЕСТВУЕТ.

нА ПРАКТИКЕ АЛГОРИТМ~S ОКАЗЫВАЕТСЯ УДИВИТЕЛЬНО ЭФФЕКТИВНЫМ;
ПРИ~$m=2^{35}$ ЧИСЛО ПОВТОРЕНИЙ ШАГОВ~S2--S5 ОКАЗЫВАЛОСЬ РАВНЫМ~$6$, $10$,
$14$, $17$, $21$ ДЛЯ~$n=2$, $3$, $4$, $5$, $6$. оДНАКО ДО СИХ ПОР НЕТ
ТЕОРИИ, ПОЛНОСТЬЮ ОПИСЫВАЮЩЕЙ АЛГОРИТМ, И НА САМОМ ДЕЛЕ В НЕКОТОРЫХ
СЛУЧАЯХ \emph{МЕТОД МОЖЕТ ПРОСТО ЗАЦИКЛИТЬСЯ.} тАК ЧТО ТЕРМИН "АЛГОРИТМ" В
ДАННОМ СЛУЧАЕ, СТРОГО ГОВОРЯ, НЕПРИМЕНИМ. лЕГКО ИЗМЕНИТЬ ЭТУ ПРОЦЕДУРУ ТАК,
ЧТОБЫ ЧИСЛО ИТЕРАЦИЙ БЫЛО ОГРАНИЧЕНО (СМ.~УПР.~16). дОСТАТОЧНО ВВЕСТИ
ЕЩЕ ОДНУ ПЕРЕМЕННУЮ~$d$ И УСТАНАВЛИВАТЬ~$d\asg 0$ НА ШАГЕ~S1 И В
ОПЕРАЦИИ~|TRANS|. кРОМЕ ТОГО, В КОНЦЕ ШАГА~S3 ДОБАВИТЬ: "$d\asg d+1$;
ЕСЛИ~$d>n$, ПЕРЕЙТИ НА~S6". оДНАКО, ВОЗМОЖНО, ЧТО ЭТО ПРИВЕДЕТ К ОЧЕНЬ
ДЛИННОМУ ПЕРЕБОРУ НА ШАГАХ~S6--S9, КАК ПОКАЗАНО В УПР.~18. в ТАКОЙ
СИТУАЦИИ ЗНАЧИТЕЛЬНЫМИ ПРЕИМУЩЕСТВАМИ ОБЛАДАЮТ ПРИЕМЫ, КОТОРЫЕ ОБСУЖДАЮТСЯ
В УПР.~22 И~23. аЛГОРИТМ ЗАЦИКЛИВАЕТСЯ ПРИ~$n=2$, $a=1025$, $m=2^{46}$,
ХОТЯ ПОДОБНАЯ НЕУДАЧА БЫВАЕТ РЕДКО.

в ОДНОМ ИЗ ПРОСЧИТАННЫХ АВТОРОМ СЛУЧАЕВ ПРИ~$n=6$ "ОЖИДАЕМАЯ ДЛИНА
ПЕРЕБОРА"~$\prod (2c_j+1)$ НА ШАГЕ~S3 ПРИНИМАЛА ПОСЛЕДОВАТЕЛЬНО
СЛЕДУЮЩИЕ ЗНАЧЕНИЯ:
$$
\eqalign{
 &1\times 10^{43}, 6\times 10^{42}, 2\times 10^{42}, 9\times 10^{41},
   2\times 10^{41}, 6\times 10^{33}, 4\times 10^{33},\cr
 &1\times 10^{29}, 1\times 10^{20}, 6\times 10^{19}, 4\times 10^{18},
   9\times 10^{12}, 4\times 10^{10}, 3\times 10^{8},\cr
 &1\times 10^8, 8\times 10^7, 1\times 10^7, 7\times 10^6, 1.7\times 10^7,
   1.8\times 10^7, 7\times 10^5,\cr
 &1\times 10^5, 5\times 10^4, 3825, 3825, 675.\cr
}
$$

тАКИМ ОБРАЗОМ, ЭТА ВЕЛИЧИНА УМЕНЬШАЕТСЯ ОТ~$10^{43}$ ДО ЗНАЧЕНИЯ
НИЖЕ~$1000$, ПРИЧЕМ НЕ МОНОТОННО: ДВАЖДЫ ЗНАЧЕНИЕ \emph{УВЕЛИЧИВАЕТСЯ.}
вЕРОЯТНО, ДАЛЬНЕЙШИЕ ИТЕРАЦИИ ЕЩЕ БОЛЬШЕ СНИЗЯТ ЗНАЧЕНИЕ~$675$, ТАК ЧТО,
ПО-ВИДИМОМУ, КОНСТАНТУ~$1000$ В ШАГЕ~S3 СЛЕДУЕТ УМЕНЬШИТЬ, СКАЖЕМ,
ДО~$100$. (\emph{зАМЕЧАНИЕ.} иСТИННОЕ ЧИСЛО НАБОРОВ~$X[1]$,~\dots, $X[n]$,
ИСПЫТАННЫХ В ПОЛНОМ ПЕРЕБОРЕ (ШАГИ
%%121
\bye