1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 68
Текст из файла (страница 68)
Первые СТ(у) — й членов, полученных таким способом, не зависят от а,(х). Но частное содержит лишь члены степени СТ(/) — СТ(д). Поэтому если СТ(/) — СТ(д)(СТ(д) — й, т. е. йк: (2СТ(у) — СТ(о, то частное не зависит от у,(х). Если СТ(7) — СТ(д)( (СТ(/) — й, то частное не зависит от Ях). Но неравенство СТ(7)— — СТ(д)«СТ(/') — й следует из й<2СТ(у) — СТ(/) и СТ(/))СТ(у). Таким образом, утверждение (а) доказано. Что касается утверждения (б), то аналогичные рассуждения показывают, что члены остатка, имеющие степень СТ(/) — (СТ(д) — й) и выше, не зависят от д,(х). Аналогично члены остатка, имеющие степень й и выше, не зависят от /,(х). Но СТ(/) — СТ(д)+й)й.
Таким образом, в г(х) и г,(х)х" все члены степени СТ(/) — СТф)+й и выше совпадают. П Лемма 8.7. Пусть /(х)=/((х)хь+/,(х) и д(х)=д((х)хь+д,(х), где СТ(7',)Сй и СТ(д,)(й. Пусть СТ(/)=и и СТ(6) =СТ(/). Тогда Р(/. г) = >?и» еп "е, ((((«+А>/ь1) "ю, ((((А-М/(>п т. е. частные, входящие в последовательности остатков для (т, д) и (/>, а(), совпадают по крайней мере до того места, где во второй последовательности появляется остаток степени, не большей поло- вины степени полинома Д о к а з а т е л ь с т в о. Лемма 8.6 гарантирует совпадение частных и достаточного количества старших членов в соответствую- где СТ(д,)(й. Пусть (/ и (/( — частные( ~(х)/д(х) ~и( ~((х)/д((х) (, а г и г,— остатки / (х) (/ (х) д (х) и 7( (х) — (/( (х)д((х) соответственно.
Если СТ(/))СТ(д) и йе=2 СТ(д) — СТ(7) (т. е. С 6(д())(/,СТ(/>)), то (а) () (х) =(/((х), (б) в > олиномах г(х) и г,(х)х" все члены степени й+СТЯ вЂ” СТ(6) и выше совпадают. 8.8, АЛГОРИТМ НАХОЖДЕНИЯ НОЛ ПОЛИНОМОВ щих остатках, входящих в рассматриваемые последовательности. П Теорема 8.17. Пусть аа(х) и а,(х) — такие полиномы, чпю СТ(а,)=п и СТ(а,) <и.
Тогда ПНОД(а,, а,) =)зь,кань Д о к а з а т ел ь с т во. Теорема доказывается простой нндукцней по и, в которой учитывается лемма 8.7, чтобы гарантировать, что матрица )7 в строке 4 равна )7оь'1(зз'~ззь а 5 в строке 9 равна (аэ. ап Йгпзл!зп+ Из ьаь П Теорема 8.18. Процедура ПНОД выполняется за ОА(М(п)1ой п) шагов, если ее аргументы имеют степени не выше и; здесь М (п)— время умножения двух полиномов степени и. Д о к аз а тел ь ство. Докажем утверждение для случая, когда п степень числа 4. Поскольку время выполнения процедуры ПНОД, очевидно, не убывает с ростом и, то наша теорема будет тогда верна и для произвольного и. Если СТ(а,) — степень числа 4, то СТ (Ь,) = — СТ(а,), СТ(д,) ( — СТ(а,) .
Таким образом, время Т(п) выполнения процедуры ПНОД для входа степени п удовлетворяет условию Т(п) (~2Т ( — ) +сМ (п) (8.27) для некоторой постоянной с. Другими словами, тело процедуры ПНОД включает в себя два вызова той же процедуры для аргументов половинного размера и постоянное число других операций с временной сложностью ОА(п) илн ОА(М(п)), Решение неравенства (8.27) должно быть известно читателю; оно ограничено сверху функцией с,М(п)1одп для некоторой постоянной с,.
П Перейдем к изложению полного алгоритма нахождения наибольших делителей. В нем участвует процедура ПНОД, вычисляющая вагиз, затем Йо.з Рь Йо,за~8 н т. д., где п — степень входа. Алгоритм 8.7. НОД-алгоритм Вход. Полиномы р,(х) н р,(х), для которых СТ(рз)(СТ(р,). Выход, Наибольший общий делитель НОД(РН Рз) для Рз н Р . Метод. Вызываем процедуру НОД(ри р,), где НОД вЂ” рекурсивная процедура, приведенная на рис. 8.8. П Прнмер 8.12.
Продолжим пример 8.11. Там р,(х)=х'+х'+х'+ +х'+1 и р,(х)=х' — 2х'+Зхз — х — 7. Мы уже нашли, что 1 — (х+ 3) — — х — — ~~ — х'+ — х+— ~ 4 Гб/ 4 Гб Гб) 343 ГЛ. 8. АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ ргосебнге НОД (а„а,): 1.
И а, делит а„(!8еп ге1пгп а, е!ее Ьей(п 2. )с — ПНОД (а„а,); 3. ф- й(. [~1; 4. И Ь, делит Ье 1Ьеп ге1пгп Ь, е!ее Ьей(п 5. с Ь, щодЬ,; 6. ге1пгп НОД(Ь„с) Ене( епб Рес. 8.8. Процедура НОЙ. Поэтому в строке 3 вычисляем Ь, = 4х' — 7х*+ 11х + 22, 3 8 93 46 Ь = — — х* — — х —. 16 !6 8 Обнаруживаем, что Ь, не делит Ь,.
В строке 5 находим, что Ь„щод Ь, = 3952х+ 3952. Так как последний полипом делит Ь„то вызов процедуры НОД в строке 6 завершает работу в строке 1 и выдает в качестве ответа 3952х+3952. Разумеется, х+1 также является наибольшим общим делителем для р, и р,. П Доказательство корректности алгоритма 8.7 тривиально, если доказать, что он заканчивает свою работу. Таким образом, коррект. ность алгоритма вытекает из анализа времени его работы, что составляет содержание следующей теоремы.
Теорема 8.!9, Если СТ(р,)=п, то алгоритм 8,7 выполняется за ОА(М(п) !ой и) шагов, гдв М(п) — время рмноясения дврх полиномов степени и. Д о к а з а тел ь ство. Неравенство Т (и) ~ Т ( — ) + с,М (и) +с,М (и) 1ой и, (8.28) где с, и с, — постоянные, описывает время работы алгоритма 8.7. Действительно, степень полинома Ь, меньше половины степени к ! О ИОД ЦЕЛЫХ ЧИСЕЛ полинома а,, так что первое слагаемое в (8.28) отражает рекурсивный вызов в строке 6. Слагаемое с,М(и) отражает деления и умножения в строках 1, 3 — 5, с,М(п) )од и — вызов процедуры ПНОД в строке 2. Легко видеть, что решение неравенства (8.28) ограничено сверху функцией )ОМ(и) (од п, где й — некоторая постоянная.
П Следствие, НОД двух полиномов степени не выше и можно вычислить эа время 0»(п 1од'п). 8.10. ИОД ЦЕЛЫХ ЧИСЕЛ Обсудим кратко изменения, которые надо произвести в процедурах ПЙОД н НОД, чтобы они годились для целых чисел. Чтобы понять, где возникают трудности, вернемся к лемме 8.6, показывающей, что при нахождении частных от деления полиномов степеней и и и — д нам ни в одном из них не нужны члены степени, меньшей и — 2д.
По аналогии с леммой 8.6 можно рассмотреть два целых числа ~ и д, )>д, и записать их в виде ~=),2»+)» и гг=д,2»+Е„где ),<2» и д,<2». Вместо условия СТ(д,(х))=»»),СТД,(х)) можно предполагать, что 1',<(д,)к. Тогда можно считать, что 1=дд+г и ),=-д,д,п-гь Комбинируя эти формулы, получаем д,2» (д — д,) = (» + г,2" — ад» вЂ” г. (8.29) Так как г,<дн )О<2» и все эти целые числа неотрицательны, легко вывести из (8.29), что а — о,<0. Пусть о=о,— т для некоторого т)0.
Тогда из (8.29) заключаем, что тд,2» < од + г = (а, — т) д» + г. Следовательно, ту = ту,2" + тд, <дд, + г. (8 30) Поскольку ),<(д,)», то д,(~,. Кроме того, по условию д,<2» и к<8, так что из (8.30) вытекает, что тд < д,2»+д -.2д. (8.31) Теперь из (8.31) непосредственно следует, что т<2. Отсюда заключаем, что или о=он или о=о,— 1. В первом случае нет трудностей, Если же о=о,— 1, то нельзя рассчитывать, что процедура ПНОД сработает правильно. К счастью, можно показать, что д,~д, только если д — последнее частное в последовательности остатков, для которого процедура ПНОД строит матрицу. Иными словами, подставляя д — д,= — 1 в (8.29), получаем (8.32) г = (» -1- г,2" — од» + д,2».
ГЛ. Е АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ Так как г(й=й,28+8„то из (8.32) вытекает г828+~8с д8(1+у) и тем более г,(1+у, а значит, г,(уи Итак, число г„которое стоит в последовательности остатков после ~, и йи должно быть меньше 1,/дь ПосколькУ д8))Я, то г,( ()Я, а это означает, что процедура ПНОД выдала бы матрицу, со. держащую частные вплоть до (8(йь но не далее.
Если эта матрица используется в строке 6 процедуры ПНОД, то может оказаться, что число 1, вычисляемоев строке 6, будет не меньше азь". Но поскольку ошибка в последнем частном равна всего 1, можно показать, что продолжение последовательности остатков на ограниченное число членов (не зависящее от размера а,) после выполнения строки 6 будет достаточно для того, чтобы один из очередных членов этой последовательности стал меньше азь". Аналогичный прием надо при. менить и после строки 6 процедуры НОД.
Еще один круг трудностей связан с леммой 8.6. В случае полиномов мы смогли показать, что в последовательности остатков, образованной с привлечением старших членов полиномов, определенные члены высокого порядка совпадают с соответствующими членами в последовательности, образованной по всем членам полиномов. Аналогичный результат приближенно выполняется и для целых чисел при условии о=о,. Однако можно только ограничить разность между г и г,2" числом 28(у+1); нельзя гарантировать, что какие-нибудь конкретные разряды чисел г и г,2" будут совпадать. Тем не менее такой источник "ошибок округления" приведет к тому, что после выполнения строки 6 процедуры ПНОД и строки 5 процедуры НОД в последовательности остатков понадобится лишь ограниченное число дополнительных членов. Из-за продолжения последовательности остатков на ограниченное число членов, сложность алгоритма увеличивается на Ое(М (и)), где М(п) — время умножения и-разрядных двоичных чисел, так что анализ времени работы процедур ПНОД и НОД, по существу, не изменится.
Поэтому справедлива следующая теорема. Теорема 8.20. Если М (и) — время умножения двух и-разрядных двоичных целых чисел, то существует алгоритм, отыскивающий их наибольший общий делитель за Ое(М (и) 1ой и) шагов. До к а з а тел ь с т в о. Упражнение на предложенную выше модификацию процедур ПНОД и НОД„П Следствие. НОД двух целых чисел можно найти за время Ое(п 1о88 п 1ой 1ой п). П ЗЛ!. БШБ РАЗ О КИТАЙСКОЙ ТБОРБМБ ЕЛ!. ЕЩЕ РАЗ О ПРИМЕНЕНИИ КИТАЙСКОЙ ТЕОРЕМЫ ОБ ОСТАТКАХ Мы обещали показать, как применить НОД-алгоритм для по.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
