Задача перемножения длинных чисел

4. Метод Ш. Винограда

Вышеприведенные методы ориентированы  на реализацию умножения в тех  случаях, когда операнды обладают близкой  разрядностью. Однако существуют методы, ориентированные именно на реализацию умножения в случае операндов различного размера. Одним из таких методов является метод Ш. Винограда. Данный метод ориентирован на умножение в тех случаях, когда один операнд на треть короче другого. Метод Ш. Винограда позволяет осуществить исходное умножение c помощью десяти операций суммирования, четырех умножений с операндами половинного размера по сравнению с исходным коротким множителем и двух сдвигов.

5. Алгоритмы быстрого умножения целых чиселмногократной точности

Приведенный выше алгоритм представляет собой просто первый (r=1) модифицированный алгоритм из бесконечной последовательности алгоритмов

В алгоритме разбиваем сомножители на r частей таким образом, что

, ,

где k=max(m,n)/(r+1).

Нетрудно получить обобщение  вычислительных формул для предлагаемых алгоритмов.

Теорема. Трудоемкость рассмотренного алгоритма умножения можно оценить величиной

,

гдеn - количество цифр в перемножаемых числах.

Известны и другие более  быстрые алгоритмы (и более сложные) умножения целых чисел многократной точности. Из них необходимо отметить класс модулярных алгоритмов и алгоритмов, основанных на быстром преобразовании Фурье. Однако «быстрые алгоритмы» являются быстрыми лишь в случае огромных чисел.

Существует понятие обменной точки, т.е. того значения длины числа (количества цифр в числе), при котором  быстрый алгоритм начинает выигрывать у классического алгоритма. Эти величины обычно значительны и часто зависят от реализации алгоритма на компьютере.

6. Дискретное преобразование Фурье

Изобретение Быстрого преобразования Фурье приписывается Кули (Coolet) и  Таки (Tukey) — 1965 г. На самом деле быстрое преобразование Фурье неоднократно изобреталось до этого, но важность его в полной мере не осознавалась до появления современных компьютеров. Некоторые исследователи приписывают открытие быстрого преобразования Фурье Рунге (Runge) и Кёнигу (Konig) в 1924 г. Наконец, открытие этого метода приписывается ещё Гауссу (Gauss) в 1805 г.

Пусть имеется многочлен  -ой степени:

 

Не теряя общности, можно  считать, что  является степенью 2. Если в действительности не является степенью 2, то мы просто добавим недостающие коэффициенты, положив их равными нулю.

Из теории функций комплексного переменного известно, что комплексных корней -ой степени из единицы существует ровно . Обозначив эти корни через , известно, что . Кроме того, один из этих корней (называемый главным значением корня -ой степени из единицы) таков, что все остальные корни являются его степенями: .

Тогда дискретным преобразованием Фурье (ДПФ) (discreteFouriertransform, DFT) многочлена (или, что то же самое, ДПФ вектора его коэффициентов ) называются значения этого многочлена в точках , т.е. это вектор:

