Описание тега karatsuba
Асимптотически быстрый алгоритм умножения больших целых чисел. Понимание этого алгоритма и его реализаций.
Алгоритм Карацубы требует O(n^log₂3) операций однозначного умножения для умножения пары n-значных чисел и, следовательно, асимптотически быстрее, чем обычный алгоритм умножения O(n²).
Он был предложен Анатолием Карацубой в статье, опубликованной в Известиях АН СССР в 1962 году.
Связанный тег - strassen, который охватывает как алгоритм умножения Шёнхаге – Штрассена, так и алгоритм умножения матриц Штрассена.
Полезные ссылки
- Алгоритм Карацубы в Википедии
- А.А. Карацуба "Сложность вычислений " (опубликовано в 1995 г.)
- Черновик главы об умножении длинных целых чисел Арно Эйгенвиллига и Курта Мельхорна из книги "Алгоритмы отключены"