1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 66
Текст из файла (страница 66)
Программа вычисления целого числа по его модульному представлению. ге 2/ Метод. Сначала вычисляем до/ — — Бр, как в алгоритме 8.4'). «о=1 Затем запускаем программу на рис. 8.4 в предположении, что в ней гь 2/-1 3// = ; — Е Ч//бана П Ра Пример 8.6. Пусть р„р„р„р, равны соответственно 2, 3, 5, 7 и (н„и„и„нз)=(1, 2, 4,3). Тогда г/го — — рг для 0~1 4, г/ог=6, дог=35 и г/оз=р=210. Далее, г(о (Зоо5а7) ' опоо( 2 = 1, поскольку 1 и 1 05 = — 1 (гпоо( 2), 11,=(2и5и7)- пгог$3=1, поскольку 1и70 =1 (п1ог(3), с(о=(2и3н7) ' нгой5=3, поскольку За 42 =1 (пгой5), 11,=(2и3и5) ' пзо67=4, поскольку 4и30 — 1 (п1ой7). Таким образом, в строке 1 вычисляются аоо=1и1= 1, зхо=1" 2= 2 зоз=3и4=12 аоо=4и3=12 Затем выполняется цикл в стрсжах 3, 4 с 1=1.
Здесь 1 принимает значения 0 и 2; следовательно, вод = зооирхо + зхоиЧоо = 1и3+ 2и2 = 7 о зы = зооиозо+ азово/оо = 12и7 + 12и5 = 144 Далее выполняется цикл в строках 3, 4 с /=2, а 1 принимает только значение О. Получаем зоо = зогао/ос + зогио/ог = 7и35+ 144»6 = 1109. ') Эаметим, что числа е// зависят только от чисел рь Можно включить их во входные данные, а не вычислять, ибо разрешается предварительная обработка. Но легко показать, что на порядок времени работы не влияет, вычислены заранее зги е// или нет. 331 Гл. а АРиФметические ОЛЯРАции Ряс.
8.6. Вычисления яз прнмера 8.6. Таким образом, результатом строки 5 будет 1109 пюй 210, т. е. 59. Можете проверить, что вычеты числа 59 по модулям 2, 3, 5 и 7 равны 1, 2, 4 и 3 соответственно. На рис. 8.5 эти вычисления изображены графически. П Теорема 8.11, Алгоритм 8.5 правильно вычисляет целое число и, для которого и++(и„иь..., и„,). Дока з а тел ь ство. Элементарная индукция по 1' показывает, что в» принимает нужное значение, т. е. с+гг-1 в»= Х, уой и (Р .
Корректность алгоритма непосредственно следует из леммы 8.2, т. е. из справедливости формулы (8.20). П Теорема 8.!2. Пусть даны й попарно взаимно простых целочисленных модулей р„р„..., рг, и вычеты (и„и„..., и„,). Если каждое из чисел р, содержит не более Ь битов, то существует алгоритм с предварительной обработкой данных, вычисляющих число а.т. интеРпОляция ООлинОМОВ а †! и, для которого 0<и .,р=пр, и ич-е(и„ ии ..., и„,), эа время з=о Ов (М (Ьк) !ОЕ lе), где М (л) — время умножения двух л-битовых чисел. Д о к а з а т е л ь с т в о.
Вычисление чисел ды занимает Ов(М(Ья) !ОЕ я) времени '). Для анализа тела алгоритма заметим, что э» содержит не более Ь2У+Ь+!' битов, ибо является суммой 2) слагаемых, каждое из которых равно произведению 2У+1 целых чисел, состоящих не более чем из Ь битов.
Поэтому каждое слагаемое содержит не более Ь(2/+1) битов, а сумма 2У таких слагаемых— не более Ь(2У+1)+!од (2У)=Ь2'+Ь+! битов. Таким образом, строка 4 занимает время Ов(М (Ь2У)). Цикл в строках 3, 4 повторяется й/2l раз для фиксированного 1, так что весь цикл выполняется за Ов Я М(Ь2У)) шагов, а в силу обычного предположения о росте функции М(л) это не превосходит Ов(М (ЬЬ)).
Так как цикл в строках 2 — 4 итерируется 1ой й раз, то общая сложность составляет Ов(М(Ья) 1ОЕ Ь) шагов. Легко показать, что сложность строки 5 меньше. (:! Сведствие. Китайский алгоритм с предварипмльной обработкой данных, примененный к Ь модулям по Ь битов в каждом, работает не более Ов (Ья 1ОЕ й 1ОЕ ЬЬ 1ОЕ 1ОЕ Ьй) времени.
8.7. КИТАЙСКАЯ ТЕОРЕМА ОБ ОСТАТКАХ И ИНТЕРПОЛЯЦИЯ ПОЛИНОМОВ Должно быть ясно, что все результаты предыдущего раздела справедливы и для полиномиальных модулей, а не только для цело- численных. Поэтому верны следующая теорема и ее следствие. Теорема 8.13. Пусть р,(х), р,(х),..., ра,(х) — полиномы сте- пени не больше й и М (л) — число арифметических операций, необ- ходимых для умножения двух полиномов степени л. Пусть и,(х), и (х), „иа- (х) — такие полиномы, что степень полинома из(х) меньше степени полинома р,(х), 0(!<у.
Тогда существует алгоритм с предварительной обработкой данных, вычисляюи!ий эа время Оа(М(йй) 1ОЕ Ь) тот единственный полипом и(х) степени, а — ! меньшей степени лолинома р (х)=33 рз (х), для которого шо и (х) с-ь (и, (х), и, (х), ..., ив, (х)), Д О к аз а тел ь от в о. Применяется аналог алгоритма 8.5 и доказательство следует доказательству теоремы 8.12.
(:) '! Поскольку 0(в) и М (в! но существу равны, мы предпочитаем везде употревлвть М(п!. 333 ГЛ. З. АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ Следствие. Сугцесптвует алгоритм восстановления полиномов по остаткам (согласно китайской теореме) с временной сложностью ОА (й/з 1оп й 1оя й/з). Рассмотрим один важный частний случай: все модули имеют степень 1. Если р, (х)=х — а„О<!<й, то вычеты (числа и;) постоянны, т.
е. являются полиномами степени О. Если и (х)=и, (гпод (х — а,)), то и(х)=д(х) (х — а,)+и, и, значит, и(а;)=ио Таким образом, единственным полиномом и(х) степени, меньшей /з, для которого и(х)е-з ео (и„и„..., и,,), будет тот единственный полипом степени, меньшей й, для которого и(а;)=и; для каждого г, 0<!<й. Другими словами, и(х) — зто полипом, интерполируемый по значениям и, в точках аь 0 =/</г.
Поскольку при работе с полиномами интерполяция очень важна, мы с удовольствием отметим, что интерполяцию по значениям в й тОЧКаХ МОЖНО ВЫПОЛНИТЬ За ВрЕМя ОА (й 1Ояз /Г), дажЕ ЕСЛИ НЕт ПрЕдварительной обработки данных. Это объясняется тем, что здесь, как мы увидим из следующей леммы, легко найти значения коэффициентов г( из (8,20) '). Лемма 8.3. Пусть р,(х)=х — а, для 0(з</з, где все а; различны з — ! (т, е.
все р,(х) взаимно проста). Пусть р(х)=Дрз(х), с;(х)= г=е =р(х)/р;(х) и й,(х) — постоянный полинам, причем йз(х)сз(х)=1 (пюдр,(х)). Тогда йз(х)=1/Ь, где Ь= — р(х)(,=,Р До к а э а тел ь ст в о. Запишем р(х)=с~(х) р;(х), так что — р (х) = р, (х) — с, (х) -1- с, (х) — р; (х). в в в (8.21) Далее, йрз (х)/йх=! и р, (а,\=О, поэтому (8.22) ! Заметим, что й (х) обладает тем свойством, что й;(х) с,(х)= — 1(шог((х — а~)), и, значит, йз(х)с~(х)=-у;(х) (х — а,)+1 при некотором у~ (х). Таким образом, йз (а,)=1/с, (а,).
Теперь лемма немедленно следует из (8,22), поскольку й;(х) — постоянная. П Теорема 8.14. Интерполяцию полинома ло значениям в й точках можно вьтолнить за время ОА(й 1одз й) без предварительной обработки данных. Д о к а з а т е л ь с т в о. В силу леммы 8.3 вычисление полиномов й~ эквивалентно вычислению значений производной некоторого т) Кзк упоминзлось в рззд. 8.6, зтв зздзчз в действительности несложна и в общем случае. Но в общем случае нужна техника следующего раздела. ззз к7.
интеРлоляция полиномоз Ф-1 полинома степени й — 1 в й точках. Полинам р(х)=Ч р~ (х) можно получить за время Оа (й 1оя' й), если сначала вычислить р,р„р,р„ затем р,р,р,р„р,р,р,р„... и т. д. Производную полинома р(х) можно найти за Оа(А) шагов. Вычисление значений производной занимает Ох(А !од' А) времени в силу следствия 2 теоремы 8.10. Теорема вытекает теперь из следствия теоремы 8.13 при а=1. С) Пример 8.7. Проннтерполируем полинам по следующим парам (точка, значение): (1, 2); (2, 7); (3, 4); (4, 8). Здесь а;=!+1 для 0~!<4, и,=2, и,=7, и,=4 и и,=8 Тогда р! (х)=х — !' — 1, а полинам э р(х)=Црр(х) равен х' — 10 х'+35х' — 50х+24. Далее, др(х)/ах= о=а =4х' — 30х'+70х — 50, и в точках 1, 2, 3, 4 этот полипом принимает соответственно значения — 6, 2, — 2, 6.
Таким образом, д„дм д, и И, равны соответственно — '/„17„— '!, и '!,. С помощью быстрого китайского алгоритма 8.5, переделанного для полиномов, получаем эм =!)оиер1+г(ти1ро = ( 6 ) (2) (х — 2)+ (2 ) (7) (х — 1) = !9 !7 = — х —— 6 6 ' э„ = Й,и,р, + Й,и,р, = ( — 2 ) (4)(х — 4) + ( 6 ) (8) (х — 3) =* 2 3 = — — х+4 и затем з„= и (х) = з„дм + э„а„= Г!9 !71 ( 2 (6 6) = ~ — х — 1 (х' — 7х — 12) + ! — — х+ 4 ! (х' — Зх+ 2) з У и (х) = — х' — 19х'+ — х — 26. 6 89 2 П Как отмечалось в гл. 7, такие арифметические операции над полиномами, как сложение и умножение, можно выполнять, вычисляя полиномы в л точках, производя над найденными значениями арифметические операции и затем интерполнруя полинам по полученным в результате значениям.
Если на выходе должен быть полинам степени не более л — 1, то этот способ приведет к правильному ответу. Метод БПФ именно это и делает в случае, когда в качестве л точек берутся числа ы0, !»',..., м" '. Здесь алгоритмы вычисления значений и интерполяции оказались особенно простыми благодаря ствойствам степеней числа м и специального упорядочения их.
Однако стоит заметить, что вместо степеней числа м можно было бы взятьлюбойнабор точек. Тогдаунас было бы такое "преобразова- ээз ГЛ Ь. АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ ние", что на всю задачу (преобразование, вычисления и обратное преобразование) потребовалось бы ОА(п !од' и), а не ОА(п 1он и) времени. 8.8. НАИБОЛЬШИЕ ОБЩИЕ ДЕЛИТЕЛИ И АЛГОРИТМ ЕВКЛИДА Определение. Пусть а, и а,— положительные целые числа. Положительное целое число Е называется наибольшим сби(им дели. телем чисел а, и а, (его часто обозначают через НОД(а„а,)), если 1) у делит а, и а„ 2) всякий общий делитель чисел а, и а, делится.
Легко показать, что для положительных целых чисел а, и а, такое число Е единственно. Например, НОД(57„33)=3. Алгоритм Евклида для вычисления НОД(а„а,) состоит в вычислении последовательности остатков а„а„..., а, где аь 2» '1(й,— ненулевой остаток от деления а~, на а~, и аь нацело делит а„, (т. е. аь„,— — 0). В этой ситуации НОД (а„а,)=а„. Пример 8.8. В примере, приведенном выше, а,=57, а,=ЗЗ, а,=24, а,=й, а,=б и а,=З. Поэтому 8=5 и НОД (57, 33)=3. П Теорема 8.15.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
