уравнений, когда коэффициенты представлены в формате с плавающей точкой, а матрица коэффициентов плохо обусловлена. В таком виде коэффициенты трактуются как точные рациональные числа. Модульный способ дает более быстрый метод вычисления истинных результатов быстрее, чем традиционные методы могут дать приближенный ответ! Последующие достижения в этой области опубликованы в работе М. Т. McClellan, JACM 20 (1973), 563-588. Исследования, посвященные ограничениям в применении этого метода, опубликованы в работе Е. Н. Bareiss, J. Inst. Math, and Appl. 10 (1972), 68-104.

Опубликованная литература по модулярной арифметике ориентирована, главным образом, на разработку компьютеров, так как свойства свободного переноса модулярной арифметики делают ее привлекательной с точки зрения быстродействующих операций. Эта идея впервые была опубликована А. Свободой (А. Svoboda) и М. Валахом (М. Valach) в чехословацком журнале Stroje па Zpracovani Informaci {Information Processing Machines) 3 (1955), 247-295, a затем независимо - X. Л. Гар-нером (Н. L. Garner) [IRE Trans. ЕС-8 (1959), 140-147]. Использование модулей 2*j -1 было предложено А. С. Френкелем в работе JACM8 (1961), 87-96, а некоторые преимущества модулей такого вида продемонстрированы А. Шёнхаге (А. Schonhage) [Computing 1 (1966), 182-196]. Дополнительную информацию и исчерпывающую библиографию по этому вопросу можно найти в книге N. S. Szabo, R. I. Тапака Residue Arithmetic and its Applications to Computer Technology (New York: McGraw-Hill, 1967). В 1968 году опубликована книга И. Я. Акинского и Д. И. Юдицкого, в которую включена глава, посвященная комплексным модулям [см. Rev. Roumaine de Math. Pures et Appl. 15 (1970), 159-160]*. Обсуждение модулярной арифметики будет продолжено в разделе 4.3.3В.

Сообщение на доске объявлений гласило, что он находится в комнате 423, но при взгляде на план системы нумерации, с виду логичной, складывалось впечатление, будто ее разрабатывал либо лунатик, либо математик. - РОБЕРТ БЭРНАРД (ROBERT BARNARD), The Case of ttie Missing Bronte (1983)

УПРАЖНЕНИЯ

1. [20] Найдите все целые числа и, удовлетворяющие всем следующим условиям: и mod 7 = 1, и mod 11 = 6, и mod 13 = 5, О < и < 1000.

2. [М20] Будет ли теорема С по-прежнему справедливой, если допустить, что a,ui,U2,. . ... ,Ut и и - произвольные вещественные числа (а не только целые)?

► 3. [Мйб] {Обобщенная китайская теорема об остатках.) Пусть mi,m2,... ,тт-положительные целые числа, m - наименьшее общее кратное чисел mi,m2,.. ,тг и пусть а, «1, «2,..., «г-произвольные целые числа. Докажите, что имеется точно одно целое число и, удовлетворяющее соотношениям

а < и < а + т, и = щ (по модулю mj), 1 < j < г,

при условии, что

Ui = Uj (по модулю gcd(mi, mj)), 1 < i < J < г,

и что если последнее условие не выполняется, то такого целого числа и не существует.

* См. Акинский И. Я. и Юдицкий Д. И. Машинная арифметика в остаточных классах. - М.: Сов. радио, 1968. -440 с. (1970). - Ярил*, перев.

4. [20] Продолжите процесс, представленный в (13). Чему будут равны тпу, ms, mg, ...?

► 5. [М23] Предположим, что метод, определенный в (13), продолжен до того момента, когда уже нельзя выбрать ни одного нового числа mj. Получим ли мы этим "вульгарным" методом наибольшее возможное значение произведения mim2 тт, такое, что все mj будут положительными целыми числами, меньшими 100, и попарно взаимно простыми?

6. [М22] Пусть е, f и д - неотрицательные целые числа.

a) Покажите, что 2" = 2f (по модулю 2 - 1) в Том и только в том случае, когда е = / (по модулю д).

b) Для заданных е mod / = d и се mod / = 1 докажите тождество

((1 + 2"* + • • + 2"-) • (2 - 1)) mod (2 - 1) = 1.

(Таким образом, получена сравнительно простая формула для величины, обратной 2 - 1, по модулю 2 - 1, как это и требуется в (23).)

► 7. \М21] Покажите, что (24) можно переписать следующим образом:

v\ *г- и\ mod mi,

«2 («2 - V\) Cl2 mod 7712,

«3 4- («3 - («1 + miW2)) C13C23 mod тз.

Vt *r- {ur - (vi + mi{V2 + m2(W3 H-----F-mr-2Wr-l) . • . )))cir . . .C(r l)r mod77?.r.

