Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 32
Текст из файла (страница 32)
Ш. Вант (Р. Б. Жапб),) Если а„— старший коэффициент полинома н(х) и  — граница коэффициентов некоторого множителя и, то для алгоритма разложенкя, приведенного в тексте раздела, требуется найти разложение по модулю р'., где р' > 2[и [В. Но [и„[ мохсет быть больше, чем В, когда В выбирается по методу из упр.
21. Покажите, что если поливом и(х) приводим, то существует способ восстановления одного из его истинных множителей по разложению по модулю р', когда р' > 2В', с помощью алгоритма из упр. 4.5.3-51. 41. [М47[ (Визами (Веавхащу), Тревисан (Тгет1эап) и Ванг (%алб),) Докажите или опровергните следующее: существует константа с, гикая, что если 7(х) — некоторый целый полипом с коэффициентами, по абсолютному значению не превосходящими В, то один из его непрнводимых множителей имеет коэффициенты, ограниченные величиной сВ.
Ф.б.З, Вычисление степеней В этом разделе рассматривается интересная задача — эффективное вычисление х" и данным х и и, где и — положительное целое число. Предположим, например, что необходимо вычислить х'е Можно просто начать с х и 15 раз умножить его на х. Но тот же ответ можно получить всего за четыре умножения, если несколько раз возвести в квадрат получающийся результат, последовательно вычисляя хэ, х4, хэ г1е Эта же идея, в целом, применима к любому значению и слелуюшим образом. Запишем и в виде числа в двоичной системе счисления (убирая нули слева). Затем заменим каждую "1" парой символов БХ, каждый "0" — символом Б и вычеркнем крайнюю слева пару символов "БХ'" .Результат представляет собой правило вычисления х", в котором "Б" трактуется как операция возведения е квадрат, а "Х"' †к операция 1ьмнооюеннл иа х.
Например,п = 23 имеет 'двоичное представление 10111, Таким образом, мы формируем последовательность БХ Б БХ БХ БХ, нз которой удаляем начальную пару" БХ для получения окончательного правила ББХБХБХ. Это правило гласит, что необходимо "возвести в квадрат, возвести в квадрат, умножить на х, возвести в квадрат, умножить на х, возвести в квадрат и умножить на х", т.
е. последовательно вычислить значения хэ, х4, хэ, х'о, х", хээ, хэз Этот бинарный метод можно легко обосновать, проанализировав последовательность степеней при вычислении: рассматривая каждое "Б" как операцию умножения на 2, а "Х" — как операцию прибавления 1 и начав с 1, а не с х, мы придем к вычислению и в соответствии со свойствами двоичной системы счисления. Этот метод очень древний; он полнился до 200 г.
до н. э. в классической индусской Чанда- сутре (СЬапдаЬ-зйгга) Пингалы (Р)пба!а) [см. В. Пасса апд А. Н. Б1пбЬ, Н)эсогу оу Н!пдц МаГЬщпабсз 2 (Байоге: Моб!а1 Вапагэ) Раэ, 1935), 76], Похоже, что в течение следующего тысячелетия этот метод не упоминался нигде за пределами Индии. В 952 г.
н. э. аль-Уклндиси (а1-Пс~)16)в1) из Дамаска четко пояснил, как эффективно вычислить 2" для произвольного и. См. ТЬе АН1ЬшеПс ог" аИ7011д)зу Ьу А. Б. БаЫап (Погдгесйн П. НеЫе1, 1975), 341-342, где общие идеи проиллюстрированы на примере и = 51. См. также работу аль-Бируни (а1-В1гйш) СЬгопо1ойу оГАпс!епг ЬТаг1опз, переведенную и отредактированную Э. Саше (Е. Басйац) (1опдоп, 1879), 132-136. Эта арабская работа 11 века оказала сильное влияние на развитие математики. Рис.
13. Вычисление х", освовакное на сканировании лвончной записи в справа налево. Бинарный метод зй и Хв для получения х" не требует дополнительной памяти, за исключением памяти для хранения х и текущего промежуточного результата, а потому он удобен для аппаратной реализации на бинарном компьютере. Метод легко программируем, однако требует сканирования двоичного представления числа п слева направо, в то время как компьютерные программы обычно делают зто в обратном направлении, в связи с тем, что доступные операции деления на 2 и взятия остатка по модулю 2 выводят двоичное представление чншш справа налево. Поэтому зачастую более удобным оклзывается следующий алгоритм, основанный на сканирования числа справа налево.
Алгоритм А (Бинарный метод возведения в степень справа налево). Этот алгоритм (рнс. 13) вычисляет значение х", где и — положительное целое число (здесь х принадлежит любой алгебраической системе, в которой определено ассоциативное умножение с единичным элементом 1). А1. (Инициализация.1 Установить Ю +- п, У +- 1, Я <- х. А2. (Деление Х пополам.) (В этот момент х" = 1'Я~.) Установить Х <- (А~2) н одновременно определить, было ли Ю четно, Если Х было четно, перейти к шагу А5. АЗ, (Умножение 1 на я.) Установить 1 ~- л, умноженное на 1.
А4. (Х = О?) Если Х = О, то выполнение алгоритма прекращается с У в качестве резульшта, Аб. (Возведение о в квадрат.) Установить Я вЂ” Я, умноженное на Я, и вернуться к шагу А2. В качестве примера применения алгоритма А рассиотрни пошаговое вычисление хзз. Х У Я После шага А1 23 1 х После шага А5 11 х хз После шага А5 5 хз х~ После шага Аб 2 х' хз После шага А5 1 х' х'о После шаха А4 О хзз х'о Соответствующая алгоритму А И1Х-программа приведена в упр. 2.
Великий вычислитель аль-Каши (а1-КйэЬ1) сформулировал алгоритм А в 1427году [Историко-математические исследования 7 (1954), 256-257). Этот алгоритм тесно связав с процедурой умножения, в действительности использовавшейся египетскими математиками за 2000 лет до н. э. Если заменить шаг АЗ на "1' е- 1'+ Я", а шаг А5 на "Я ~- л + Я" и если установить 1' равным нулю, а не единице на шаге А1, то в результате работы алгоритма получится У = пх. [См.
А. В. СЬасе, ТЬе ВЬшд МагЬетайса1 Раругие (1927); Ч'. 1з'. Зггпзе, ЯиеПеп ипс( БгшЬеп гпг СеесЬ1сЬге Нег Ма1Ьетагй А1 (1930).] Это практичный метод умножения чисел вручную, поскольку используются только простые операции удвоения, деления пополам и сложения. Часто его называют русским крестьянским методом умножения, так как Запад стал свидетелем его популярности в России в 19 веке.
Количество умножений, требуемых алгоритмом А, составляет [16п1 + и(п), где и(п) равно количеству единиц в двоичном представлении числа и. Это на одно умножение больше, чем при бинарном методе "слева направо", о котором упоминалось в самом начале данного раздела, так как при первом выполнении шага АЗ просто производится умножение на единицу. Из-за дополнительного времени на накладные расходы этого алгоритма метод не так хорош для малых значений и, скажем, для и < 10, если, конечно, время, необходимое для умножения, сравнительно невелико.
Если значение и известно заранее, то предпочтителен двоичный метод "слева направо'.* Иногда, например прн вычислении х" шод и(х), которое обсуждалось в разделе 4.6.2, гораздо проще умножать на х, чем выполнять обобщенное умножение или возведение в квадрат, так что двоичные методы для возведения в степень в таких случаях, в первую очередь, подходят для очень больших значений и.
Для вычисления точного значения х" с многократной точностью при целом х, большем,чем размер компьютерного слова, бинарные методы не слишком хороши до тех пор, пока я не станет столь огромным, что высокоскоростное умножение (см. раздел 4.3.3) будет неприменимо. Однако такие приложения очень редки. Точно так же двоичный метод мало пригоден для возведения в степень полиномов [см. в В.
3. Расешап, 5!СОМР 3 (1974), 196-213, обзор публикаций по проблеме возведения полииомов в степень). Главная идея этого примечания состоит в том, что двоичные методы хороши„но не являются панацеей. Онн применимы в основном тогда, когда время умножения х' х~ по сути, не зависит от 1 и й (напрнмер, когда выполняется умножение с плавающей точкой или умножение по модулю т); в таких случаях порядок времени работы уменыпается с и до 1ой и. Уменьшение количества операций умножения.
Несколько авторов без доказательства опубликовали утверждение о том, что двоичный метод дает минимально возможное число умножений. Однако зто утверждение неверно, и простейший контрпрнмер — и = 15, при котором двоичный метод требует шести умножений, в то время как у = хз можно вычислить с помощью двух умножений н х'~ = у — с помощью еще трех, т.
е, получить требуемый результат, выполнив всего пять умножений. Обсудим теперь несколько других процедур для вычисления х", в предположении, что и известно заранее. Такие процедуры особенно интересны, например, при генернровании машинного кода оптимизирующим компилятором. 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. "Дерево степеней." ~/'~ ! /~ /~ ! й /!~ ! ! й ! й / ! /~ !, й,! !~ ! /~ /!~ ! ! /~ эгешод множишелл основан на разложении и. Если п = ре, где р представляет собой наименьший простой множитель и и 0 > 1, х" можно найти, вычислив хэ и возведя эту величину в степень 0.
Если и — простое число, можно вычислить х" ' и умножить его на х. И конечно, прн и = 1 получаем х" безо всяких вычислений. Неоднократно применяя эти правила, можно получить процедуру вычисления х" прн любом данном значении и. Например, чтобы найти хее сначала нужно вычислить у = хе = хех = (хз)эх а затем построить у" = у'еу = (уз)ву. Весь процесс предусматривает выполнение восьми умножений, в то время как двоичному методу потребовалось бы девять умножений. Метод множителя в среднем превосходит двоичный метод, но в некоторых случаях (наименьший нз них — п = 33) двоичный метод лучше.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
