\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