38 35 42 29 31 56 44 46 39 52 50 45 60 41 43 80 54 37 72 49 51 96 66 68 65 128

Рис. 14. "Дерево степеней."

Метод множителя основан на разложении п. Если п = pq, где р представляет собой наименьший простой множитель п vl q > 1, ж" можно найти, вычислив и возведя эту величину в степень q. Если п - простое число, можно вычислить х~ и умножить его на х. И конечно, при п = 1 получаем х" безо всяких вычислений. Неоднократно применяя эти правила, можно получить процедуру вычисления ж" при любом данном значении п. Например, чтобы найти х, сначала нужно вычислить ?/ = д,4д, (а;22д, затем построить ?/ = уу = {у)у. Весь процесс предусматривает выполнение восьми умножений, в то время как двоичному методу потребовалось бы девять умножений. Метод множителя в среднем превосходит двоичный метод, но в некоторых случаях (наименьший из них - п = 33) двоичный метод лучше.

Двоичный метод может быть обобщен в т-арный метод следующим образом. Пусть п = dom + dim~ + + dt, где О < dj < т для О < j < t. Вычисление начинается с построения х, х, х, ..., х"~. (На самом деле нужны только те степени х, у которых dj появляются в представлении числа п, и это часто экономит наши усилия.) Затем возведем x° в степень т и умножим на х\ Таким образом мы вычислили 2/1 = 2;dom+di зтем возведем j/i в степень т, умножим на x и получим У2 = ж*"" +dim+d2 Этот процесс продолжается до тех пор, пока не будет вычислено значение yt = ж". Когда dj = О, естественно, умножение на х не является необходимым. Заметим, что данный метод при m = 2 сводится к обсуждавшемуся ранее двоичному методу "слева направо" однако менее ясный т-арный метод "справа налево" требует большего объема памяти и несколько большего количества шагов (см. упр. 9). Если т представляет собой малое простое число, т-арный метод будет особенно эффективен для вычисления степеней одного полинома по модулю другого, когда коэффициенты рассматриваются по модулю т в соответствии с 4.6.2-(5).

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

ния ж" найдите п в представленном на рисунке дереве; путь от корня дерева к п дает последовательность показателей степеней, встречающихся при эффективном вычислении х". Правило, по которому строится это "дерево степеней" приводится в упр. 5. Вычислительные тесты показали, что дерево степеней дает оптимальные результаты для всех указанных на рисунке п, однако для достаточно больших значений п метод дерева степеней не всегда оптимален (наименьшие примеры неоптимальности - п = 77, 154, 233). Первое значение, для которого дерево степеней превосходит и двоичный метод, и метод множителя, -тг = 23. Первое значение, для которого метод множителя превосходит метод дерева степеней, - п = 19879 - 103 • 193. Такие случаи весьма редки. (Для п < 100000 метод дерева степеней лучше метода множителя 88 803 раз, столь же хорош И 191 раз и проигрывает ему только 6 раз.)

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

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

1 = ао, ai, аг, = п, (1)

обладающих тем свойством, что

uj = Oj -ь Ok для некоторых к < j < i, (2)

для всех г = ], 2, ..., г. Это определение можно трактовать следующим образом. Рассмотрим простой компьютер с аккумулятором, который способен выполнять три операции: LDA, STA и ADD. Машина начинает работу с 1 в аккумуляторе и затем вычисляет число п, складывая полученные ранее результаты. Заметьте, что ai должно быть равно 2, а аг равно 2, 3 либо 4.

Наименьшая длина г, для которой существует аддитивная цепочка для п, обозначается как 1{п). Наша цель в оставшейся части этого раздела состоит в изучении функции 1{п). Значения 1(п) для малых п приведены в дереве на рис. 15, которое показывает, как вычислить х" с наименьшим возможным количеством умножений для всех п < 100.

Проблема определения 1{п) была, по-видимому, впервые поставлена в 1894 году X. Деллаком (Н. Dellac) и частично решена Э. деЖонкиэрес (Е. de Jonquieres) упомянутым методом множителя [см. LIntermediaire des Mathematiciens 1 (1894), 20, 162-164]. В своем решении де Жонкиэрес перечислил значения 1{р) для всех простых чисел р < 200, но в его таблице значения для р = 107, 149, 163, 179 были слишком велики.

Методом множителя можно получить неравенство

1{тп) < 1{т) + 1{п), (3)

поскольку можно взять цепочки 1, ai, ..., а = m и 1, 6i, ..., bg = п тл построить цепочку 1, ai, ..., Ог, afti, ..., abs = rim.

7 10

/ / \

14 И 20

/\ /\ /\

19 28 21 22 23 40

I /\ А I /\

38 29 56 31 42 44 46 41 80 39 54 45 60 50 51 96 35 52 43 68 37 72 49 66 65

15 24

/\ /\

27 30 25 48

А /\

/\ I /\ I I I /\

76 58 57 59 62 84 88 47 92 82 83 85 78 55 90 63 75 100 53 97 99 70 61 77 86 69 74 73 98 67 81

I I I I I I I I

89 94 93 95 79 91 71 87

Рис. 15. Дерево, минимизирующее число умножений для п < 100.

Можно также сформулировать т-арный метод в терминах аддитивных цепочек.

Рассмотрим случай, когда m = 2*, и запишем п = dom -l-dim~ -I-----hdf в m-ичной

системе счисления. Соответствующая аддитивная цепочка принимает вид

1,2,3,...,т - 2,т - 1,

2do) 4do! • • •) nido, mdo + di,

2{mdo+di),4{mdo+di), .,m{mdo + di),mdo + mdi + d,

m%+m-di+--- + dt. (4)

Ее длина равна m-2 + {k + l)t,H зачастую ее можно уменьшить, удалив некоторые элементы из первой строки (те, которые не встречаются среди коэффициентов dj, а также элементов из 2do, 4do, которые уже имеются в первой строке). Если какое-либо dj равно нулю, последний член в правой части соответствующей строки, конечно, может быть опущен. Кроме того, как обнаружил Э. Г. Тюрбер (Е. G. Thurber) [Duke Math. J. 40 (1973), 907-913], можно опустить все четные числа (за исключением 2) в первой строке, если привести значения вида dj/2 в вычислении е шагами ранее.

Простейший случай т-арного метода - двоичный (бинарный) метод (т = 2), когда общая схема (4) упрощается до правила "S и X" упоминавшегося в начале этого раздела: бинарная аддитивная цепочка для 2п представляет собой бинарную аддитивную цепочку для п с добавлением числа 2тг; для 2п+1 она является бинарной аддитивной цепочкой для 2п с последующим числом 2тг -Ь 1. Из бинарного метода можно заключить, что

1{2° + 2 +--- + 2)<eo + t, если ео > ej > • • • > е< > 0.