В.Б. Алексеев - Введение в теорию сложности алгоритмов (1114530), страница 4
Текст из файла (страница 4)
При этом О можно предварительно получить подсхемой с 2 эпементами, реализующей хохо = О. Так как сложность каждого сумматора можно сделать не более 0(и), то сложность подученной схемы будет пе больше чсм Ь(М„) +0(71). Пусть теперь нужно перемножить два 2и-разрядвых числа Х и У. Разобъем их на части, содержащие по и разрядов. Тогда получим Х = Х12" + Хо, У = У12" + 12. Отсюда ХУ = Х1112 + (Х112+ Х211)2" + Х212 = = Х,У2'"+ [(Х1+ Х,)(1;+ 1;) — Х,1; — Х,У]2" + Х,У,. Так как Х112 + Х21"1 > О, то при вычитании в квадратной скобке ие возникает отрицательных чисел. Таким образом, умножение ХУ двух 2и-разрядных чисеп сводится к двум умножениям и-разрядных чисел Х1У1 и Х212, умножению и + 1-разрядных чисел (Х1 + Хз)(11 + 12) и нескольким сложениям и вычитаниям чисел с числом разрядов не более 4и (так как ХУ < 21").
Умножение и+1-разрядных чисел (Х1+Хз)(У1+ Уз) можно (как указано выше) свести к умножению и-разрядных чисел. Таким образом, умножение двух 2и-разрядных чисел сводится к трем умножениям и-разрядных чисел и 0(и) дополнительных операцвй. В резулътате дпя сложности Ьк(и) алгоритма Карапубы имеем Ьк(2и) < ЗЬк(и) + О(и). Ппя и = 1 применяем обычный алгоритм (одна конъюнкция), длк и = 2" (й = 1, 2, 3,... ) применяем описанную рекурсию, для 21 1 < и < 2~ дописываем в перемвожаемые числа спереди нули, делая длину равной 21, и применяем рекурсивный алгоритм дпя 21-разрядных чисел. В результате по теореме 2.4 о рекуррентном неравенстве дпя описанного алгоритма Карацубы получаем 1, (и) = 0(иьэ!2) Теорема джаэана. 2.4. Алгоритм Тоома для умножения чисел Здесь мы рассмотрим еще более быстрый алгоритм для умножения чисел, который предложил А.
Л. Тоом [15]. Нам потребуется сведующей известный факт о многочпенгх. з твержденне (ивтерпопяционная формула Лагранжа). Пусть Р(х) = спх" +с„-»х" ~+...+с»х+со — произвольныс полипом степени и,. значения. когпорого Р(д ) известны в и + 1 различных точках дм да,..., дп+ь Тогда существуют такие констпанты а~„зависящие тоько о1ид»,да,...,д„+ь что со — — ~~~ с»епР(д„,), д = О, 1,..., п. (2.4) ем »в При этом, если все 4„рациональньь, то и все а~ рациональны. Теорема 2.6.
Юля любогв фиксированного г ) О выполняется М(и) = О(иые), где М(п) — минимальная битовая сложность умноохвния двух п-разрядных двоичных чисел. Показательство. Зафиксируем натуральное Л > 2 и рассмотрим спепующий алгоритм Тоома [15] дпя умножения и-разрядных двоичных чисел А и В. Если Л"' » < и < Л, то увеличим разрядность до Й~, приписывая спереди нули. Дпя и = Й~ поступаем следующим образом. Режем А и В на Л кусков длины ~к"' ». Пусть А = (А» »А» г...А»Ао)г и В = (В» »В» г... В»Во)г, Рассмотрим многочпены Дх) = А»»х»» + А» гх» г + + А»х + Ао и д(х) В»-»х ~+В»-ах~ г+...+ В|х+Во. Тогда А = Д2» ), В = д(2» ) иискомоеС = А В =1(2 ).д(2» ) = Л(2» ),гдеЛ(х) = Дх) д(х).
Заметим, что Л(х) — миогочлен степени 2Л вЂ” 2. Алгоритм состоит из спгцуюших шагов. 1. Вычисляем Ддн) и д(д ), где дмйг,..., дм 1 — любые фиксированные целые точки (например, д = О, х1, х2,..., х(Й вЂ” 1)). 2. Вычисляем Л(д ) = ДЫ )д(д ) тем же алгоритмом для и = Л"' (мы уточним это виже). 3. По формуле (2.4) вычиспяем коэффициенты с (д = О, 1,..., 2Й— 2) многочпена Л(х). 4. Вычисляем Л(2»" ) = С = АВ. Оценим теперь сложность каждого шага. Отметим, что х = и, к~ ~ = ~~ и й — константа.
Шаг 1. На этом шаге вычисляем 3'(с~ ) и д(13,„) непосредственно по формулам многочленов, выполюся все операции "в столбик". При этом, так как все о — константы и 3с — константа, вычисление всшс 11' (т = 1, 2,,, 2Й вЂ” 1; 1 = 2, 3,..., Й вЂ” 1) требует константного числа битовых операпий и ллины всех получаемых чисел ограничены константой (зависящей от Ь, но не зависящей от и). Поэтому вычисление всех одночленов Асс' требует 0(п) битовых операций и длины получаемых чисел не превосходят "- + солей Аналогично для В113,'„. Складывая эти одночлены (Ь вЂ” константа), получаем, что вычисление всех значений 1 (И ) и д(Н ) требует 0(п) битовых операций и длина всех этих значений не превосходит т + сопзс. Шаг 2.
На этом тоаге нам надо 21с — 1 раз перемножить числа длвны не более "-+ солей Пусть С и Р— 2 таких числа, и С = (С1Со) з, Р = (Р1Ро)9, где длина чисел Со и Ро равна ~. Тогда С Р = (С1 . 2Г+ Со) (Р1. 29 + Ро) = С1.01 2т + (С1Ро+ СоР1) 2с + СоРо Будем вьгчислять С1Р1, 01Ро, СоР1 "в столбик", а СоРо рекурсивно тем же алгоритмом, если длина Со и Ро, равная 39 ', больше 1. Если же Ь~ 1 = 1, то СоРо также вычисляем "в столбик". Пусть 1т(п)— битовая сложность алгоритма Тоома (в худшем случае) для умножения чисел длины и. Тогда число операций на шаге 2 ие превосходит (2Ь— 1)Ьт(а) + 0(п), и получающиеся числа имеют длину 0(п). Шаг 3. Так как все д,„— целые, то все сс в формуле (2.4) рациональные.
Пусть 33 — их общий знаменатель и сс = -Яв. Тогда все 33 — целые и сс = ~2 ', Д„,Ь(И ). Так как 1с — константа, все )3 „— константы и длина всех чисел Ь(4„) есть 0(п), то для вычисления всех сумм 2":, 33т Ь(с3 ), д = О, 1,...,239 — 1, требуется 0(п) битовых операций и при этом получаются числа длины 0(п). Так как 33 — константа, то вычисление всех с (которые заведомо должны быть целыми, как козффидиенты многочлена Ь(х) = т" (х)д(х)) требует 0(п) битовых операпий (делим "в столбик"), и все сс имеют длину 0(п). Шаг 4. Вычисление Ь(2~ ) сводится к сложению чисел сс, сдвинутых влево не более, чем на и разрядов.
Так как чисел сс константное количество, то вычисление Ь(2" ') = С = АВ требует 0(п) битовых операций. Для общего числа йт(п) битовых операций в описанном алгоритме (при и = Ь"') имеем Рт(п) ( (2Ь вЂ” 1)Рт( — ) + 0(п). 19 Тогда по теореме 2.4 о рекуррентном неравенстве для всех и получаем 1 (и) = 0(пиз (ь-О) С ростом !т имеем 1 !ось(2!с — 1) = 1+ !оеь(2 — -) — т 1. к Поэтому для любого е ) О можно выбрать к так, что !обе(2Й вЂ” 1) ( 1+ с и Ьг(п) = 0(п~+т).
Теорема доказана. Замечание. Еше более быстрым является алгоритм умножения чисел Шенхаге и Штрассена, битовая сложность которого равна 0(п!ояп!оя!ояп) [16]. 2.5. Алгоритм Штрассена для умножения матриц Рассмотрим задачу умножения двух квадратных матриц А = []ау[] и В = ]]Ьм[[ порядка п. Пусть А В = С = ][с„т[]. Тогда по определению с„= 2 " т атэбр,. В хачестве входа мы бУдем РассматРивать все значения а;,.
и ум, считал их "неделимыми", то есть мы воспринимаем их как единое целое и не можем работать с какими-либо их чэстюли. В качестве операций будем рассматривать 4 арифметические операции, которые могут применяться как к исходным переменным ау, ум, так и к уже построенным выражениям. Наша задача состоит в получении всех выражений для с„,. Сложностью алгоритма будет считаться число арифметических операций. Обычный алгоритм умножения матриц ("строчха на столбец" ) требует пз умножений и пз(п — 1) сложений, то есть порядка пз операпий. Более быстрый по порядку алгоритм типа "разделяй и властвуй" предложил Штрассен [17]. Теорема 2.7 (В.
Штрассеи). Юля умножения двух матриц порядка и сутцестеуетп алеоритм с числом арифметпических операций 0(п"нт т) Воказатпельстпео. Опишем такой алгоритм. Если и — не степень двойки и ближайшая к и сверху степень двойки есть 2ь, то расширим данные матрицы А и В до матриц А' и В' порядка 2ь так, чтобы в левых верхних углах матрид А' и В' стоюти, соответственно, А и В, а остальные элементы были равны О. Тогда, если А' ° В' = С', то легко видеть, что в С' в левом верхнем углу стоит матрица С = А ° В, а остальные элементы равны О. Поэтому для вычисления С = А В достаточно перемножить матрицы А' и В' порядка 2". Пусть далее в = 2" — степень двойки и А,  — матрицы порядка и = 2ь. Разрежем каждую из матриц А и В, а также искомую матрицу С = А .
В, на 4 квадратных блока размера - "х "-: Ап Аьз ( Вп Вьз ~ Сп Сьз Ам Азз ' ( Вд Взз ' ~ Сзз Сзз Иэ алгебры известно, что в этом случае Сп = АцВц+АыВм, Сы = АцВи+ АгзВзз, Сзз = АззВп+АюВзь Сзз = АззВы+АззВзз. Таким образом, вычиспение матрацы С сводится к 8 умножениям матриц порддка -" (н нескольким сложениям).
Идея Штрассена состоит в замене 8 умножений на 7 (сравните с алгоритмом Карацубы). Рассмотрим следующие 7 произведений; Р~ = (Ап + Азз)(Вп + Взз), Рз = (Ап + Аы)Взз, Рз = ( — Азз+Ам)(Вы+ Вьз), Рз = Азз(-Вы+ Взз), Рз = (Аы — Аю)(Вм+ Вю), Рг = (Ам+ Агз)Вп- Р4 = Ап(Вы — Взз), Раскрывая скобки и приводя подобные члены, можно проверить, что Сп = Рз + Рз — Рз + Рз Си = Р4+ Рз, См — — Ра+ Рп Сю = Рг+ Рг+ Р4 — Рг.
Таким образом, умножение матриц порядка п сводится к 7 умножениям матриц порядка "- и нескольким сложениям матриц порядка "-..Если о = 2", то этот пропесс можно продолжить рекурсивно. Если же н = 1, то для умножения матриц порядка 1 требуется всего 1 умножение элементов. Пусть 1 (а) — число арифметических операций в описанном алгоритме. Так как сложение двух матриц порядка "- требует 0(из) операций, то для о = 2" (й = 1, 2, 3,...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
