1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 64
Текст из файла (страница 64)
!/(х) — ОБРАТНЫЙ ~ ~ айх' йУЕ 1=Цй /й-! 3. г(х) — 2!/(х) х!а!е1й-й — (!/ (х))'~ ~~", а,х' 1=Е ге1цгп ~г(х)/х" ' ( ецио Рнс. 2.2. Процедура для обращения аолнноиов. 321 11 А. Аао. Дж. Ховнржйй, Дж. Уаован гл. в. лгиемвтическиа опяглции му для вычисления 1/а, нет необходимости вызывать процедуру ОБРАТНОЕ. Сам алгоритм состоит в вызове процедуры ОБРАТНЫЙ с аргументом р(х). П Пример 8.3. Вычислим ~к"/р(х) (, где р(х)=х' — х'+х'+2к'— — хв — Зх'+х+4.
В строке 2 обращаем полипом х' — х'+х+2, т. е. находим д(х)= ! хЧ(к' — х'+х+2) ~. Проверьте, что о(х)=х'+х' — 3. Поскольку я=б, строка 3 вычисляет г(к)=2о(к) х" — (о(к))' р(х)= =х" +х" — Зх" — 4к'+Зх" +! 5х'+12к' — 42х' — 34х'+ 39х' + 5! х'— — 9х — Зб. Затем в строке 4 получаем результат з(х)=х'+х' — Зх~— — 4х'+Зх'+15х+12. Заметим, что з(х) р(х)=х"+полипом степени б.
П Теорема 8.6. Алгоритм 8.6 правильно вычисляет полипом, обратный к данному. Доказательство. Докажем индукцией по я, где /з— степень числа 2, что если з (х) =ОБРАТНЫЙ (р (х)) и р (х) имеет степень л — 1, то в(х)р(х)=х*" '+1(х), где 1(х) — полином степени, меньшей й — 1. Базис, т. е. случай А=1, тривиален, нбо р(х)=а„ в(х)= 1/а, и слагаемого 1(х) нет. Для шага индукции положим р (х) =р, (х)хм'+р, (х), где СТ(р,) = =й/2 — 1 и СТ(р,)(й/2 — 1.
Тогда по предположению индукции, если в, (х)=ОБРАТНЫЙ (р, (х)), то в, (х)р, (х)=х" '+А (х), где СТ(1,) й/2 — 1. В строке 3 вычисляем г(х)=2з,(х)хм!ма ' — (в,(х))'(р,(х)хм'+р,(х)). (8.14) Достаточно показать, что г (х) р (х) =х'ь-'+полипом степени, меньшей 2й — 3. Тогда деление на хл-и в строке 4 дает искомый результат. В силу (8.14) и равенства р(х)=р,(х) хм'+р,(х) имеем г(х) р(х)=2з,(х) р,(х)х'" '+2з,(х) р,(х) хммм-'— — (з, (х) р, (х) кь/'+ з, (х) р, (х))*. (8.15) Подставив х" '+1,(х) вместо в,(х) р,(х) в (8,15), получим г(х) р(х) =х'" ' — (1,(х) хьм+в,(х) р,(х))'. (8.!6) Так как СТ(1,) И2 — 1 и степени полиномов з,(х) н р,(х) не больше я/2 — 1, то степени всех' членов в (8.16), отличных от х"-', не превосходят 2й — 4. П Ясно, что время работы алгоритмов 8.3 и 8.! оценивается схожим образом, если рассматривать две меры сложности (соответственно арифметическую и битовую). Аналогично можно показать, что и другие оценки времени, установленные в равд.
8.2, переносятся а4.модильнхя лгиФматнкх на полиномы, если вместо битовых шагов рассматривать арифметические. Таким образом, верна следующая теорема. Теорема 8.7. Пусть М(п), В(п), !7(п) и З(п) — арифметические сложности соответственно умножения, деления, одрам(ения и возведения в квадрат полиномов от одной переменной. Все зти функции равны с точностью до постоянных множителей. Д о к а з а т е л ь с т в о. Аналогично доказательству теоремы 8.5 и результатов, на которые оно опирается. П Следствие. 77олином степени 2п можно разделить на полинам степени и за время Ол (и 1ой п). Д о к а з а т е л ь с т в о.
В силу теоремы 8.7 и следствия 3 теоремы 7.4. П 8А. МОДУЛЬНАЯ АРИФМЕТИКА В некоторых приложениях удобно выполнять арифметические операции над целыми числами в "модульном" представлении(т. е. в системе классов вычетов). Это значит, что вместо того, чтобы представлять целое число в системе счисления с фиксированным основанием, его представляют вычетами по модулям нз множества попарно взаимно простых чисел.
Если р„р„..., рь,— попарно взаимЬ вЂ! но простые числа и р =Цр1, то любое целое число и, 0<и(р, !=О можно однозначно представить множеством его вычетов и„и„... ...,иь „где и;=и по модулю рь 0<!(я. Когда р„р„..., р,, фиксированы, пишут ич~(и„и„..., иь,). Сложение, вычитание и умножение легко выполняются, если их результаты заключены между 0 и р — 1 (другими словами, если эти вычисления можно рассматривать как вычисления по модулю р), Пусть ич.+(и„и„..., ил,), оч.+(ом о„..., оь,). Тогда и+о!-+(1о„гв„..., и„,), где го, (иг-(-о,) шой р,, (8.!7) и — о!-1(х,, х„..., х,), где х;=(ц — о,) той р„(8.!8) ио+-~(у„у„..., у„,), где у;=и!о! пюй р,.
(8.!9) Пример 8.4. Пусть р,=5, р,=З и р,=2. Тогда 4<-+(4, 1, 0), поскольку 4=4 той 5, 1=4 пюй 3 и 0=4 той 2. Аналогично 7+-+(2, 1, 1) и 281-~(3, 1, 0). Заметим, что в силу (8.19) 4 х 7+-!(3, 1, О), а это — представление числа 28. Первая компонента произведения 4х7 равна 4х2 гной 5, т. е. 3; вторая компонента равна 1х 1 пюй 3, т. е. 1; третья равна ОХ1 гпой 2, т. е. О. Кроме того, 4+71-~(1, 2, !) 333 гл. а АРиФметические опеРАции (представление чиспа 11), 7 — 4 1-1(З, О, 1) (представление числа 3).
С) Однако неясно, как в модульной арифметике экономно выполнять деление. Заметим, что отношение и/о может не быть целым числом, а если бы и было, то в общем случае нельзя найти его модульное представление, вычисляя и,/о1 по модулю р, для каждого 1. Действительно, если р1 не является простым числом, то между 0 и р,— 1 может оказаться несколько целых чисел ю, равных и;/о, по модулю р1 в том смысле, что юо1=и1 (шод р1). Например, если р;=6, о;=3 и и,=З, то в качестве ю можно было бы взять 1, 3 или 5, по. скольку 1хЗ=Зх3=5х3=3(шод 6). Поэтому (и1/о1) гпод р; может не иметь смысла.
Преимущество модульного представления в основном в том, что арифметические операции можно реализовать с меньшими аппаратными затратами, чем при обычном представлении, поскольку вычисления выполняются независимо для каждого модуля. В отличие от обычного (позиционного) представлении чисел, здесь не нужны никакие переносы. К сожалению, проблемыэффективного деления и контроля переполнений (т.
е. выхода результата за пределы области, заключенной между 0 и р — 1) оказываются непреодолимымн, и поэтому такие системы редко реализуются в машинных блоках общего назначения. Тем не менее содержащиеся здесь идеи находят применение, главным образом при рассмотрении полиномов, поскольку делить полиномы скорее всего не потребуется. Кроме того, как мы увидим в следующем разделе, вычисление полиномов и их вычетов (по модулю других полиномов) тесно связаны. Сейчас покажем, что модульная арифметика целых чисел "работает" так, как нужно. Первая часть доказательства состоит в том, чтобы доказать, что соотношения (8.17) — (8.19) выполняются.
Эти соотношения очевидны, и мы оставляем их в качестве упражнения. Вторая часть доказательства — показать, что соответствие и1-1(им и„ ..., иь,) взаимно однозначно (т. е, является изоморфизмом). Хотя этот результат несложен, сформулируем его в виде леммы. Лемма 8,1, Пусть р„ р„ ..., р,, — попарно взаимно проапые 1-1 целые числа, р=Цр1 и и,=и пюд рь Тогда соответствие и~-+ 1еа <-+ (и„и„..., иь,) между целыми числами и в интервале (О, р) и наборами вида (и„и„,. „и„,), 0<и1 < рг при 0<1 < й, взаимно однозначно. Д о к а з а те л ь с т в о. Очевидно, что для каждого и найдется соответствукиций Ьчленный кортеж. Так как в интервале зтл кь модкльн»я»гифматика (О, р) заключено ровно р значений переменной и и допустимых Й-членных кортежей также ровно р, достаточно показать, что каждый такой кортеж соответствует не более одному целому числу и. Допустим, что два числа и н и, О.
и(о(р, соответствуют кортежу (и„и„..., и»,). Тогда разность и — и должна делиться на каждое число рь Поскольку все р, попарно взаимно просты, разность и — и должна делиться и на р. Но ичьп и а — и делится на р, так что и и о должны разниться не менее чем на р и, значит, не могут оба лежать между 0 и р — !. П Для того чтобы можно было пользоваться модульной арифметикой, нужны алгоритмы, осуществляющие переход от позиционного представления к модульному и обратно. Один из методов перехода от позиционного представления целого числа и к его модульному представлению состоит в том, чтобы разделить и на каждое из чисел р;, 0(!(л. Допустим, что каждое из чисел р~ содержит Ь разрядов в двоичном представлении.
Тогда для представления »-1 р=Пр |=о требуется, грубо говоря, Ьй битов (двоичных разрядов), а деление и на каждое из чисел ро где 0(и(р, могло бы потребовать /г делений ЬЬ-битового числа на Ь-битовое число. Разбив каждое деление на й делений 2Ь-битовых чисел на Ь-битовые, можно перейти к модульному представлению за время Оа(л»»у(Ь)), где !7(п) — время деления целых чисел (не превосходящее Оа(а !оя л )оя )од и) в силу следствия теоремы 8.5). Однако можно проделать эту работу за значительно меньшее время, если применить метод, напоминающий метод деления полиномов из разд.
7.2. Вместо того чтобы делить число и на каждый из и модулей р„р,,..., р „сначала вычисляем произведения р, р„ р,р„ ..., р», р» „ затем р, р, р, р„ р, р, р,р„ ... и т. д. Далее вычисляем вычеты с помощью приема "разделяй и властвуй". Деля, получаем вычеты и, и и, числа и по модулям р,... р»м и р»~о... р» , соответственно. Теперь задача вычисления и пюд рь О(!(/о, сведена к двум подзадачам половинного размера, а именно и тод р,=и, пюд р, для 0 =!(/о/2, и и пюд р,=и, пюд р~ для й/2(!(й. Алгоритм 8.4. Вычисление вычетов Вход. Модули р„р„..., р„, и такое целое число и, что »-~ 0(и(р=П р . ~ьо Выход.
Числа и;, О~!(л, такие, что и,=и пюд рь Мелюд. Допустим, что /о — степень числа 2, скажем /о=2'. ГЛ. 8. АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ (Если нужно, добавим ко входу лишние модули, равные 1, чтобы сделать й степенью числа 2.) Начинаем с вычисления определенных произведений модулей, аналогичных полиномам о,„из разд. 7.2. Пусть 0 =!(1, число 1 кратно числу 2г и О~л(й; положим С+8/-8 9»= П Р Таким образом, 9~е=р8 и 9ы=4~»-891+1 '»-8 Сначала вычисляем числа ды, затем находим остатки иы от деления и на каждое нз чисел ды. Искомым ответом будут числа ипн Детали приведены в программе на рис. 8.3.
П Теорема 8.8. Алгоритм 8.4 правильно вычисляет числа и;. Д о к а з а т ел ь с т в о. Доказательство следует плану доказательства теоремы 7.3, где вычислялнсь значения полинома в корнях и-й степени из единицы. Легко показать индукцией по 1, что строка 4 правильно вычисляет числа дц.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
