"выбрасывания девяток", который использовался для определения и mod 9 в случае, когДа и выражалось в десятичной системе.

Обратный переход от модулярного представления к позиционной системе счисления вьшолняется немного сложнее. В связи с этим интересно отметить, как изучение способов вычисления приводит к пересмотру критериев оценок математических доказательств. В теореме С утверждается, что возможен переход от (щ,... ,Ur) к и, и приводятся два доказательства. Первое из рассмотренных доказательств считается классическим; оно основывается лишь на самых простых понятиях, а именно:

i) любое число, кратное mi, тг, ... и тПг, должно быть кратным mim2. .Шг, если числа т , попарно взаимно просты;

ii) если тп предметов поместить в тп ящиков так, чтобы ни в каком ящике не было двух предметов одновременно, то в каждом ящике должно быть по одному предмету.

Согласно традиционным понятиям математической эстетики это, несомненно, наилучший способ доказательства теоремы С. Но с точки зрения вычислительной он никуда не годится! Это все равно что сказать: "Попробуйте перебирать и = а, а + 1,..., пока не найдете значение, для которого u = ui (по модулю mi),... , м = «г (по модулю Шг)".

Второй способ доказательства теоремы С более конкретен. Он показывает, как вычислить г новых констант Мх,.. .,Мг и получить решение, выражаемое через данные константы, с помощью формулы (9). В этом доказательстве используются более сложные понятия (например, теорема Эйлера), но с вычислительной точки зрения оно гораздо более удовлетворительно, поскольку константы Мх,..., Mr определяются только один раз. С другой стороны, определение констант Mj при помощи уравнения (8) является нетривиальной задачей, так как вычисление Эйлеровой у-функции в общем случае требует факторизации, т. е. разложения чисел thj на простые сомножители. Существует много способов вычисления Mj, лучших, чем использование (8). В связи со сказанным можно снова подчеркнуть разницу между математической элегантностью и вычислительной эффективностью. Но даже после нахождения Mj при помощи лучшего из возможных способов можно столкнуться с фактом, что Mj слишком велико. Таким образом, использование (9) приводит к большому числу вычислительных операций с высокой точностью, а именно этого нам хотелось бы избежать прежде всего.

Поэтому, чтобы найти действительно пригодный для практического применения метод перехода от (их, -.., Иг) к и, необходимо иметь лучшее доказательство теоремы С. Такое доказательство предложено в 1958 году X. Л. Гарнером (Н. L. Garner). Оно основано на использовании (2) констант dj для I < i < j < г, где

c,jm, = l (по модулю m ,). (23)

