2.4. Точные вычисления, использующие модулярную арифметику

Основываясь на результатах теории чисел, представленных в предыдущих разделах, мы собираемся обсудить интересный способ выполнения точных арифметических действий с (большими)

целыми числами. Основная идея состоит в том, чтобы использовать один или несколько модулей (теорема 2.3.25), не имеющих общих делителей, и вместо действий с самими числами выполнять действия с их остатками (Gregory et al., 1984; Knuth, 1969; Scott, 1985).

Рассмотрим сначала случай одного модуля. Пусть нам дано выражение гл) над Z, зависящее от целочисленных аргументов i, и нужно вычислить (оценить) его. Тривиальный подход состоит в непосредственном вычислении выражения над Z; при этом, однако, промежуточные результаты могут не быть целыми числами (могут иметь бесконечные представления, как, например, ), и отбрасывание цифр или округление может привести к неточности окончательного результата. того чтобы избежать этого, нужно воспользоваться обходным путем при вычислении . Этот подход проиллюстрирован на рис. 2.4.1.

Рис. 2.4.1. Окольный путь вычисления выражения (), использующий один модуль.

Вместо вычисления над мы сначала по выражению над получаем эквивалентное выражение над для некоторого , где , или, что эквивалентно, Затем мы вычисляем выражение над и получаем эквивалентный результат , где в завершение мы отображаем обратно в множество целых чисел.

Следует отметить, что отношение эквивалентности не определяет однозначно окончательный результат [Аналогия с задачей «чему равно значение . Очевидно, что значение не определено однозначно, оно может быть равным 7, 20 и т.д. Если, однако, мы откуда либо знаем,

что , то может быть равным только 7.] Для того чтобы однозначно определить нужно иметь априорную оценку его величины; эта оценка используется в качестве модуля , и все операции выполняются в кольце . Если мы имеем оценку на величину , то мы ищем наименьшее неотрицательное решение уравнения если же мы имеем оценку на , то ищем наименьшее по абсолютной величине решение.

