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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Умножение Карацубы»)
Перейти к навигации Перейти к поиску

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

.

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

История[править | править код]

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

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

Описание метода[править | править код]

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

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

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

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

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

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

Примеры[править | править код]

Графическая иллюстрация другого примера: умножения 1234 на 567 по алгоритму Карацубы. Сначала выполняются нижние шаги , а потом их результаты подставляются в верхнюю схему.

Для удобства изложения будем использовать десятичную систему, то есть аргументы многочлена вида вместо . Цветовая разметка цифр не связана с предыдущим разделом, а обозначет лишь, из какого числа вычленяется та или иная часть.

Вычислим :

  • заметим, что и вычислии :
    • заметим, что и вычислим
    • вычислим
    • вычислим
    • складывая результаты, получим, что
  • вычислим как :
    • заметим, что и вычислим
    • вычислим
    • вычислим
    • складывая результаты, получим, что
  • вычислим как :
    • заметим, что и вычислим
    • вычислим
    • вычислим
    • складывая результаты, получим, что
  • складывая результаты, получим, что

Примечания[править | править код]

  1. На практике алгоритм становится эффективнее обычного умножения при умножении чисел длиной порядка сотен двоичных (десятков десятичных) разрядов, на числах меньшей длины алгоритм не даёт существенного преимущества из-за большего, чем в наивном алгоритме, числа требуемых сложений, вычитаний и сдвигов.
  2. С. А. Гриценко, Е. А. Карацуба, М. А. Королёв, И. С. Резвякова, Д. И. Толев, М. Е. Чанга. Научные достижения Анатолия Алексеевича Карацубы // Математика и информатика, 1, К 75-летию со дня рождения Анатолия Алексеевича Карацубы, Совр. пробл. матем., 16, МИАН, М., 2012, 7–30.
  3. Карацуба Е. А. Быстрые алгоритмы и метод БВЕ, 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.

Ссылки[править | править код]