AOP_Tom2 (1021737), страница 128
Текст из файла (страница 128)
— Лрньс нерее. Алгебраическая система 5 обычно представляет собой множество целых или рациональных чисел. Она может быть и множеством полиномов (с другими, отличными от х переменными); тогда (1) — полипом от нескольких переменных. В частности, алгебраическая система 5 может состоять нз целых чисел О, 1, ..., т — 1 со сложением, вычитанием и умножением, выполняемыми по модулю гп (см, формулу 4.3.2 — (11)); этот важный случай называется полиномиальной арифметикой по модулю т. Особенно важна полиномиальная арифметика по модулю 2, когда каждый коэффициент равен 0 или 1. Читатель должен обратить внимание на сходство между полиномиальной арифметикой и арифметикой многократной точности (раздел 4.3.1), где основание счисления 6 заменено на х.
Основное отличие состоит в том, что коэффициент пь при я ,л в полиномиальной арифметике, вообще говоря, никак не связан с соседними коэффициентами иььы так что понятие "перенос" из одного места в другое в полиномиальной арифметике отсутствует. В действительности полиномиальная арифметика по модулю 6, по существу, идентична арифметике с многократной точностью по основанию 6 за исключением отсутствия переносов. Например, сравним умножение (1101)г на (1011)з в двоичной системе счисления с аналогичным умножением хз + яз + 1 на хз + х + 1 по модулю 2. Двоичные числа 1101 х 1011 Полиномы по модулю 2 1101 х 1011 1101 1101 1101 1101 1101 1101 10001111 1111111 Произведение этих полиномов по модулю 2 получено путем отказа от всех переносов и составляет хе+ ха + я4+ ха + хз + х + 1. Если умножать полиномы так же, как целые числа, без получения остатков по модулю 2, результат будет равен те + х + х + Зх' + яз + з + 1; переносы в данном случае также не используются, однако коэффициенты в произведении могут оказаться произвольно большими.
В связи с сильным сходством полиномнальной арифметики и арифметики с многократной точностью нет необходимости подробно обсуждать операции сложения, вычитания и умножения в этом разделе. Однако нужно отметить некоторые аспекты, отличающие практическое использование полиномиальной арифметики от арифметики многократной точности. Очень часто при работе с полиномами наблюдается тенденция к появлению большого количества нулевых коэффициентов и полиномов огромных степеней, а потому желательно использовать специальные формы представления полиномов (см, раздел 2.2.4). Кроме того, арифметика полиномов от нескольких переменных приводит к программам, которые легче всего понять в рамках рекурсии (эта ситуация будет обсуждаться в главе 8).
Хотя методы сложения, вычитания и умножения полиномов сравнительно просты и понятны, несколько важных аспектов полиномиальной арифметики достойны специального рассмотрения. В следующих разделах будут обсуждаться деление полиномов и связанные с ним методы, такие как поиск нанболыпего общего делителя и разложение на множители. Мы рассмотрим также проблему эффективного вычисления полиномов, т. е. задачу поиска значения и(х) при данном х Е о с использованием минимально возможного чигпа операций.
Частный случай вычисления х при болыпих и достаточно важен и разбирается отдельно в разделе 4.6.3. Первым большим набором компьютерных подпрограмм для работы с полиномиальной арифметикой стала система АЬРАК [%. 8. Вгокп, 1. Р. Нуч(е, апг( В. А. Тайне, Ве!! Яуэгет ТссЬ. Х 42 (1963), 2081 — 2119; 43 (1964), 785 — 804, 1547 — 1562), Другой ранней вехой в этой области стала Р34 эуэсегп Джорджа Коллинза (Оеогбе Со11шэ) [САСМ 9 (1966), 578 — 589; см. также С.
Ь. НатЫт, Сотр. Х 10 (1967), 168-171). УПРАЖНЕНИЯ 1. [!О) При работе с полиномивльной арифметикой по модулю 10 чему будет равна разность 7х+ 2 н х~ + 5? Чему будет равно произведение бх~ + х + 3 и 5тэ + 2? 2. [!7) Истинны ли следующие утверждения? (в) Произведение нормированных полиномов нормировано.
(Ь) Произведение полиномов степени т и и имеет степень т+ и. (с) Сумма полиномов степени гп и и имеет степень шах(ш, и). 3. [МЯО) Если каждый из коэффициентов и„..., ио, и„..., оо в (4) представляет собой целое число, удовлетворяющее ушювиям )и,[ < тп [е,[ < тэ, то чему равно максимальное абсолютное значение произведения коэффициентов юь? 4. [2![ Можно ли умножение полиномов по модулю 2 упростить с помощью обычных арифметических операций на двоичном компьютере, если коэффициенты упакованы в машинные слова? 5. [Мй!] Покажите, как можно умножить два полинома степени < и по модулю 2 со временем умножения, пропориионвльным 0(п'к ) прн больших и, адаптируя метод Карапубы (см. раздел 4.3.3). 4.6.1. Деление пплинпмов Разделить один полипом на другой можно так же, как одно целое число с многократной точностью на другое, при выполнении арифметических операций с полиномами над полем.
Поле Я представляет собой коммутативное кольцо с единицей, в котором точное деление возможно так же, как и операции сложения, вычитания и у'множения, Как обычно, это означает, что для любых и, о Е В и о ~ 0 в Я всегда имеется элемент ш, такой, что и = пих Наиболее важными полями коэффициентов, появляющимися в приложениях, являются а) рациональные числа (представленные в виде дробей; см. раздел 4.5.1); Ь) действительные или комплексные числа (представленные в компьютере как приближения с плавающей точкой; см. раздел 4.2); с) целые по модулю р, где р — простое число (деление может быть реализовано так, так предложено в упр. 4.5.2-16); Й) рациональнь~е функции над полем, т.
е. частное двух полиномов, коэффициенты которых находятся в этом поле, а знаменатель нормирован. Особо важный случай представляет собой поле целых по модулю 2, в котором элементы могут принимать значения О и 1. Полиномы над этим полем (т. е. полиномы по модулю 2) имеют много общего с целыми числами в двоичной записи; рациональные функции над данным полем поразительно схожи с рациональными числами, числители и знаменатели которых представлены в двоичной записи. Если даны два полинома, и(х) и в(х), над полем и в(х) ф О, можно разделить и(х) на в(х) и получить полипом-частное д(х) и полипом-остаток г(х), удовлетворяющие условиям и(х) = д(х) .
в(х) + г(х), с$ея(г) ( 4еб(в). Легко увидеть, что существует не более одной пары полиномов (д(х), г(х)), удовлетворяющих этим соотношениям; в самом деле, если условиям (1) при одних и тех же полиномах и(х) и в(х) удовлетворяют две пары — (дг(х),г,(х)) и (дг(х), гг(х)),— то д1(х) и(х) + г,(х) = дг(х) и(х) + гг(х), т. е. (дг(х) — дг(х)) в(х) = гг(х) — гг(х). Теперь если дг(х) — дг(х) ф О, имеем с1еб((дг — дг) и) = бей(дг — дг) + Йеб(в) > деб(и) > Йеб(гг — г,), т. е.
получаем противоречие (так как из равенства (дг(х) — дг(х)) в(х) = гг(х) — гг(х) следует пей((дг — дг) в) = бей(гг — гг) — Прим. перев.). Значит, дг(х) — дг(х) = О и гг(х) = гг(х). Чтобы определить д(х) и г(х), можно использовать алгоритм 4.3.1Р для деления чисел с многократной точностью, только без переносов. Алгоритм Р (Деление пвлиномов иад полем). Даны полиномы и(х) = и„х" + + игх + са и(х) — имх + ' ' ' + игх + 2Ю, нвд полем Я, где и„ф О и т > и > О.
Алгоритм находит полиномы г(х) = г„гх" + + га д(х) =де „х "+ +да, нэд полем Я, удовлетворяющие условиям (1). Р1. [Итерация по Е) Выполнять шаг Р2 для й = т — и, т — п — 1, ..., О; затем прекратить выполнение алгоритма с (г„ы, го) = (ив-ы, иа). Р2. (Цикл деления.) Установить сначала дь +- и„.ьь/в„, а затем — иу +- и, — давг — ь для г = и + й — 1, п + й — 2, ..., /с. (Действие последней операции состоит в замещении и(х) на и(х) — дьхьи(х), полипом степени < и+ Й.) ! Пример использования алгоритма Р приводится ниже, в (5).
Количество выполняемых арифметических операций, в сущности, пропорционально п(т — и + 1). Обратите внимание, что явное деление коэффициентов выполняется только в начале шага Р2 и знаменателем всегда является в„. Таким образом, если и(х)— нормированный полинам (с в„= 1), реальное деление не производится вовсе. Если умножение более предпочтительно, чем деление, имеет смысл предварительно вычислить значение 1/в„и на шаге Р2 выполнить умножение на эту величину. Зачастую остаток г(х) из (1) будет записываться как и(х) шод и(х). Области единственного разложения на множители. Если мы ограничимся рассмотрением полииомов над полем, то не охватим полиномы над множеством целых чисел и полиномы от нескольких переменных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