DFT((A(

Аналогично определяется и обратное дискретное преобразование Фурье (InverseDFT). Обратное дискретное преобразование Фурье для вектора значений многочлена — это вектор коэффициентов многочлена :

InverseDFT(

Таким образом, если прямое дискретное преобразование Фурье переходит от коэффициентов многочлена к его значениям в комплексных корнях -ой степени из единицы, то обратное дискретное преобразование Фурье — наоборот, по значениям многочлена восстанавливает коэффициенты многочлена.

Рассмотрим применение дискретного  преобразования Фурье для умножения полиномов. Даны два многочлена и . Посчитав дискретное преобразование Фурье для каждого из них: и — это два вектора-значения многочленов.

При умножении многочленов, в каждой точке их значения просто перемножаются, то есть:

 

Но это означает, что  если перемножить вектора и , просто умножив каждый элемент одного вектора на соответствующий ему элемент другого вектора, то получится не что иное, как дискретное преобразование Фурье от многочлена :

 

Наконец, применяя обратное дискретное преобразование Фурье, получается:

 

гдесправа под произведением двух дискретных преобразований Фурье понимается попарные произведения элементов векторов. Такое произведение, очевидно, требует для вычисления только операций. Таким образом, если научиться вычислять дискретное преобразование Фурье и обратное дискретное преобразование Фурье за время , то и произведение двух полиномов (а, следовательно, и двух длинных чисел) можно найти за ту же асимптотику.

Следует заметить, что, во-первых, два многочлена следует привести к одной степени (просто дополнив коэффициенты одного из них нулями). Во-вторых, в результате произведения двух многочленов степени  получается многочлен степени , поэтому, чтобы результат получился корректным, предварительно нужно удвоить степени каждого многочлена (опять же, дополнив их нулевыми коэффициентами).

7. Быстрое преобразование Фурье

Быстрое преобразование Фурье (fastFouriertransform) — это метод, позволяющий вычислять ДПФ за время . Этот метод основывается на свойствах комплексных корней из единицы (а именно, на том, что степени одних корней дают другие корни).

Основная идея быстрого преобразования Фурье заключается в разделении вектора коэффициентов на два вектора, рекурсивном вычислении дискретного преобразования Фурье для них, и объединении результатов в одно быстрое преобразование Фурье.

Итак, пусть имеется многочлен  степени , где — степень двойки, и :

 

Необходимо разделить его на два многочлена, один — с чётными, а другой — с нечётными коэффициентами:

 

 

Нетрудно убедиться, что:

 

Многочлены  и имеют вдвое меньшую степень, чем многочлен . Если возможно за линейное время по вычисленным и вычислить , то получится искомый алгоритм быстрого преобразования Фурье (т.к. это стандартная схема алгоритма "разделяй и властвуй", и для неё известна асимптотическая оценка ).

Итак, пусть имеются вычисленные вектора и . Необходимо найти выражения для .

Во-первых, вспоминая (1), сразу получаются значения для первой половины коэффициентов:

-1.

Для второй половины коэффициентов  после преобразований также получается простая формула:

=

(Здесь использовалось (1), а также тождествами , .)

Итак, в результате получились формулы для вычисления всего вектора :

1,

 

(эти формулы, т.е. две  формулы вида  и , иногда называют "преобразование бабочки" ("butterflyoperation"))

8. Обратное быстрое преобразование Фурье

Итак, пусть дан вектор — значения многочлена степени в точках . Требуется восстановить коэффициенты многочлена. Эта известная задача называется интерполяцией, для этой задачи есть и общие алгоритмы решения, однако в данном случае будет получен очень простой алгоритм (простой тем, что он практически не отличается от прямого быстрого преобразования Фурье).

Дискретное преобразование Фурье  можно записать, согласно его определению, в матричном виде:

Тогда вектор можно найти, умножив вектор на обратную матрицу к матрице, стоящей слева (которая называется матрицей Вандермонда):

Непосредственной проверкой  можно убедиться в том, что  эта обратная матрица такова:

Таким образом, получаем формулу:

Сравнивая её с формулой для :

 

заметно, что эти две задачи почти ничем не отличаются, поэтому коэффициенты можно находить таким же алгоритмом "разделяй и властвуй", как и прямое БПФ, только вместо везде надо использовать , а каждый элемент результата надо разделить на .

Таким образом, вычисление обратного дискретного преобразования Фурье почти не отличается от вычисления прямого дискретного преобразования Фурье, и его также можно выполнять за время .

3. Анализ алгоритмов перемножения

В данном разделе анализируются  алгоритмы перемножения с точки  зрения их эффективности при работе с разными числами (затраты временных ресурсов, памяти)

Область вычислительной математики, которая называется быстрые алгоритмы, появилась в 1960 году.

Под алгоритмом  понимается правило или способ вычисления, не формализуя это понятие. Считать, что числа записаны в двоичной системе счисления, знаки которой 0 и 1 называются битами.

Определение 1.Запись знаков 0, 1 , плюс, минус, скобка; сложение, вычитание и умножение двух битов называется одной элементарной или битовой операцией.

Быстрые алгоритмы — это  область вычислительной математики, которая изучает алгоритмы вычисления заданной функции с заданной точностью  с использованием как можно меньшего числа битовых операций. Тем самым, алгоритмы, которые можно назвать  быстрыми, являются реальными алгоритмами. Такие алгоритмы, реализованные на ЭВМ в программном (а иногда и аппаратном) обеспечении позволяют существенно увеличить производительность работы компьютера, а иногда и решить задачи, размер которых не позволял найти решение путём применения обычных методов вычисления. Вопрос о размере задачи, которую можно решить за некоторое время с помощью данного компьютера, приводит  к понятию сложности вычисления.

В дальнейшем, если не оговаривается  иначе, под сложностью вычисления подразумевается битовая сложность.

Первые постановки задач  о сложности вычислений (1956 г.) принадлежат А. Н. Колмогорову, который в то же время подчёркивал, что «цикл моих работ по теории информации был создан под большим влиянием публикаций Норберта Винера и Клода Шеннона».

Прежде чем ввести понятие  сложности вычисления, необходимо определить, что значит вычислить функцию в заданной точке. Рассмотрим наиболее простой пример вычисления вещественной функции y = f(x) вещественного переменного x, a ≤ x ≤ b. Пусть f(x) на (a,b) удовлетворяет условию Липшица порядка α, 0 < α <1, так что при x1, x2 ∊ (a,b):

|f(x1) – f(x2)| ≤ |x1 – x2|α. 

Пусть n — натуральное  число.

Определение 2. Вычислить функцию y = f(x) в точке x = x0 ∊ (a,b) с точностью до n знаков, значит найти число A, что

|f(x0) – A| ≤ 2–n.

Определение 3. Количество битовых операций, достаточное для вычисления функции f(x) в точке x = x0 с точностью до n знаков посредством данного алгоритма, называется сложностью вычисления f(x) в точке x = x0.

Таким образом, сложность  вычисления f(x) в точке x = x0 есть функция n; а также f(x) и x = x0. Эту функцию  обозначают символом

Sf(n) = Sf,x0(n).

Ясно, что Sf зависит также  от алгоритма вычисления и при  разных алгоритмах будет разной. Сложность вычисления непосредственно связана со временем, затрачиваемым компьютером на это вычисление и потому иногда в литературе обозначается «временной» функцией T(n).

Вопрос о поведении Sf(n) при n → ∞ для класса функций  или конкретной функции f, был впервые поставлен А. Н. Колмогоровым около 1956 года. Поскольку при вычислениях в первую очередь используются четыре арифметических действия: сложение, вычитание, умножение и деление, то прежде всего нужно знать количество битовых операций, достаточное для выполнения этих действий. Из определений 2 и 3 следует, что числа x0 и A можно представить в виде целой части и n двоичных знаков после запятой, т.е.

A = [A] + 0,ν1ν2ν3 ... νn,

x0 = [x0] + 0,μ1μ2μ3 ... μn,

где νj, μj = 0 или 1, j = 1, 2, ... , n.

Так как целые части [A], [x0] — фиксированные величины, а n → ∞, то действия производятся по существу с n-значными числами. Отсюда прежде всего  возникает вопрос о сложности  вычисления суммы, разности, произведения и частного двух n-значных чисел a и b.

Функция сложности умножения  получила специальное обозначение M(n).

Перемножая два n-значных  числа обычным школьным способом «в столбик», при этом фактически складывается n n-значных чисел. Так что для сложности этого «школьного» или «обычного» метода мы имеем оценку сверху M(n) = O(n2).

В 1956 г. А. Н. Колмогоров высказал гипотезу, что нижняя оценка M(n) при  любом методе умножения есть также  величина порядка n2 (так называемая «гипотеза n2 Колмогорова»). На правдоподобность «гипотезы n2» указывал тот факт, что метод умножения «в столбик» известен не менее 4-х тысячелетий (например, этим методом пользовались шумеры), и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден.

В 1960 А. А. Карацубанашёл новый метод умножения двух n-значных чисел с оценкой сложности

M(n) = O(nlog23),   log23 = 1,5849... ,

и тем самым опроверг «гипотезу n2». Этот метод впоследствии был  назван «DivideandConquer» («Разделяй и властвуй»); другие, используемые в настоящее время названия этого метода — «BinarySplitting», «Принцип Дихотомии» и т. п.

С момента появления «DivideandConquer»  начала развиваться теория быстрых  вычислений. Исследования с целью  поиска алгоритма умножения со сложностью, близкой к оптимальной, были продолжены рядом авторов (среди них были Тоом, Кук, Шёнхаге), и в 1971 г. Шёнхаге и Штрассен построили алгоритм с наилучшей на настоящее время оценкой для M(n),

M(n) = O(n log n loglog n).

При построении этого алгоритма  кроме "DivideandConquer" они использовали идею выполнения арифметических действий по модулю чисел Ферма 22n+ 1, а также быстрое преобразование Фурье.

Каждый из приведенных  в данной курсовой работе методов  умножения использует различные  принципы; так, в основе квадратичного  алгоритма лежит простой поразрядный перебор с перемножением; в основе метода Карацубы – метод декомпозиции; третий же способ, используя ту же самую парадигму декомпозиции для быстрого вычисления ДПФ, ускоряет умножение путем перевода многочленов из коэффициентного представления в вектор значений в точках.

В результате теоретического анализа были выведены функции трудоемкости для алгоритмов, выражающие зависимость количества базовых операций от длины входа. Если решать, что время решения задачи прямо пропорционально количеству затрачиваемых базовых операций, то  эмпирическим путем найдя среднее время на базовую операцию можно построить функции временных прогнозов. Функцию временного прогноза для алгоритма перемножения «в столбик» можно увидеть на рисунке 3.1, функцию временного прогноза для алгоритма быстрого преобразования Фурье можно увидеть на рисунке 3.2.