8.6. ПРИМЕНЕНИЕ КИТАЙСКОЙ ТЕОРЕМЫ ОБ ОСТАТКАХ

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

Лемма 8.2. Пусть произведение всех кроме (т. е. где ). Положим (т. е. ). Тогда

Доказательство. Поскольку числа попарно взаимно просты, то, как известно (упр. 7.9), числа существуют и единственны. Кроме того, делится на при так что при Поэтому

Так как то

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

Наша задача состоит в эффективном вычислении (8.20). Сразу трудно увидеть, как можно вычислять по не прибегая к методу проб и ошибок. Позже мы увидим, что эта задача не так уж трудна, если использовать алгоритм Евклида из разд. 8.8 и его быструю реализацию из разд 8.10. В данном разделе мы изучим только ту форму китайской задачи об остатках, которая основана на "предварительной обработке". Если часть входных данных фиксирована для ряда задач, то все величины, зависящие только от этой фиксированной части, можно вычислить заранее и считать частью входа. Алгоритм, в котором сделаны такие предварительные вычисления, называют алгоритмом с предварительной обработкой данных

Для китайского алгоритма с предварительной обработкой данных входом будут служить не только вычеты и модули но и обратные к ним (числа ). Эта ситуация не является нереальной. Если часто применять китайский алгоритм для перевода чисел, представленных вычетами по фиксированному множеству модулей, то разумно заранее вычислить те функции от этих модулей, значения которых используются в алгоритме. В следствии теоремы 8.21 мы увидим, что на оценку сложности наличие предварительной обработки (или ее отсутствие) влияет весьма скромно.

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

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

(как в алгоритме 8.4), а затем — целые числа

Если то Если то вычисляем по формуле получаем что и нужно для (8.20).

Алгоритм 8.5. Быстрый китайский алгоритм с предварительной обработкой данных

1. Попарно взаимно простые целочисленные модули где для некоторого

2. Множество "обратных" к ним чисел т. е. таких, что где

3. Последовательность вычетов

Выход. Единственное целое число для которого

Рис. 8.4. Программа вычисления целого числа по его модульному представлению.

Метод. Сначала вычисляем как в алгоритме 8.4. Затем запускаем программу на рис. 8.4 в предположении, что в ней

Пример 8.6. Пустьро, равны соответственно . Тогда для Далее,

Таким образом, в строке 1 вычисляются

Затем выполняется цикл в строках 3, 4 с Здесь принимает значения и 2; следовательно,

Далее выполняется цикл в строках 3, 4 с принимает только значение 0. Получаем

Рис. 8.5. Вычисления из примера 8.6.

Таким образом, результатом строки 5 будет т. е. 59. Можете проверить, что вычеты числа 59 по модулям 2,3, 5 и 7 равны 1, 2, 4 и 3 соответственно. На рис. 8.5 эти вычисления изображены графически.

Теорема 8.11. Алгоритм 8.5 правильно вычисляет целое число и, для которого

Доказательство. Элементарная индукция по показывает, что принимает нужное значение, т. е.

Корректность алгоритма непосредственно следует из леммы 8.2, т. е. из справедливости формулы (8.20).

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

и, для которого за время где время умножения двух -битовых чисел.

Доказательство. Вычисление чисел занимает времени 1). Для анализа тела алгоритма заметим, что содержит не более битов, ибо является суммой слагаемых, каждое из которых равно произведению целых чисел, состоящих не более чем из битов. Поэтому каждое слагаемое содержит не более битов, а сумма таких слагаемых — не более битов. Таким образом, строка 4 занимает время Об Цикл в строках 3, 4 повторяется раз для фиксированного так что весь цикл выполняется за

шагов, а в силу обычного предположения о росте функции это не превосходит Так как цикл в строках 2—4 итерируется раз, то общая сложность составляет Об шагов. Легко показать, что сложность строки 5 меньше.

Следствие. Китайский алгоритм с предварительной обработкой данных, примененный к модулям по битов в каждом, работает не более Об времени.