1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 60
Текст из файла (страница 60)
Д о к а з а т е л ь с т в о. В силу теоремы 7.4 и следствия тео. ремы 7.6. С) Снова заметим, что в следствии 4 доминирует вторая величина. Фактически теорема 7.1 допускает такую интерпретацию. Предположим, что р(х) и д(х) — полиномы степени и — 1. Можно вычислить полиномы р и 4 в любых 2п — 1 или более точках, скажем с„с„..., и затем перемножить р(с!) и д(с!), чтобы получить значения рд в тех же точках. По этим значениям можно интерполяцией построить единственный полинам степени 2п — 2.
Он и будет произведением р(х) 4(х) Когда преобразование Фурье применяют к вычислению свертки (илн, что эквивалентно, к умножению полиномов), выбирают с!=о!Г, где 1о — примитивный корень степени 2п из единицы. Далее находят преобразования Фурье полиномов р и о (т. е. вычисляют р и д в точках с„с„...), попарно перемножают результаты этих преобразований (т. е. умножают р (су) на д(с!), чтобы получить значение произведения в точке с!), и вычисляют ро, применяя обратное Гл. е ВыстРОе пРЯОБРАВОВАние ФуРье преобразование. Лемма 7.! гарантирует, что это обращение на самом деле дает формулу для интерполяции.
Иными словами, мы действительно восстанавливаем полипом по его значениям в точках ГБО М1 <Ри-1 УЛ. АЛГОРИТМ ШЕНХАГŠ— ШТРАССЕНА ДЛЯ УМНОЖЕНИЯ ЦЕЛЫХ ЧИСЕЛ Теперь изучим важное приложение теоремы о свертке — алгоритм быстрого битового умножения целых чисел. В равд. 2.6 мы видели, как умножить два и-разрядных двоичных числа за 0(л"е~) шагов, разбивая каждое двоичное число на два (л/2)-разрядных числа. Этот метод можно обобщить, разбивая числа на Ь блоков по 1 разрядов в каждом.
Если рассматривать этн Ь блоков как коэффициенты полн нома, получатся выражения, аналогичные тем, что встречалнсь в (2.4). Чтобы определить коэффициенты произведения полнномов, вычисляем полнномы на некотором подходящем множестве точек, перемножаем найденные значения и ннтерполируем. Выбрав в качестве точек, в которых вычисляются полнномы, примитивные корни нз единицы, можно воспользоваться преобразованием Фурье н теоремой о свертке. Сделав Ь функцией от л н применив рекурсию, можно умножить два и-разрядных двоичных числа за ОВ (п 1ОЕ а 1од 1ой л) шагов. Для простоты ограничимся случаем, когда п — степень числа 2.
В случае когда и не является степенью числа 2, нужно добавить к началам входных векторов подходящее количество нулей, чтобы а стало степенью числа 2 (это увеличивает только мультнпликатнвную постоянную). Кроме того, мы вычислим произведение двухлразрядных двоичных чисел по модулю 2"+1. Чтобы найти точное значение произведения двух и-разрядных двоичных чисел, надо добавить нули к началам н умножать 2л-разрядные числа по модулю 2*" + 1, тем самым увеличивая время опять не более чем в постоянное число раз.
Пусть и н Π— двоичные целые числа между 0 н 2", которые надо перемножить по модулю 2"+1. Заметим, что двоичное представление числа 2" занимает а+! разрядов. Если число и нлн О равно 2", то оно представляется специальным символом — 1, и в этом особом случае умножение выполняется легко: если и=2", то ип по модулю 2"+! получается путем вычисления 2" +1 — О по модулю 2" +1. Допустим, что а=-2", н положим Ь=2А/', если й четно, н Ь =2м — и/е в противном случае. Пусть 1е и/Ь. Заметим, что 1)Ь н 1 делится на Ь без остатка. Первый шаг состоит в разбиении и и О на Ь блоков по ! битов в каждом.
Таким образом, и = и,,2м '1 '+... + и,2'+ и„ О О 2м-1н+ 7.». АлГОРитм шенхАГе — штРАссенА Произведение ио представимо в виде ио = у„»2<»»-з>с+... -(-у,2'+у„ (7.8) где ь-с у = Хиуо,, О(1 <2Ь. )=в (Для !(О или !)Ь вЂ” 1 берем ис=о,=О. Член уаь с равен 0 и включен только для симметрии.) Произведение ио можно вычислить с помощью теоремы о свертке. Перемножение преобразований Фурье требует 2Ь умножений.
Применяя обернутую свертку, можно уменьшить число умножений до Ь. Именно по этой причине мы вычисляем ио по модулю 2'+1. Так как Ы=а, то 2»'= — 1(шод 2в+1). Отсюда в силу (7.8) и леммы 7.6, взяв ио по модулю 2"+1, находим, что но=(соь,2сь "с+... +сос2с-)-соь) (шой2" +!), где сот=ус — у»+с, 0 =с(Ь. Так как произведение двух 1-разрядных двоичных чисел меньше 2*', а у, и уь+,— это суммы, составленные из с+1 и Ь вЂ” (1+1) таких произведений соответственно, то сос=ус — у»+с удовлетворяет неравенствам — (Ь вЂ” 1 — с) 2»с(сос((с+1) 2*'.
Следовательно, сос может принимать не более Ь2сн значений. Если мы сможем вычислить все сос по модулю Ь2", то сможем вычислить ио по модулю 2" +1, сделав 0 (Ь 1оя (Ь2")) дополнительных шагов для сложения Ь экземпляров сос с необходимыми сдвигами. Чтобы вычислить все сос по модулю Ь2*', вычисляем эти исс дважды — по модулю Ь и по модулю 2"+1. Пусть шс — это исс по модулю Ь, а исс — это сос по модулю 2"+1. Так как Ь вЂ” степень числа 2, а число 2м +1 нечетно, то Ь и 2*'+1 взаимно просты. Поэтому сос можно получить из ис, и со; по формуле сос = (2»н + 1) ((со,' — исс) шод Ь) + со, '), учитывая, что сос лежит между — (Ь вЂ” 1 — с) 2сн и (1+1) 2". Вычисление сос по исс и исс требует 0(!+!он Ь) шагов для каждого сос, что дает в целом 0(Ы+Ь 1он Ь), или 0(л) шагов.
Значения исс по модулю Ь вычисляются так: берем ис = и, по модулю Ь и о', =о, по модулю Ь и формируем два (ЗЬ 1ой Ь)-разрядных числа й и б, как показано на рис. 7.7. Произведение йб вычисляется с помощью алгоритма из разд. 2.6 не более чем за 0((ЗЬ )ой Ь)") шагов, т. е. менее чем за 0(л) шагов. Далее, йо= с) Если для взаимно простых р, и р, выполнены сравнения нчыдс (сподрс), ыр=-де (псод рй н О мы<рс рс, то си= р, (рз пкк1 р,) (д,— д, сноб рй+д,. Пусть рс=Ь и р,=2ы+1. Поскольку Ь вЂ” степень числа 2 и »~2ьс, то Ь делит 2'с и, значит, злементом, обратным к 2" +1 по модулю Ь, будет !, гл.
т. выстоон попово»зовднин енвьв и = и,',00...0и»,00...0и, '»...00...0и> о = о»,00...0о,',00...0о»,...00...0и,' рнс. ЧЛ. Изображение составных чисел, используемых при вычислении ы по модулю Ь. В каждом блоке, состоящем из нулей, содержатся 2 1оя Ь нулей. зь — 1 зь-ь =Уу',2<з'оаьы, где у',=Х и',о' ,г Заметим, что у; (2»"зь так что все г="в улъ у, легко восстановить по произведению йд. Тогда шь по модулю Ь можно найти, вычисляя у', — уь+ь по модулю Ь. Вычислив все ьвь по модулю Ь, вычисляем твь по модулю 2ы +1 с помощью обернутой свертки. Дия этого надо взять преобразование Фурье, выполнить попарные умножения и найти обратное преобразование.
Пусть в=2'пь и тп=2»с+1. По теореме 7.5 элементы в и Ь имеют обратные по модулю т, а от — примитивный корень Ь-й степени из единицы. Поэтому отрицательно обернутая свертка векторов [и„чриь..., трь-хиь,[ и [пе, чупы... ..., чрь-' иь т[, где чР=2тйь (чр — корень степейи 2Ь из единицы), равна!(уе — уь)> чр(у — уь+т) ° °" чР» '(уь-ь — у»ь- )1(шод2ы+1), ь-1 где у,=~~ и,и, > для Ы=л~2Ь вЂ” 1.
Значения свь по модулю 2"+1 à — о можно йолучить соответствуквцим сдвигом. Весь алгоритм таков: Алгоритм 7.3. Алгоритм Шенхаге — Штрассена для умножения целых чисел Вход. Два а-разрядных двоичных целых числа и и и, где а=2». Выход. (и+1)-разрядное произведение вв по модулю 2"+1.
Метод. Если л мало, умножьте и на о по модулю 2"+1 вашим любимым алгоритмом. Для большого л положим Ь=2»~т, если й четно, н Ь=2~» — нгз, если й нечетно. Пусть 1=п/Ь. Представим и ь — ! ь-1 и о в виде Д и»2п и о в виде Д п,2п, где иь и оь — целые числа между 0 и 2' — 1 (т. е. числа и~ — это блоки, составленные из ! разрядов числа ьн аналогично о,— блоки из ! разрядов числа о).
1. Вычисляем преобразование Фурье по модулю 2ы +1 векторов [иь>,ри > трь 'иь-дт и [о„чро чрь 'оь- !т где»у=2»пь ичрь берется в качестве примитивного корня Ь-й степени из единицы. 2. Вычисляем по модулю 2" +1 покомпонентное произведение преобразований Фурье, полученных на шаге 1, при помощи алгоритма 7.3, который рекурсивно применяется для вычисления про- 1.6, АлГОРитм швихьге — шт1 ьссгнл изведения каждой пары соответствующих компонент.
(Ситуация, когда одно из чисел равно 2", рассматривается как легкий частный случай.) 3. Вычисляем обратное преобразование Фурье по модулю 2"+1 вектора, равного покомпонентному произведению, полученному на шаге 2. Результатом будет вектор[Го„ фГоь ..., фь ' и1ь ,)г по модулю 2"+1, где и11 обозначает 1-ю компоненту отрицательйо обернутой свертки векторов [и„ и„ ..., иь ,)г и [о„ о„ ... ..., о,Р'.
Вычисляем и11" и11 по модулю 2"+1, умножая ф'1в1 наф-' йо модулю 2"+1. 4. Вычисляем гг1=1о1 пюб Ь следующим образом. (а) Пусть и',=и, по модулю Ь и о', =о1 по модулю Ь для Ж (1(Ь. (б) Построим числа й и 6, выписывая в цепочки числа и', и о, 'и вставляя между ними 2 1оя Ь нулей, т. е.
Ь вЂ” 1 Ь вЂ” 1 й=Х и', 21ььг и1 и б =у, о' 2(310К ьи. 1=о 1=: Ь (в) Вычисляем произведение йй с помощью алгоритма из равд. 2.6. ЯЬ вЂ ! 2Ь вЂ” 1 (г) произведение йб имеет видУу', 21мьги1, где уЬ=У и~ о',, Числа Го1 по модулю Ь можно восстановить по этому произведению, вычисляя Го1 =у', — у,'„по модулю Ь для М!<Ь. 5.
Вычисляем точные значения Го1 по формуле ю,=(2 +Ц((ю; —,) йь)+ю.„ учитывая, что Го! лежит между — (Ь вЂ” 1 — 1) 2" и (1+1) 2". Ь-1 6. Вычисляем Х и11 2и по модулю (2"+1). Это и есть искомый ~0 результат. С) Теорема 7.7. Алгоритм 7.3 вычисляет ио по модулю (2"+1). До к аз а тел ь от в о. По теореме 7.2 шаги 1 — 3 алгоритма 7.3 правильно вычисляют значения Га1 по модулю 2"+1. В качестве упражнения предлагаем доказать, что шаг 4 вычисляет Го1 по модулю Ь, а шаг 6 — Го1 по модулю Ь(2"+1), т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
