AOP_Tom2 (1021737), страница 141
Текст из файла (страница 141)
Саша (Е. ЯасЬап) (Еопйоп, 1879), 132-136, Эта арабская работа 11 века оказала сильное влияние на развитие математики. Рис. 13. Вычисление х", основанное нв сканировании двоичной записи и справа налево. Бинарный метод нВ и Х" для получения х" не требует дополнительной памяти, за исключением памяти для хранения х и текущего промежуточного результата, а потому он удобен для аппаратной реализации на бинарном компьютере. Метод легко программируем, однако требует сканирования двоичного представления числа п слева направо, в то время как компьютерные программы обычно делают это в обратном направления, в связи с тем, что доступные операции деления на 2 и взятия остатка па модулю 2 выводят двоичное представление числа справа налево.
Поэтому зачастую более удобным оказывается следующий алгоритм, основанный на сканировании числа справа налево, г 1 х х хт хз х4 х7 хе хт х'в 23 16 приведена в упр. 2. Л Паоле шага А1 23 После шага А5 11 После шага А5 5 После шага А5 2 После шага А5 1 После шага А4 О Соответствующая алгоритму А М11-программа Алгоритм А [Бинорныа метод возведения в сепепень справа налево).
Этот алгоритм (рис. 13) вычисляет значение х", где и — положительное целое число [здесь х принадлежит любой алгебраической системе, в которой определено ассоциативное умножение с единичным элементом 1). А1. [Инициализация.[ Установить Х +- и, 1' т — 1, Я < — х. А2. [Леление Х пополам.[ (В этот момент х" = У 7~.) Установить У +- [Х/2) и одновременно определить, было ли Х четно.
Если Л~ было четно„перейти к шагу А5. А.З. [Умножение 1' на Т[ Установить 1' < — Я, умноженное на 1'. А4. [Х = О?[ Если Х = О, то выполнение алгоритма прекращается с 1' в качестве результата. А5. [Возведение Л в квадрат.[ Установить Я < — 2, умноженное на Я, и вернуться к шагу А2. 1 В качестве примера применения алгоритма А рассмотрим пошаговое вычисление хт'. Великий вычислитель аль-Каши (а1-Кав1п) сформулировал алгоритм А в 1427году [Исторвко-мвтематвческпе исследования 7 (1954), 256 — 257[. Этот алгоритм тесно связан с процедурой умножения, в действительности использовавшейся египетскими математиками за 2000 лет до н, э, Если заменить шаг АЗ на "У < — У + 3", а шаг Ао на "Я +- Я + Е" и если установить 1' равным нулю, а не единице на шаге А1, то в результате работы алгоритма получится 1' = пх.
[См. А. В. СЛасе, ТЛе 11Лшс( МаГЛетайса! Раругиз (1927); 1У. %. БГгпне, чие11еп ип6 Юийеп виг СевсЛ1сйзе с(ег МаГЛешагй А1 (1930).) Это практичный метод умножения чисел вручную, поскольку используются только простые операции удвоения, деления пополам и сложения. Часто его называют русским крестьянским методом умножения, так как Запад стал свидетелем его популярности в России в 19 веке. Количество умножений, требуемых алгоритмом А, составляет [13п) + и(п), где и(п) равно количеству единиц в двоичном представлении числа и. Это на одно умножение больше, чем при бинарном методе "слева направо", о котором упоминалось в самом начале давнога раздела, так как при первом выполнении шага АЗ просто производится умножение на единипу.
Из-за дополнительного времени на накладные расходы этого алгоритма метод не так хорош для малых значений и., скажем, для п ( 10, если, конечно, время, необходимое для умножения, сравнительно невелико. Если значение и известно заранее, то предпочтителен двоичный метод "слева направо".
Иногда, например при вычислении х" шоб и(в), которое обсуждалось в разделе 4.6.2, гораздо проще умножать на к, чем выполнять обобщенное умножение или возведение в квадрат, так что двоичные методы для возведения в степень в таких случаях, в первую очередь, подходят для очень болыпвх значений п. Для вычисления точного значения хч с многократной точностью при целом х, .болыпем, чем размер компьютерного слова, бинарные методы не слишком хороши до тех пор, пока и не станет столь огромным, что высокоскоростное умножение (см. раздел 4.3.3) будет неприменимо. Однако такие приложения очень редки. Точно так же двоичный метод мало пригоден для возведения в степень полиномов [см.
в В.. 3. Ра1ешап, ЯСОМР 3 (1974), 196-213, обзор публикаций по проблеме возведения полиномов в степень[. Главная идея этого примечания состоит в том, что двоичные методы хороши, но не являютси панацеей. Они применимы в основною тогда, когда время умножения яз х", по сути, ве зависит от ( и й (например, когда выполняется умножение с плавающей точкой или умножение по модулю гп); в таких случаях порядок времени работы уменьшается с п до!охп. 'Уменьшение количества операций умножения.
Несколько авторов без доказательства опубликовали утверждение о том, что двоичный метод дает минимально возможное число умножений. Однако это утверждение неверно, и простейший ковтрпример — п = 15, при котором двоичный метод требует шести умножений, в то время как у = гз можно вычислить с помощью двух умножений и гы = уа — с помощью еше трех, т. е. получить требуемый результат, выполнив всего пять умножений.
Обсудим теперь несколько других процедур для вычисления в", в предположении, что и известно заранее, Такие процедуры особенно интересны, например, при генерировании машинного кода оптимизирующим компилятором. /~ /~ ! й /1~ ! ! й ! й / ! /~ !~ ! й / ! й ! 8 ЗЗ 34 64 !!й Мешод мнолспшелл основан на разложении и. Если п = рб, где р представляет собой наименьший простой множитель и и 9 > 1, х" можно найти, вычислив хг и возведя эту величину в степень д. Если п — простое число, можно вычислить х" ' и умножить его на х.
И конечно, при и = 1 получаем х" безо всяких вычислений. Неоднократно применяя эти правила, можно получить процедуру вычисления х" при любом данном значении и. Например, чтобы найти х55 сначала нужно вычислить р = х5 = х4х = (хз)эх, а затем построить рм = 9'еу = (92)59. Весь процесс предусматривает выполнение восьми умножений, в то время как двоичному методу потребовалось бы девять умножений. Метод множителя в среднем превосходит двоичный метод, но в некоторых случаях (наименьший из них — п = 33) двоичный метод лучше.
Двоичный метод может быть обобщен в гп-арнмп 44ЕШОд следующим образом. Пусть п = пбгп'+ А го' ' + . + 4, где О < ф < гп для О < 7' < й Вычисление начинается с построения х, хэ, хэ,, х"' '. (На самом деле нужны только те степени х"~, у которых Нб появляются в представлении числа п, и это часто экономит наши усилия.) Затем возведем х~' в степень гп и умножим на х"! Таким образом мы вычислили 1п — — хз'"'+4'. Затем возведем у4 в степень т, умножим на хз' н получим уе — — Хз''и +4'и'~ 4'.
Этат ПрОцЕСС ПрсдОЛжаЕтея дО тЕХ ПОр, ПОКа НЕ будЕт ВЫЧИСЛЕНО значение 94 = х". Когда 41 = О, естественно, умножение на х44 не является необходимым. Заметим, что данный метод при гп = 2 сводится к обсуждавшемуся ранее двоичному методу "слева направо", однако менее ясный гп-арный метод "справа налево" требует большего объема памяти и несколько большего количества шагов (см. упр. 9). Если т представляет собой малое простое число, т-арный метод будет особенно эффективен для вычисления степеней одного полинома по модулю друтого, когда коэффициенты рассматриваются по модулю гп в соответствии с 4.б.2-(5).
Систематический метод, дающий минимальное количество умножений для всех относительна малых значений и (в частности, для большинства встречающихся в реальных приложениях значений и), проиллюстрирован на рис. 14. Для вычисле- 38 35 42 29 31 56 44 46 39 52 50 45 60 41 43 80 54 37 72 49 51 98 бб 68 65 128 Рнс. 14. "Дерево степеней." ння х" найдите и в представленном на рисунке дереве; путь от корня дерева к п дает последовательность показателей степеней, встречающихся при эффективном вычислении х". Правило, по которому строится это "дерево степеней", приводится в упр.
5. Вычислительные тесты показали, что дерево степеней дает оптимальные результаты для всех указанных на рисунке п, однако для достаточно больших значений п метод дерева степеней не всегда оптимален (наименьшие примеры неоптимальности— и = 77, 154, 233). Первое значение, для которого дерево степеней превосходит и двоичный метод, и метод. множителя, — и = 23. Первое значение, для которого метод множителя превосходит метод дерева степеней, — и = 19879 = 103 193. Такие случаи весьма редки. (Для и < 100000 метод дерева степеней лучше метода множителя 88 803 раз, столь же хорош 11191 раз и проигрывает ему только 6 раз.) Аддитивные цепочки. Наиболее экономичный путь вычисления х" с помощью операций умножения представляет собой математическую задачу с интересной историей. Сейчас мы приступим к ее изучению не только потому, что она классическая и интересна сама по себе, но и потому, что это превосходный пример теоретических вопросов, возникающих прн изучении оптимальных методов вычислений.
Хотя мы имеем дело с умножением степеней х, проблему можно легко свести к сложению, поскольку при умножении показатели степеней складываются. Это приводит к следующей абстрактной формулировке: аддитпиеной цепочкой для п является последовательность целых чисел 1=ае, ат, атн ..., а„=п, обладаюптнх тем свойством, что а, = а. + аь для некоторых /с < 1 < т, (2) для всех 1 = 1, 2, ..., г. Это определение можно трактовать следующим образом.
Рассмотрим простой компьютер с аккумулятором, который способен выполнять три операции: РРА, БТА и АРР. Машина начинает работу с 1 в аккумуляторе я затем вычисляет число и, складывая полученные ранее результаты. Заметьте, что ат должно быть равно 2, а аз равно 2, 3 либо 4. Наименьшая длина г, для которой существует алднтивная цепочка для п, обозначается как !(и). Наша цель в оставшейся части этого раздела состоит в изучении функции !(и). Значения !(и) для малых и приведены в дереве на рис. 15, которое показывает, как вычислить х" с наименьшим возможным количеством умножений для всех и < 100. Проблема определения ((и) была, по-внднмому, впервые поставлена в 1894 году Х. Деллаком (Н.
Пе!!ас) и частично решена Э. деЖонкиэрес (Е. ВеЗопт!ц!егеа) упомянутым методом множителя (см. Ып!егтетз!а!те т!еа Ма!Леша!!с1епэ 1 (1894), 20, 162-164!. В своем решении де Жонкиэрес перечислил значения !(р) для всех простых чисел р < 200, но в его таблице значения для р = 107, 149, 163, 179 были слишком велики. Методам множителя можно получить неравенство (3) !(тпп) < !(тп) + ((и), поскольку можно взять цепочки 1, ат, ..., а„= ттт и 1, Ьт, ..., Ь, = п, н построить цепочку 1, ат,..., а„, а,Ь,,..., а, Ь„= ти.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
