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