то все множители v{t{x)) имеют степень > deg(t;). Критерий Перрона дает большой запас неприводимых полиномов v(x).

► 40. [М20] (П. Ш. Ванг (Р. S. Wang).) Если и„-старший коэффициент полинома и{х) и В - граница коэффициентов некоторого множителя и, то для алгоритма разложения, приведенного в тексте раздела, требуется найти разложение по модулю р, где > 2\un\B. Но \un \ может быть больше, чем В, когда В выбирается по методу из упр. 21. Покажите, что если полином и{х) приводим, то существует способ восстановления одного из его истинных множителей по разложению по модулю р", когда р > 2В, с помощью алгоритма из упр. 4.5.3-51.

41. [М47] (Визами (Beauzamy), Тревисан (Trevisan) и Ванг (Wang).) Докажите или опровергните следующее: существует константа с, такая, что если /(ж) - некоторый целый полином с коэффициентами, по абсолютному значению не превосходящими В, то один из его неприводимых множителей имеет коэффициенты, ограниченные величиной сВ.

4.6.3. Вычисление степеней

В этом разделе рассматривается интересная задача-эффективное вычисление х" по данным X и п, где п - положительное целое число. Предположим, например, что необходимо вычислить ж? Можно просто начать с ж и 15 раз умножить его на X. Но тот же ответ можно получить всего за четыре умножения, если несколько раз возвести в квадрат получающийся результат, последовательно вычисляя х, ж*, х .г16

Эта же идея, в целом, применима к любому значению п следующим образом. Запкщем п в виде числа в двоичной системе счисления (убирая нули слева). Затем заменим каждую "1" парой символов SX, каждый "О"-символом S и вычеркнем крайнюю слева пару символов "SX". Результат представляет собой правило вычисления х", в котором "S" трактуется как операция возведения в квадрат, а "X" - как операция умножения на х. Например, п = 23 имеет двоичное представление 10111. Таким образом, мы формир5ем последовательность SXSSXSXSX, из которой удаляем начальную пару SX для получения окончательного правила SSXSXSX. Это правило гласит, что необходимо "возвести в квадрат, возвести в квадрат, умножить на X, возвести в квадрат, умножить на х, возвести в квадрат и умножить на ж", т. е. последовательно вычислить значения х, ж*, х, х°, х, х, х.

Этот бинарный метод можно легко обосновать, проанализировав последовательность степеней при вычислении: рассматривая каждое "S" как операцию умножения на 2, а "X" - как операцию прибавления 1 и начав с 1, а не с ж, мы придем к вычислению п в соответствии со свойствами двоичной системы счисления. Этот метод очень древний; он появился до 200 г. до н. э. в классической индусской Чалда-сутре {Chandah-sutra) Пингалы (Pingala) [см. В. Datta and А. N. Singh, History of Hindu Mathematics 2 (Lahore: Motilal Banarsi Das, 1935), 76]. Похоже, что в течение следующего тысячелетия этот метод не упоминался нигде за пределами Индии. В 952 г. н. э. аль-Уклидиси (al-Uqlldisl) из Дамаска четко пояснил, как эффективно вычислить 2" для произвольного п. См. The Arithmetic of al-UqlldisI Ъу A. S. Saidan (Dordrecht: D. Reidel, 1975), 341-342, где общие идеи проиллюстрированы на примере п = 51. См. также работу аль-Бируни (al-BlrunI) Chronology of Ancient Nations, переведенную и отредактированную Э. Сащо (Е. Sachau) (London, 1879), 132-136. Эта арабская работа И века оказала сильное влияние на развитие математики.

Инициализация •

Деление Л пополам

Нечетно

Умножение Y на, Z

Четно

Возведение Z в квадрат

Рис. 13. Вычисление ж", основанное на сканировании двоичной записи п справа налево.

Бинарный метод "S и X" для получения х" не требует дополнительной памяти, за исключением памяти для хранения х и текущего промежуточного результата, а потому он удобен для аппаратной реализации на бинарном компьютере. Метод легко программируем, однако требует сканирования двоичного представления числа п слева направо, в то время как компьютерные программы обычно делают это в обратном направлении, в связи с тем, что доступные операции деления на 2 и взятия остатка по модулю 2 выводят двоичное представление числа справа налево. Поэтому зачастую более удобным оказывается следующий алгоритм, основанный на сканировании числа справа налево.

