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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Умножение Карацубы — метод быстрого умножения, позволяющий перемножать два -значных числа с битовой вычислительной сложностью .

Изобретён Анатолием Карацубой в 1960 году. Является исторически первым алгоритмом умножения, превосходящим тривиальный по асимптотической сложности[1][2][3][4].

В 1960 году Колмогоров проводил семинар, посвящённый математическим задачам кибернетики. Одной из рассматриваемых на семинаре задач стало умножение двух -разрядных целых чисел. Основным известным методом умножения в то время было умножение «в столбик», которое при алгоритмической реализации требовало элементарных операций (сложений или умножений одноразрядных чисел). Колмогоров выдвинул гипотезу, что умножение «в столбик» является оптимальным алгоритмом умножения двух чисел в том смысле, что время работы любого метода умножения не меньше по порядку величины. На правдоподобность «гипотезы » указывало то, что метод умножения «в столбик» известен не менее четырёх тысячелетий, и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден. Однако, через неделю 23-летний Карацуба[5][6][7][8] предложил новый метод умножения двух -значных чисел с оценкой времени работы и тем самым опроверг «гипотезу ».

Метод Карацубы относится к алгоритмам вида «разделяй и властвуй», наравне с такими алгоритмами как двоичный поиск, быстрая сортировка и др. Формулы рекурсивного сведения, используемые в методе Карацубы, были известны ещё Чарльзу Бэббиджу, который, однако, не обратил внимания на возможность использования лишь трёх рекурсивных умножений вместо четырёх[9].

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

Два -битовых числа можно представить в виде , , где и .

Умножение на (битовый сдвиг) и сложение делаются за постоянное время . Поэтому задача умножения сводится к вычислению коэффициентов многочлена . Используя тождество:

,

этот многочлен можно представить в виде:

.

В последнем выражении участвуют три произведения -значных чисел. Если вычислять каждое из них по той же схеме, получится алгоритм с рекуррентной оценкой времени работы:

.

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

.

Для умножения двух восьмизначных (в десятичной записи) чисел и каждое из них представляется в виде суммы двух чисел вдвое меньшей разрядности, одно из которых взято со сдвигом[10]:

Раскрывая скобки, произведение и можно переписать как:

Карацуба нашёл, что вместо четырёх умножений вдвое более коротких чисел, можно делать лишь три: , и , в результате чего выражение преобразуется к виду:

.

Для умножения укороченных вдвое чисел применяется тот же алгоритм: представляется как и так далее. На практике для достаточно коротких чисел применяется уже обычное умножение как более эффективное.

Подход работает в любой системе счисления, в том числе и в двоичной, используемой вычислительной техникой. Например, вычисление произведения двух 4096-битных двоичных чисел методом Карацубы требует элементарных однобитовых умножений вместо при умножении наивным методом.

Примечания

[править | править код]
  1. На практике алгоритм становится эффективнее обычного умножения при умножении чисел длиной порядка сотен двоичных (десятков десятичных) разрядов, на числах меньшей длины алгоритм не даёт существенного преимущества из-за большего, чем в наивном алгоритме, числа требуемых сложений, вычитаний и сдвигов.
  2. С. А. Гриценко, Е. А. Карацуба, М. А. Королёв, И. С. Резвякова, Д. И. Толев, М. Е. Чанга. Научные достижения Анатолия Алексеевича Карацубы // Математика и информатика, 1, К 75-летию со дня рождения Анатолия Алексеевича Карацубы, Совр. пробл. матем., 16, МИАН, М., 2012, 7–30.
  3. Карацуба Е. А. Быстрые алгоритмы и метод БВЕ Архивная копия от 4 ноября 2012 на Wayback Machine, 2008.
  4. Алексеев В. Б. От метода Карацубы для быстрого умножения чисел к быстрым алгоритмам для дискретных функций // Тр. МИАН. — 1997. — Т. 218. — С. 20–27.
  5. Карацуба А., Офман Ю. Умножение многозначных чисел на автоматах // Доклады Академии Наук СССР. — 1962. — Т. 145, № 2.
  6. Karacuba A. Berechnungen und die Kompliziertheit von Beziehungen (нем.) // Elektronische Informationsverarbeitung und Kybernetik. — 1975. — Bd. 11.
  7. Карацуба А. А. Сложность вычислений // Тр. МИАН. — 1995. — Т. 211. — С. 186–202.
  8. Кнут Д. Искусство программирования. — 3-е изд. — М.: Вильямс, 2007. — Т. 2. Получисленные алгоритмы. — 832 с. — ISBN 0-201-89684-2.
  9. А. Шень. Gauss multiplication trick? // Математическое Просвещение. — 2019. — Т. 24. Архивировано 21 января 2022 года.
  10. Сдвигом называется умножение или деление числа на целую степень основания системы счисления, «дописывание нулей».