Быстрое умножение

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

Андрей Колмогоров и несколько других пионеров компьютер саенса выдвинули «гипотезу $n^2$» — что . Основания на то были — шумеры научились умножать в «в столбик» (сложение $n$ $n$-значиных чисел) как минимум четыре тысячи лет назад, и за это время никто ничего быстрее не придумал.

Колмогоров уже собрал научный семинар с повесткой дня «давайте это всё уже докажем», на котором его аспирант. Аспиранта звали Анатолий Карацуба.

Алгоритм Карацубы имеет довольно значимое место в истории науки.

{\displaystyle M(n)=O(n^{2}).} M(n)=O(n^{2}). У Колмогорова была гипотеза, что нижняя оценка для {\displaystyle M(n)} M(n) при любом методе умножения есть также величина порядка {\displaystyle n^{2}} n^{2}. На правдоподобность «гипотезы {\displaystyle n^{2}} n^{2}» указывал тот факт, что метод умножения «в столбик» известен не менее четырёх тысячелетий (например, этим методом пользовались шумеры), и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден. Однако, в 1960 году Анатолий Карацуба[4][5][6][7] нашёл новый метод умножения двух n-значных чисел с оценкой сложности {\displaystyle M(n)=O(n^{\log {2}3})} M(n)=O(n^{{\log {2}3}}) и тем самым опроверг «гипотезу {\displaystyle n^{2}} n^{2}».

(Быстрое преобразование Фурье тогда уже изобрели, но к умножению чисел применять ещё не додумались.)

Можно представить себе какого-то грозного японца.

Мастер-теорема

Алгоритм Карацубы основывается на парадигме «разделяй-и-властвуй». Чтобы понять, почему его асимптотика именно такая, нам понадобится более мощная теорема, которая говорит об асимптотике большого класса «разделяек».

Мастер-теорема. Пусть имеется рекуррента:

$$ T(n) = \begin{cases} a T(\frac{n}{b}) + \Theta(n^c), & n > n_0 \\ \Theta(1), & n \leq n_0 \end{cases} $$

Тогда:

  • A. Если $c > \log_b a$, то $T(n) = \Theta(n^c)$.
  • B. Если $c = \log_b a$, то $T(n) = \Theta(n^c \log n)$.
  • C. Если $c < \log_b a$, то $T(n) = \Theta(n^{\log_b a})$.


Доказательство. Рассмотрим «дерево рекурсии» этого соотношения. В нём будет $log_b n$ уровней. На $k$-том уровне будет $a^k$ вершин, каждая из которых будет стоить $(\frac{n}{b^k})^c$ операций. Просуммируем значения во всех вершинах по всем уровням:

$$ T(n) = \sum_{k=0}^{\log_b n} a^k (\frac{n}{b^k})^c = n^c \sum_{k=0}^{\log_b n} (\frac{a}{b^c})^k $$
  • A. Если $c > \log_b a$, то $\sum (\frac{a}{b^с})^k$ это сумма убывающей геометрической прогрессии, которая не зависит от $n$ и просто равна какой-то константе. Значит, $T(n) = \Theta(n^c)$.
  • B. Если $c = \log_b a$, то $$\sum_{k=0}^{\log_b n} (\frac{a}{b^c})^k = \sum_{k=0}^{\log_b n} 1^k = \Theta(n^c \log_b n)$$
  • C. Если $c < \log_b a$, то так как сумма прогрессии асимптотически эквивалентна своему старшему элементу,
$$ n^c \sum_{k=0}^{\log_b n} (\frac{a}{b^c})^k = \Theta(n^c (\frac{a}{b^c})^{\log_b n}) = \Theta(n^c \cdot \frac{a^{\log_b n}}{n^c}) = \Theta(a^{\log_b n}) = \Theta(n^{\log_b a}) $$

Для более точных оценок асимптотики «мерджа» теорема ничего не говорит работает. Например, если мердж занимает $O(n)$

Алгоритм Карацубы

Алгоритм Карацубы сводит задачу умножения двух чисел длины $n$ к возведению $n$-значного числа в квадрат.

Зачем нам возведение в квадрат, если мы хотим умножать числа? Оказывается, это эквивалентные задачи.

Развитие идеи

То же самое можно применить матрицам.

Чемпионат идёт на пятые знаки после запятой. Возможность или невозможность умножения чисел за $O(n^{1+\epsilon})$ для произвольного $\epsilon$ ещё никто не доказал.