Карацуба

Постановка задачи

Есть два многочлена $A$ и $B$ степени $2^n$. Необходимо найти их произведение.

Решение в лоб, используя идею разделяй и властвуй

Представим $A = x^\frac{n}{2} \cdot P_A + Q_A$ и $B = x^\frac{n}{2} P_B + Q_B$. Тогда $AB = (x^\frac{n}{2} P_A + Q_A)(x^\frac{n}{2} \cdot P_B + Q_B)=x^n P_A P_B + x^\frac{n}{2}(P_A Q_B + P_B Q_A) + Q_A Q_B$.

Здесь все действия делаются за линию, кроме умножения многочленов. Чтобы перемножить многочлены степени $2^\frac{n}{2}$ запустим наш алгоритм рекурсивно. Будет 4 запуска от многочленов в два раза меньшей длины.

Время работы такого алгоритма получится $T(n) = 4T(\frac{n}{2}) + O(2^n)$, что равняется $O(2^{2n})$ и ничем не лучше обычного перемножения в два цикла.

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

Оказывается в предыдущем алгоритме можно обойтись всего тремя рекурсивными запусками. Действительно $P_A Q_B + P_B Q_A = (P_A + Q_A)(P_B + Q_B) - P_A P_B - Q_A Q_B$. Первые два рекурсивных запуска мы тратим на вычисление $P_A P_B$ и $Q_A Q_B$, после чего для получения $P_A Q_B + P_B Q_A$ достаточно вычислить (P_A + Q_A)(P_B + Q_B), что можно сделать за одно умножение вместо двух.

Время работы данного алгоритма будет выражаться как $T(n) = 3T(\frac{n}{2}) + O(2^n)$, что равняется $2^{n\log_2(3)}$

---

Автор конспекта: Станислав Донской

По всем вопросам пишите в telegram @stasana