Константы Cij легко вычисляются при помощи алгоритма Евклида, так как алгоритм 4.5.2Х для заданных i и j позволяет определить а и Ь, такие, что атп{ + bmj = gcd(mi,mj) = 1, и можно положить = а. Простой метод определения Cij для модулей специального вида 2- - 1 приведен в упр. 6.

Так как aj удовлетворяет условию (23), можно выполнить присвоения

Vl <г- ui mod mi,

«2 <- (u2 - Vl) Ci2 mod m2,

«3 <-((из-t;i)ci3-U2)c23modm3, (24)

Vr <- {... {{Ur - Vl) Cir - иг) C2r-----Vr-l) C(r-l)r mod ТПг.

Тогда число

и - VrTTir-i... m2mi +----F- U3m2mi + V2ini + Vi (25)

будет удовлетворять условиям

О < u < m, u = Uj (no модулю thj) для 1 < j <r. (26)

(Cm. упр. 8; другой способ записи формул (24), не требующий такого большого количества констант, приведен в упр. 7.) Формула (25) -это представление по смешанному основанию числа и, которое можно перевести в двоичный либо десятичный формат, используя методы, описанные в разделе 4.4. Если интервал О < и < m не является необходимым, то после завершения процесса перевода к нему можно добавить (или вычесть из него) соответствующее число, кратное т. Преимущество метода, представленного в (24), состоит в том, что для вычисления Vj используется только арифметика по модулю mj, которая уже встроена в алгоритмы этого класса. Более того, соотношения (24) позволяют выполнять вычисления параллельно. Можно начать с присвоения {vi,... ,Vr) <- {щ mod mi, ..., Ur mod m), затем в момент j при 1 < j < г сразу же получить Vk <- (vk - Vj)cjk modm*, для j < к < г. Другой способ вычисления представления числа по смешанно.му основанию, обеспечивающий возможность достижения параллелизма, рассматривается в интересной статье А. С. Френкеля (А. S. Fraenkel), опубликованной в журнале Ргос. АСМ JVat. Conf. 19 (Philadelphia, 1964), El.4. Важно отметить, что представление (25) по смешанному основанию пригодно для сравнения величин двух чисел, заданных в модулярном представлении. Так, если известно, что 0<и<тиО<и<т, можно сказать, будет ли U < и, если сначала выполнить переход к (ui,..., и) и к (и(,..., и), а затем в соответствии с лексикографическим правилом проверить выполнение неравенств Vr < vr или = uJ. и Vr i < uj. i и т. д. Нет необходимости переходить к двоичной или десятичной системе счисления, если нужно всего лишь выяснить, будет ли (uj,.. .,и) меньше, чем (uJ,... ,uj.).

Операции сравнения двух чисел или определения знака числа при модулярном представлении интуитивно понятны и очень просты, поэтому можно было бы ожидать, что удастся найти значительно более легкий способ выполнения такого сравнения, чем переход к представлению со смешанным основанием. Но из приводимой ниже теоремы следует, что шансов на поиск существенно более легкого метода мало, поскольку величина числа в модулярном представлении существенным образом зависит от всех битов всех остатков (ui,..., и)-

Теорема S (Николаш Сабо (Nicholas Szabo), 1961). Используя введенные выше обозначения, предположим, что mi < у/тп, и пусть L - произвольное значение.

удовлетворяющее неравенству

тпг <L<m-mi. (27)

Пусть д -произвольная функция, такая, что ряд {(0), (1),..., g{mi -1)} содержит меньше значений, чем т\. Тогда существуют такие числа и и v, что

д{и mod mi) = g{v mod mi), umodmj = v modmj при 2 < j < r; (28)

0<u<L<i;<m. (29)

Доказательство. Так как согласно предположению должны существовать числа и ф V, удовлетворяющие (28), д должно принимать одинаковые значения для двух различных остатков. Пусть (и, и)-пара таких значений, удовлетворяющая равенству (28) при О < U < и < т, для которых и минимально. Поскольку u = u - mi и v = V - mi также удовлетворяют равенству (28), в силу минимальности и мы должны получить и < 0. Отсюда следует, что и <mi < Ь,и, если неравенство (29) не выполняется, получаем v < L. Hov > и, av - u кратно тг ... = m/mi, так что V > V - и > m/mi > mi. Поэтому, если неравенство (29) для {u,v) не выполняется, оно будет удовлетворяться для пары {u",v") = (v - mi, и + т - mi).

Разумеется, подобный результат может быть доказан для любого mj вместо mi; можно было бы также заменить неравенство (29) условием a<u<a-t-L<u< а + т, внеся при этом незначительные изменения в доказательство. Таким образом, теорема S показывает, что многие простые функции не могут использоваться для определения области, которой принадлежит число в модулярном представлении.

Напомним теперь главные моменты, которые рассматривались в этом разделе. Применение модулярной арифметики может дать значительное преимущество в приложениях, в которых основная доля вычислений приходится на точное умножение (или возведение в степень) больших чисел в сочетании со сложением и вычитанием, но в которых очень редко появляется необходимость в делении либо сравнении чисел или не нужно проверять, не "выходят" ли промежуточные результаты за пределы области. (Важно не забывать последней оговорки; существуют методы проверки принадлежности числа данной области (один из них рассмотрен в упр. 12), но они настолько сложны, что сводят на нет все преимущества модулярной арифметики.) Некоторые приложения вычислений с применением модулярной арифметики рассмотрены X. Такахаси (Н. Takahasi) и Й. Ишибаши (Y. Ishibashi) в работе, опубликованной в Information Proc. in Japan 1 (1961), 28-42.

Примером такого приложения является точное решение линейных уравнений с рациональными коэффициентами. По различным причинам в этом случае удобно предположить, что модули mi, тг, ..., т являются простыми числами; линейные уравнения могут решаться независимо по каждому модулю mj. Эта процедура была подробно исследована И. Борошем (I. Borosii) и А. С. Френкелем (А. S. Fraenkel) [Math. Сотр. 20 (1966), 107-112] и в дальнейшем усовершенствована А. С. Френкелем и Д. Левенталем (D. Loewenthal) [J. Res. National Bureau of Standards 75B (1971), 67-75]. При помощи этого метода на компьютере CDC 1604 меньше чем за 20 мин было получего 9 независимых решений системы из 111 линейных уравнений со 120-ю неизвестными. Та же процедура полезна и для решения систем линейных