Если это сделать, то вместо г(г - 1)/2 констант dj, как в (24), потребуется только г - 1 констант Cj - cij .. C(j i)j modTTij. Оцените с точки зрения вычислений на компьютере достоинства и недостатки настоящего варианта формулы (24) по сравнению с ее исходным вариантом.

8. [М21] Докажите, что число и, определенное формулами (24) и (25), удовлетворяет условию (26).

9. [М20] Покажите, как перейти от значений vi, ..., «г, фигурирующих в уравнении (25) и представленных в нем в системе со смешанным основанием, обратно к исходным остаткам «1, ..., Ur, используя для вычислений значений щ только арифметические операции вычисления остатка по модулю mj.

10. [М25] .Целое число и, принадлежащее симметричной области (10), можно было бы представить при помощи чисел щ, ..., Ur, таких, что и = Uj (по модулю mj), удовлетворяющих условию -mj/2 < Uj < mj/2 вместо условия О < «j < mj, как указано в тексте раздела. Рассмотрите процедуры модулярной арифметики для такого симметричного представления, включая процедуру перевода (24).

11. [М23] Допустим, все числа mj-нечетные и известно, что и = {ui,...,Ur) - четное число при О < и < т. Используя мод>лярную арифметику, найдите достаточно быстрый способ вычисления и/2.

Обратите внимание на тождество 2t 2±i = ( (по модулю т). В общем случае, если W и m являются взаимно простыми, можно найти (по алгоритму Евклида) число v = (t;i,..., vr), такое, что vv = 1 (по .модулю т). Далее, если известно, что и кратно t;, то u/v = uv вычисляем при помощи модулярного умножения. Если v не является взаимно простым с т, то деление выполняется значительно сложнее.

12. [MiO] Докажите, что, если О < и, w < т, модулярное сложение чисел ии v приведет к переполнению (т. е. полученное число будет находиться за пределами допустимой области) тогда и только тогда, когда сумма меньше числа и. (Таким образом, проблема обнаружения переполнения эквивалентна проблеме сравнения.)

► 13. [М25] (Автоморфы.) Десятичное п-разрядное число х > 1 математиками-шутниками называется автоморфом, если последние п цифр числа равны х. К примеру, 9 376 есть 4-разрядный автоморф, так как 9 376 = 87909 376. [См. Scienti&c American 218 (January, 1968), 125.]

a) Докажите, что п-разрядное число х > 1 есть автоморф тогда и только тогда, когда X mod 5" = О (или 1) и х mod 2" = 1 (или 0) соответственно. (Таким образом, еати mi = 2" и тг = 5", то в (7) только числа Mi и Мг являются п-разрядными автоморфами.)

b) Докажите, что если х есть п-разрядный автоморф, то (Зх - 2х) mod 10" является 2п-разрядным автоморфом.

c) Пусть известно, что сх = 1 (по модулю у). Найдите простую формулу для числа с, являющегося функцией с и х, но не у, которая (формула) имеет вид сх = 1 (по модулю

► 14. [МЗО] {Мерзкое умножение.) По определению циклическая свертка (xo,xi,... ,x„ i) и (г/о,г/1,. •. jj/n-i) есть {zo,zi,...,Zn-i), где

Zk- x,j/j для Q<k <п.

i+j=fc (по модулю п)

Эффективные алгоритмы для циклической свертки будут рассмотрены в разделах 4.3.3 и 4.6.4.

Рассмотрим д-битовые целые числа иа v, которые представлены в виде

*:=0 fc=0

где О < Uk,Vk < г*"-"*"-. (Такое представление является смесью оснований 2U/"J и 29/"!.) Используя подходящую циклическую свертку, предложите хороший способ поиска представления числа

w-{uv) mod (2-1). [Указание. Не бойтесь использовать вычисления в формате с плавающей точкой.]

М.З.З. Насколько быстро можно выполнять умножение

Для умножения т-разрядного числа на п-разрядное традиционным методом (алгоритм 4.3.1М) требуется приблизительно стп операций, где с - константа. Для простоты в этом разделе предположим, что m = п, и обсудим следующий вопрос: Для любого ли обычного вычислительного алгоритма умножения двух п-разрядных чисел время выполнения пропорционально п по мере увеличения п? {В этом вопросе под термином "обычный" понимается алгоритм, воспринимающий в качестве входа число п и два произвольных п-разрядных числа в позиционной интерпретации и на выходе дающий произведение этих чисел также в позиционной интерпретации. Безусловно, если бы можно было для каждого значения п выбрать свой алгоритм, вопрос не представлял бы интереса, так как для любого конкретного значения п умножение можно было бы выполнить, просто отыскав результат в некоторой огромной таблице. Под термином "вычислительный алгоритм" понимается алгоритм, пригодный для применения на цифровом компьютере, подобном MIX, а вре.мя выполнения - это время, затраченное на таком компьютере на получение результата по такому алгоритму.)