Конспект: Карацуба, Штрассен и цена умножения

Понятия

Тождество Карацубы - способ получить средний член произведения одним умножением вместо двух. Штрассен - семь произведений блоков вместо восьми при умножении матриц. Тоом-Кук - обобщение: k частей и 2k − 1 умножений вместо k².

Что унести

ЧИСЛА (разрез пополам, X = X₁·Bᵐ + X₀)

наивно:    X·Y = X₁Y₁·B²ᵐ + (X₁Y₀ + X₀Y₁)·Bᵐ + X₀Y₀     4·T(n/2) + n  →  Θ(n²)

Карацуба:  z₂ = X₁·Y₁
           z₀ = X₀·Y₀
           z₁ = (X₁+X₀)(Y₁+Y₀) − z₂ − z₀                3·T(n/2) + n  →  Θ(n^1.585)

МАТРИЦЫ (разрез на четыре блока)

наивно:    восемь произведений блоков                    8·T(n/2) + n² →  Θ(n³)
Штрассен:  семь произведений сумм блоков                 7·T(n/2) + n² →  Θ(n^2.807)

Почему лестница работает: разрезав число на k частей, получаем многочлен степени k−1; произведение двух таких - многочлен степени 2k−2, и он восстанавливается по 2k−1 значениям. Значит достаточно 2k−1 умножений в точках.

Число подзадач стоит в ПОКАЗАТЕЛЕ. Поэтому убрать одно умножение - значит изменить порядок роста, а ускорить объединение - только константу. На n = 2^k цифрах: Карацуба делает ровно 3^k умножений против 4^k, отношение (4/3)^k (на тысяче цифр - в восемнадцать раз).

Плата у обоих алгоритмов одинаковая по смыслу: больше сложений и вычитаний, память под промежуточные величины, хуже численная устойчивость (элементы ответа собираются из величин другого масштаба и знака). Отсюда обязательные ПОРОГИ: до сотни слов - столбик, дальше Карацуба, дальше Тоом-Кук, на очень больших - БПФ. В GMP это видно прямо в именах функций.

Тихие ошибки: писать Карацубу без порога (медленнее столбика); забыть, что X₁ + X₀ длиннее половины на разряд; ждать от Штрассена ускорения на матрицах в сотню элементов; считать 2.807 доказанным показателем умножения матриц (это оценка сверху, сегодня опущена до ≈2.37, а снизу известно только n²).

Куда это ведёт

Следующая глава - ближайшая пара точек: там деление пополам работает не с числами, а с геометрией, и вся сложность окажется в объединении - в узкой полосе вокруг разреза.