16.1. Арифметика больших чисел
305
гичным образом можно продублировать и операцию умножения. Мы можем
проверять правильность
˜
c
после каждого сложения или умножения, опреде-
ляя, выполняется ли соотношение
c
mod
t
= ˜
c
. Впрочем, гораздо эффектив-
нее проводить все эти проверки в самом конце.
Выполнять операцию сложения по модулю
n
лишь немного труднее, чем
обычную операцию сложения. Вместо того чтобы просто записать
c
= (
a
+
b
) mod
n
, мы представляем это как
c
=
a
+
b
+
k
·
n
, где число
k
выбрано таким
образом, что результат
c
находится в диапазоне
0
, . . . , n
−
1
. Это всего лишь
другой
способ записи взятия числа по модулю. В данном случае
k
равно 0 или
−
1
при условии, что числа
a
и
b
лежат в диапазоне
0
, . . . , n
−
1
. Соответствую-
щее выражение с использованием вупинга выглядит как
˜
c
= (˜
a
+˜
b
+˜
k
·
˜
n
) mod
t
.
Отметим, что внутренняя реализация операции сложения по модулю “знает”
k
. Нам необходимо лишь получить от библиотеки значение
k
, чтобы можно
было вычислить
˜
k
.
Умножение по модулю выполнить гораздо сложнее. В этом случае нужно
снова записать
c
=
a
·
b
+
k
·
n
. Чтобы вычислить
˜
c
= ˜
a
·
˜
b
+ ˜
k
·
˜
n
(mod
t
)
, мы
должны знать
˜
a,
˜
b,
˜
n
и
˜
k
. Первые три числа у нас уже есть, а вот значение
˜
k
нужно каким-то образом извлечь из
функции умножения по модулю. Это
можно сделать при создании библиотеки “с нуля”, однако модифицировать
существующую библиотеку будет весьма сложно. В качестве универсально-
го решения можно предложить следующее: вычислить
a
·
b
, а затем поде-
лить полученный результат на
n
, используя деление “в столбик”. Полученное
частное и будет тем самым значением
k
, которое необходимо для вычисления
WOOP
(
k
)
. Остаток от деления — это результат
c
. Единственным недостатком
универсального
метода является крайне медленная скорость его выполнения.
Применив вупинг к операции умножения по модулю, это несложно сде-
лать и для операции возведения в степень по модулю. Большинство функ-
ций возведения в степень по модулю вычисляют результат посредством ряда
обычных умножений по модулю. (Некоторые из них используют отдельную
функцию возведения в квадрат по модулю, но и ее можно продублировать
с помощью вупинга как обычную операцию умножения по модулю.) Доста-
точно лишь сохранять для каждого большого числа
x
значение WOOP
(
x
)
и вычислять WOOP каждого произведения как произведение значений
WOOP входных чисел.
Как видите, алгоритмы, использующие вупинг, вычисляют WOOP резуль-
тата выражения на основе значений WOOP входных чисел. Если значение
WOOP одного или нескольких входных чисел окажется неверным, WOOP
результата выражения практически наверняка также окажется неверным.
Другими словами, ошибка хотя бы в одном значении WOOP распространится
и на конечный результат.