будете иметь дело со знаковыми числами, то получите 3 = -5. Однако и 11 и -5 имеют одно и то же представление в дополнительном коде (поскольку их разность равна 16), так что в обоих случаях в качестве мультипликативного обратного элемента используется одно и то же содержимое машинного слова.

Рассмотренная теорема непосредственно применима к задаче деления (знакового и беззнакового) на нечетное число d на W-битовом компьютере. Поскольку любое нечетное число является взаимно простьпй с 2", теорема гласит, что если d нечетно, то существует целое d (единственное в диапазоне от О до 2"" -1 или от -2"" до 2"" -1), такое, что dd а l(mod f). Следовательно, для любого п, являющегося делителем d, справедливо соотношение

= (rfs«J(mod2").

Другими словами, nfd можно вычислить путем умножения и на rf, после чего взять правые W6m полученного произведения.

Если делитель d представляет собой четное число, то пусть rf = rf • 2, где rfo нечетно, а it > 1. Тогда просто выполняется сдвиг числа п вправо на к позиций (устраняя нулевые биты), после чего выполняется умножение на rf (сдвиг можно выполнить и после операции умножения).

Ниже приведен код для деления на 7 числа п, кратного 7. Этот код дает корректный результат как при знаковом, так и при беззнаковом делении.

li M,0xB6DB6DB7 Мультипликативное обратное, (5*2**32+1)/7 mul q,M,n q = n/7

Вычисление мультипликативного обратного по алгоритму Евклида

Каким же образом можно вычислить мультипликативное обратное число? Стандартный метод- использование "расширенного алгоритма Евклида". Этот метод вкратце рассматривается далее в приложении к нашей основной задаче, а заинтересовавшимся читателям можно посоветовать обратиться к [49] и [39, раздел 4.5.2].

Пусть задан нечетный делитель d и нам требуется найти число х, такое, что

rf»; = l(modm),

причем в нашей задаче т = 2"" (где W- размер машинного слова). Это может быть выполнено, если будет решено в целых числах дг и у (положительных, отрицательных, равных 0) уравнение

dx + my = l.

Начнем с того, что сделаем d положительным, добавляя к нему достаточное количество раз число m (rf и d + km имеют одно и то же мультипликативное обратное). Затем запишем следующие уравнения (где rf,m > О):

rf(-l) + m(l)=»i-rf, (31,а)

rf(l) + m(0) = rf. (31,6)

Если d = l, поставленная задача решена, так как (31,6) показывает, что jc = l. В противном случае вычислим

Далее умножим уравнение (31,6) на g и вычтем его из (31,а). Это даст нам уравнение d{-\- q) + т{\) = т- d - qd = iem(m -d,d).

Это уравнение справедливо, поскольку мы просто умножили одно из уравнений на константу и вычли его из другого. Если Tem{m-d,d)=l, то задача решена (последнее уравнение и является решением) и x = -l-q .

Повторим описанный процесс с последними двумя уравнениями, получая новое уравнение. Будем продолжать эти действия до тех пор, пока в правой части уравнения не будет получена 1. Тогда множитель при d, приведенный по модулю /и, и будет представлять собой искомое мультипликативное обратное к d.

Если m-d<d , так что первое частное равно О, то третья строка будет точной копией первой, так что второе частное будет ненулевым. Кроме того, в разных источниках зачастую в качестве первой строки используется следующая:

d(0) + m{l) = m,

но в нашем приложении m = 2" невозможно представить в компьютере.

Лучше всего проиллюстрировать описываемый процесс на конкретном примере. Пусть /и=256 и d=7. Тогда процесс вычислений выглядит как показано ниже (для получения третьей строки используется q = [249/7] = 35).

Таким образом, мультипликативным обратным по модулю 256 числа 7 является -73 (или, используя числа из диапазона от О до 255, число 183). Проверяем: 7 • 183 = 1281 s l(mod 256).

Начиная с третьей строки, числа в правом столбце представляют собой остатки от деления чисел, расположенных выше, так что это строго убывающая последовательность неотрицательных чисел, которая, таким образом, должна завершиться О (в примере выше для этого требуется еще один шаг). Кроме того, число перед О должно быть 1 по следующей причине. Предположим, что последовательность остатков завершается некоторым числом Ь, не равным 1, после которого идет число 0. Тогда целое, предшествующее Ь, должно быть кратным b (скажем, числом кЬ) с тем, чтобы следующим остатком в последовательности было число 0. Такие же рассуждения приводят к выводу, что для того, чтобы получить остаток Ь, предшествующим jt,f»

числом должно быть kkjb + b. Продолжая эту последовательность, вы увидите, что

каждое из этих чисел должно быть кратно Ь, включая числа из первых двух строк, которые равны m-d и и являются взаимно простыми.

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

Для проведения данных вычислений на компьютере заметим, что если rf < О, то к нему необходимо прибавить г". Однако в случае арифметики, использующей дополнительный к 2 код, это делать не обязательно; достаточно просто рассматривать d как беззнаковое число, независимо от того, как именно его рассматривает приложение.

Вычисление q должно использовать беззнаковое деление.

Заметим, что все вычисления можно выполнять по модулю т, так как это никак не влияет на правый столбец (его значения все равно остаются в диапазоне от О до m -1). Это важно, так как позволяет нам выполнять вычисления с "одинарной точностью", используя беззнаковую компьютерную арифметику по модулю 2.

Большинство величин в рассматриваемой таблице не обязательно должны бьпъ представлены при вычислениях, например столбец множителей при 256, поскольку при решении уравнения dx + my = \ нас не интересует значение у. Нет необходимости и в представлении d в первом столбце. Оставляя в таблице только необходимое, получим ее сокращенный вид.

255 249 1 7

220 4

37 3

183 1

Программа на языке С для проведения этих вычислений представлена в листинге 10.4.

Листинг 10.4. Алгоритм Евклида поиска мультипликативного обратного по модулю 2

unsigned mulinv(unsigned d) d должно быть нечетно {

unsigned xl, vl, x2, v2, x3, v3, q;

xl = OxFFFFFFPF; vl = -d;

x2 = 1; v2 = d;

while (v2 > 1)

q = Vl/v2;

x3 = xl - q*x2; v3 = vl - q*v2; xl = x2; vl = v2; x2 = x3; v2 = v3;

return(x2);

Причина использования условия цикла v2 > i вместо более естественного v2 ! = i заключается в том, что если при использовании последнего условия функции будет ошибочно передано четное значение, то цикл может никогда не завершиться (если аргумент d четен, v2 никогда не получит значение 1, но в конечном итоге примет значение 0).

Что же вычисляет данная программа, если передать ей четный аргумент? Как и следует из формул, она вычисляет число jc, такое, что dx = O(mod 2"), которое вряд ли может

оказаться полезным. Однако минимальные изменения в программе (изменение условия цикла на v2 ! = О и возврат значения х1 вместо х2) приводят к вычислению ею числа jc,