Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 33
Текст из файла (страница 33)
Двоичный метод может быть обобщен в ш-арнмй мешод следующим образом. Пусть и = дот~ + д1т1 1+ - ° ° + 4, где О < И < т для О < у < а Вычисление начинаетгя с построения х, хз, хз, ..., х '. (На самом деле нужны только те степени х4, у которых ду появляются в представлении числа п, и зто часто экономит ваши усилия.) Затем возведем хее в степень ш и умножим на хег Таким образом мы вычислили у~ = хе' +е'. Затем возведем у, в степень ш, умножнм на хе' и получим а 4 +8 уз = х е ее' +е'.
Этот процесс продолжается до тех пор, пока не будет вычислено значение у~ —— х". Когда г(1 = О, естественно, умножение на хез не является необходимым. Заметим, что данный метод при и = 2 сводится к обсуждавшемуся ранее двоичному методу "слева направо", однако менее ясный ш-арный метод "справа налево'* требует большего объема памяти и несколько большего количества шагов (см. упр.
Р). Если т представляет собой малое простое число, ш-арный метод будет особенно эффективен для вычисления степеней одного полинома по модулю другого, когда коэффициенты рассматриваются по модулю гп в соответствии с 4.Б.2-(б). Систематический метод, дающий минимальное количество умножений для всех относительно мальм значений и (в частности, для большинства встречающихся в реальных приложениях значений и), проиллюстрирован на рис, 14. Для вычисле- ния х" найдите и в представленном на рисунке дереве; путь от корня дерева к и лает последовательность показателей степеней, встречающихся при эффективном вычислении х".
Правило, по которому строится это "дерево степеней", приводится в упр. 5. Вычислительные тесты показали, что дерево степеней дает оптимальные результаты для всех указанных на рисунке и, однако для достаточно больших значений и метод дерева степеней не всегда оптимален (наименьшие примеры неоптимальности— и = 77, 164, 233), Первое значение, для которого дерево степеней превосходит и двоичный метод, и метод множителя, — п = 23. Первое значение, для которого метод множителя превосходит метод дерева степеней, — и = 19879 = 103 193. Такие случаи весьма редки. (Для и < 100000 метод дерева степеней лучше метода множителя 88 803 раз, столь же хорош 11 191 раз и проигрывает ему только 6 раз.) Аддитивные цепочки.
Наиболее экономичный путь вычисления х" с помощью операций умножения представляет собой математическую задачу с интересной историей. Сейчас мы приступим к ее изучению не только потому, что она классическая и интересна сама по себе, но и потому, что это превосходный пример теоретических вопросов, .возникающих при изучении оптимальных методов вычислений.
Хотя мы имеем дело с умножением степеней з, проблему можно легко свести к сложению, поскольку при умножении показатели степеней складываются. Это приводит к следующей абстрактной формулировке: аддигливной цепочкой длл и является последовательность целых чисел 1 = ае, ам аз, ..., а„ = и, (1) обладающих тем свойством, что а; = ау+ аь для некоторых А <у < 1, (2) для всех 1 = 1. 2, ..., г.
Это определение можно трактовать следующим образом. Рассмотрим простой компьютер с аккумулятором, который способен выполнять три операции: !.0А, БТА и АЮР. Машина начинает работу с 1 в аккумуляторе н затем вычисляет число п„складывая полученные ранее результаты. Заметьте, что а~ должно быть равно 2, а аз равно 2, 3 либо 4. Наименыпая длина г, для которой существует алдитнвная цепочка для п, обозначается как 1(п). Наша цель в оставшейся части этого раздела состоит в изучении функции 1(п). Значения Цп) для малых и приведены в дереве на рис.
13, которое показывает, как вычислить х" с наименьшим возможным количеством умножений для всех и < 100. Проблема определения 1(п) была, по-видимому, впервые поставлена в 1894 го. ду Х. Деллаком (Н. Пе!!ас) и частично решена Э. деЖонкиэрес (Е. дедопйц!Ьгеэ) упомянутым методом множителя [см. Г1пгегтеглшге с(ез Ма!йети!с(епэ 1 (1894), 20.
162-164). В своем решении де Жонкиэрес перечислил значения !(р) для всех простых чисел р < 200, но в его таблице значения для р = 107, 149, 163, 179 были слишком велики. Методом множителя можно получить неравенство (3) !(пгп) < 1(т) + !(и), поскольку можно взять цепочки 1, ам ..., а, = гп и 1, Ьм ..., Ь, = и и построить цепочку 1, а„..., а„а„Ь„..., а„Ь, = пш, l~ й /~ /~ /~ ! ! ! Л 19 28 2! 22 23 40 27 30 25 48 26 34 36 33 64 !Й Й! ! Й 1"17"1 ! /~ й /~ й й ! 3829 56 314244 46 41 80 395445 60 50 51 96 35 52 43 68 37 72 49 66 65 ! ! 7"1 ! ! ! 7"1 ! Й ! ! ! 7"1 ! ! й ! ! й ! ! ! ! ! ! 765857596284884792828385785590637510053 97 99 70 61 77 86 69 74 73 98 67 81 )!! !! ! ! 899493 95 79 91 Рис.
15, Дерево, минимизирующее число умножения для и < 100, Можно также сформулировать т-ариый метод в терминах аддитивных цепочек. Рассмотрим случай, когда т = 2", и запишем и = а)от'+ Н1 гпа 1+ "+ 4(1 в гп-ичной системе счисления, Соответствующая ацдитивная цепочка принимает вид 1,2,3„...,т — 2,7п — 1, 2а)о > 440,..., ШНО, 034(о + Ы1, 2(тйо+41),4(пм(0+4(1),...,гп(тдо+ И1),гп 4(о + тА + 42 т'е)о + п11 1А1 + ° ° + а(4. (4) Ее длина равна ш — 2+ (1+ 1)3, и зачастую ее можно уменыпить, удалив некоторые элементы из первой строки (те, которые не встречаются среди коэффициентов 4173 а также элементов из 200, 440, ..., которые уже имеются в первой строке).
Если какое-либо 42 равно нулю, последний член в правой части соответствующей строки, конечно, может быть опущен, Кроме того, квк обнаружил Э. Г, Тюрбер (Е. Са. ТЪпгЪег) (1)пке Магй. Х 40 (1973), 907-913), можно опустить все четные числа (за исключением 2) в первой строке, если привести значения вида 4117'2' в вычислении е шагами ранее.
Простейший случай т-арного метода — двоичный (бинарпый) метод (гп = 2), когда общая схема (4) упрощается до правила аЯ н Х*', упоминавшегося в начале этого раздела: бинарная аддитивная цепочка для 2п представляет собой бинарную аддитивную цепочку для и с добавлением числа 2п; для 2п+1 она является бинарной аддитивной цепочкой для 2п с последующим числом 2п + 1.
Из бинарного метода можно заключить, что 1(2аа + 2аа + . + 2а~) а' е + 7 если ео ~ 61 ) „., ) 61 ) 0 (3) Определим теперь две вспомогательные функции для удобства последующего обсу- ждения: Л(п) = ~18п); и(п) = количество единиц в двоичном представлении и. (б) (7) Таким образом, Л(17) = 4, и(17) = 2. Эти функции могут быть определены следую- щими рекуррентнымн соотношениями: (8) (9) Л(2п) = Л(2п+ 1) = Л(п) + 1; и(2п) = и(п), и(2п + 1) = и(п) + 1.
Л(1) = О, и(1) = 1, С их помощью можно записать, что бинарные аддитивные цепочки для и требуют ровно Л(п) + и(п) — 1 шагов, а (б) принимает вил 1(п) < Л(п) + и(п) — 1. Специальные классы цепочек. Не теряя обпшости, можно положить, что эд- днтивные цепочки возрастающие, т. е. 1=ае<аг <аз« .а,.=п.
Если два числа из а одинаковы, то одно из ннх может быть опущено. Можно также переупорядочить последовательность (1) в порядке возрастания и удалить члены, ббльшие, чем и, не нарушая свойство аддитивной цепочки (2). В дальнейшем будем рассматривать только возраститцне цепочки, не оговаривая это соглашение явно. Теперь удобно определить несколько специальных терминов, относящихся к аддитивным цепочкам. По определению для 1 < ( < г (12) для некоторых у и А, О < А < у < А Если это соотношение выполняется для более чем одной пары (у, А), полагаем, что у — наибольшее из возможных.
Будем говорить, что шаг 1 цепочки (11) — удвоение, если у = А = 1 — 1. Тогда а; имеет максимально возможное значение 2а; и которое может следовать за возрастающей цепочкой 1, аы ..., а; м Если у (но не обязательно А) равно 1 — 1, будем говорить, что шаг 1— звездный шаг (э$аг эсер). Важность звездньгх шагов поясняется ниже. И наконец, будем говорить, что шаг 1 представляет собой малый шаг, если Л(а~) = Л(а~ 1). Поскольку а~ 1 < а; < 2а~ „величина Л(а~) всегда равна либо Л(а; г), либо Л(а; 1) + 1; отсюда следует, что длина г любой цепочки (11) равна Л(п) плюс количество малых шагов. Эти типы шагов удовлетворяют ряду элементарных соотношений.
Шаг 1 всегда представляет собой удвоение. Ясно, что удвоение — звездный шаг, ио никогда не малый шаг. За удвоением всегда следует звездный шаг. Кроме того, если шаг 1 не малый, то шаг 1+ 1 является либо малым, либо звездным, либо н тем, и другим одновременно. Рассматривая данное утверждение с другой стороны, получим, что если шаг 1+ 1 не является нн малым, нн звездным, то шаг 1 должен быть малым. Звездной цепочкой (эсаг сйаеэ) является аддитнвная цепочка, включающая только звездные шаги. Это означает, что каждый член а; представляет собой сумму а; 1 и предшествующего ему аы простой "компьютер", упоминавшийся ранее, после (2), в звездной цепочке использует только две операции, ЗТА и АРО (беэ ЬРА), поскольку каждый новый член последовательности использует предыдущий резуль- тат, находящийся в аккумуляторе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