Сложности с изложенным методом обхода возникают, когда выполняются операции деления. Как уже отмечалось, в случае когда — простое число, кольцо является конечным полем [оно обозначается также в котором мы можем выполнять все арифметические операции. Поскольку обратный элемент к любому ненулевому элементу всегда существует, мы определяем деление по модулю следующим образом:

где, как отмечалось выше, — мультипликативный обратный элемент к элементу по модулю , который мы будем также обозначать просто через . Частное двух целых чисел в также является целым числом, даже если b не делит а в

Пример.

Число, полученное в этом примере (рассматриваемое как промежуточный результат), имеет смысл, поскольку

Предположим теперь, что модуль ограничивает окончательный результат . Если не является целым числом, принадлежащим , то и для того чтобы получить последнее число, требуется дополнительная информация; эта априорная информация различна для разных случаев и проиллюстрирована ниже двумя примерами. Если, однако, лежит в , то [Напомним еще раз, что — это результат, полученный при вычислении выражения над кольцом целых чисел, тогда

как получается при вычислении в Таким образом, арифметика одного модуля может быть использована для выполнения последовательности точных арифметических операций над целыми числами в даже если эта последовательность включает операции деления; трудности могут возникнуть лишь при интерпретации результатов.

Когда мы хотим вычислить выражение, окончательное значение которого может быть положительным или отрицательным, нам нужно уметь работать с отрицательными числами. Это можно делать, используя симметричное множество которое, как нетрудно видеть, изоморфно множеству отображение между этими двумя множествами показано на рис. 2.4.2.

Рис. 2.4.2. Отображение между симметричным и неотрицательным множествами для р = 11.

Например, имеет наименьшее неотрицательное решение и наименьшее по абсолютной величине решение

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

Пример. Выполним точные арифметические операции в для того чтобы вычислить в этом примере априорная информация состоит в том, что мы ищем результат в

симметричном множестве.

Отображая результат обратно в симметричное множество, мы получаем правильный ответ

В приведенном примере потому что мы знаем с самого начала, что лежит в симметричном множестве для GF(p). В следующем примере это не так.

Пример. Вычислим х = 1/2 — 2/3, пользуясь точно такой же априорной информацией, как и в предыдущем примере. Проводя вычисления, как и в предыдущем примере, получим

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

Перейдем теперь к арифметике нескольких модулей. Использование арифметики нескольких модулей является «естественным» решением проблемы, с которой мы сталкиваемся в арифметике

одного модуля: как мы видели, модуль должен быть достаточно большим, чтобы результат определялся однозначно по его остатку . Однако, когда нам приходится выбирать значение то большим, чем размер компьютерного слова, схема с одним модулем теряет всю свою привлекательность. Поэтому мы используем несколько модулей и применяем окольный путь для вычисления выражения; эта схема иллюстрируется на рис. 2.4.3.

Рис. 2.4.3.

Окольный путь вычисления выражения (), использующий модулей .

Для заданного выражения зависящего от целочисленных аргументов мы сначала вычисляем где и к для коротких модулей m. При условии, что выражения определены над мы вычисляем их над и получаем эквивалентные результаты ; в завершение, пользуясь греко-китайским алгоритмом либо таблицами, мы получаем окончательный результат . Здесь снова модули должны быть выбраны таким образом, чтобы Если дана оценка на то мы ищем наименьшее неотрицательное решение греко-китайской задачи об остатках, если же оценивается то ищется наименьшее по абсолютной величине решение.

Рассмотрим более подробно арифметику нескольких модулей. Знакомые нам всем системы счисления являются линейными, позиционными и весовыми. Это означает, что всем позициям соответствуют веса, зависящие от одного основания. Например, в десятичной системе счисления используются веса и т.д. Вместо этого многомодульная система счисления использует взаимно простые позиционные основания, например 3, 5, 7. В табл. 2.4.1 перечислены числа и их остатки по основаниям 3, 5 и 7.

Таблица 2.4.1 Остатки чисел по основаниям 3, 5, 7

Остатки в табл. 2.4.1 однозначно определяют число; всего имеется различных чисел, представимых в этой системе. Например, вектор [2,1,3] однозначно определяет десятичное число 8 и называется стандартным набором остатков числа 8 относительно данного вектора оснований. В нашем случае вектор является вектором оснований. Мы будем пользоваться обозначением

Как и в случае одного модуля, мы также можем определить наименьшую неотрицательную числовую систему и при условии, что все модули нечетные, наименьшую по абсолютной величине числовую систему, или симметричную систему остатков, относительно данного вектора оснований

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

Теорема 2.4.1. Два целых числа имеют одинаковые стандартные наборы остатков относительно вектора оснований

тогда и только тогда, когда

Доказательство. Доказательство оставляется читателю в качестве упражнения.

Пример. Рассмотрим как в табл. 2.4.1, где Тогда и, значит, .

Из теоремы 2.4.1 следует, что множество содержит М элементов, которые взаимно однозначно отображаются на элементы множества Нетрудно видеть, что два множества с соответствующими операциями сложения и умножения представляют собой изоморфные конечные коммутативные кольца, и, следовательно, многомодульная арифметика эквивалентна арифметике по модулю М.

Главное преимущество многомодульной числовой системы состоит в отсутствии переносов при выполнении операций сложения и умножения. Арифметика замкнута в каждой позиции (т.е. арифметические действия выполняются полностью и независимо в разных позициях). Поэтому можно выполнять сложение и умножение длинных целых чисел так же быстро, как и обычных (коротких) чисел.

На двоичных компьютерах удобно использовать модули вида т.е. каждый модуль на единицу меньше, чем степень двойки. Имеем

В последнем выражении мы складываем младший и старший разряды произведения. Как мы видим, действия по модулю выполняются сравнительно просто. (Если модуль m не имеет такого вида, то при сложении нужно взять и когда и )

В некоторых случаях необходимо знать, являются ли модули взаимно простыми. Если они имеют вид , то для проверки этого можно использовать следующее простое правило: . Из него вытекает, что модули взаимно просты тогда и только тогда, когда числа взаимно просты. Это правило следует из алгоритма Евклида и тождества

Пример. В табл. 2.4.1 рассмотрим числа ; их сумма равна . Точно так же их произведение равно Заметим, что при отсутствии таблицы ответ восстанавливается с помощью греко-китайского алгоритма. Кроме того, если результат операции больше, чем М, то мы не получим правильного ответа; поэтому критическим моментом является правильный выбор вектора оснований.

Мы видим, что время, которое требуется для сложения, вычитания и умножения двух -значных чисел при использовании многомодульной арифметики, равно без учета времени преобразования к модулярному представлению и обратно. сложения и вычитания здесь нет никаких преимуществ, но для умножения может быть достигнуто существенное улучшение по сравнению с обычным методом, требующим времени . Многомодульная арифметика также идеально подходит для параллельных компьютеров.

Для выполнения деления определим мультипликативный обратный к элементу по модулю вектора оснований следующим образом:

Далее, если

Конечно, как и в случае одного модуля, если b не делит а, то результат не может быть проинтерпретирован без дополнительной информации; однако он допустим в качестве промежуточного результата.

Основная трудность при работе с многомодульными числовыми системами заключается в сравнении величины целых чисел. Конечно, можно использовать симметричную систему остатков, вычесть из одного числа другое и затем определить знак разности. К сожалению, проблема этим не решается, поскольку остатки в симметричной системе не несут информации о знаке числа; один из способов определения знака числа состоит в обратном преобразовании к обычному виду, что разрушает саму

идею многомодульной арифметики. Задача определения знака числа может быть решена гораздо лучшим способом с помощью преобразования числа к так называемому представлению со смешанными основаниями (mixed-radix representation). При этом преобразовании мы выполняем только операции многомодульной арифметики. Мы уже встречались с представлением со смешанными основаниями, когда выражали решение в греко-китайском алгоритме в виде

где каждое не превосходит соответствующего модуля называется старшим членом числа . В этой форме знак числа совпадает со знаком его старшего члена. (Отметим, что в форме со смешанными основаниями мы имеем где частные различны для различных позиций . Если , то мы имеем представление с фиксированным основанием; в частности, при получается хорошо знакомое десятичное представление.) При определении знака удобно, чтобы последний модуль в векторе оснований был равен 2, поскольку нужно знать, в какой половине множества возможных чисел лежит результат. Например, на рис. 2.4.2 числа образуют нижнюю половину множества возможных чисел, соответствующую значению а числа — верхнюю половину, соответствующую значению

Предположим теперь, что нам дано представление относительно вектора оснований и мы хотим определить знак числа . Нам нужно преобразовать к форме со смешанными основаниями и определить знак старшего члена. Для этого необходимо вычислить цифры упомянутые выше. Очевидно, что из вытекает

и, следовательно, Мы получили первую цифру. Далее возьмем разность (вычитая из каждого остатка, представляющего ). Имеем

Первая цифра (в смешанном представлении) числа равна нулю, и, следовательно, первые цифры всех последующих чисел

можно будет не рассматривать. Будем считать, таким образом, что размерность вектора равна Найдем затем , (многомодульный) мультипликативный обратный к элементу по модулю где размерности , и вычислим (многомодульное) произведение для того чтобы получить вторую цифру Будем продолжать этот процесс до тех пор, пока не вычислим если его значение равно 0 или 1, то число соответственно положительное или отрицательное, потому что лежит соответственно в нижней или верхней половине возможного множества значений.

Пример. Определим знак числа с вектором оснований . Очевидно, что , или, как было объяснено выше, ; мы сократили вектор оснований до . Для того чтобы получить вторую цифру вычислим ; умножив на этот элемент, получим [4, 2, 1]. Следовательно, и, вычитая из последнего модулярного выражения, получим , или (Теперь мы уже сократили вектор оснований до ) Далее вычисляется и, умножая на этот элемент, мы получаем [2,1]; поэтому Вычитая из последнего модулярного выражения, получаем или (Теперь ) В заключение мы вычисляем и, умножая на этот элемент, получаем [1], откуда следует, что Поэтому является отрицательным числом; действительно,