Алгоритм А {Бинарный метод возведения в степень справа налево). Этот алгоритм (рис. 13) вычисляет значение г", где п - положительное целое число (здесь х принадлежит любой алгебраической системе, в которой определено ассоциативное умножение с единичным элементом 1).

А1. [Инициализация.] Установить N ir- п, Y ir- 1, Z +- х.

А2. [Деление N пополам.] (В этот момент х" = Y Z.) Установить N +- [A72J и одновременно определить, было ли N четно. Если N было четно, перейти к шагу А5.

A3. [Умножение Y на Z] Установить У +- Z, умноженное на Y.

А4. [N - О?] Если 7V = О, то выполнение алгоритма прекращается с У в качестве результата.

А5. [Возведение Z в квадрат.] Установить Z +- Z, умноженное на Z, и вернуться к шагу А2. I

В качестве примера применения алгоритма А рассмотрим пошаговое вычисле-

ние X

Соответствующая алгоритму А М1Х-программа приведена в упр. 2.

Великий вычислитель аль-Каши (al-KashI) сформулировал алгоритм А в 1427го-ду [Историко-математические исследования 7 (1954), 256-257]. Этот алгоритм тесно связан с процедурой умножения, в действительности использовавшейся египетскими математиками за 2000 лет до н. э. Если заменить шаг A3 на "F У -ь Z] а шаг А5 на "Z Z + Z" и если установить Y равным нулю, а не единице на шаге А1, то в результате работы алгоритма получится У = пх. [См. А. В. Chace, The Rhind Mathematical Papyrus (1927); W. W. Struve, Quellen und Studien zur Geschichte der Mathematik Al (1930).] Это практичный метод умножения чисел вручную, поскольку используются только простые операции удвоения, деления пополам и сложения. Часто его называют русским крестьянским методом умножения, так как Запад стал свидетелем его популярности в России в 19 веке.

Количество умножений, требуемых алгоритмом А, составляет

[IgnJ +v{n),

где i/(n) равно количеству единиц в двоичном представлении числа п. Это на одно умножение больше, чем при бинарном методе "слева направо", о котором упоминалось в самом начале данного раздела, так как при первом вьшолнении шага A3 просто производится умножение на единицу.

Из-за дополнительного времени на накладные расходы этого алгоритма метод не так хорош для малых значений п, скажем, для п < 10, если, конечно, время, необходимое для умножения, сравнительно невелико. Если значение п известно заранее, то предпочтителен двоичный метод "слева направо" Иногда, например при вычислении ж" mod «(ж), которое обсуждалось в разделе 4.6.2, гораздо проще умножать на х, чем выполнять обобщенное умножение или возведение в квадрат, так что двоичные методы для возведения в степень в таких случаях, в первую очередь, подходят для очень больших значений п. Для вычисления точного значения х" с многократной точностью при целом г, большем, чем размер компьютерного слова, бинарные методы не слишком хороши до тех пор, пока п не станет столь огромным, что высокоскоростное умножение (см. раздел 4.3.3) будет неприменимо. Однако такие приложения очень редки. Точно так же двоичный метод мало пригоден для возведения в степень полиномов [см. в R. J. Fateman, SICOMP 3 (1974), 196-213, обзор публикаций по проблеме возведения полиномов в степень].

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

Уменьшение количества операций умножения. Несколько авторов без доказательства опубликовали утверждение о том, что двоичный метод дает минимально возможное число умножений. Однако это утверждение неверно, и простейший контрпример - п = 15, при котором двоичный метод требует шести умножений, в то время как у = х можно вычислить с помощью двух умножений и х = у - С помощью еще трех, т. е. получить требуемый результат, выполнив всего пять умножений. Обсудим теперь несколько других процедур для вычисления х", в предположении, что п известно заранее. Такие процедуры особенно интересны, например, при генерировании машинного кода оптимизирующим компилятором.