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

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

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

История

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

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

Алгоритм

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

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

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

,

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

.

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

.

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

.

Примеры

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

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

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

.

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

Подход работает в любой системе счисления, в том числе и в двоичной, используемой вычислительной техникой. Например, вычисление произведения двух 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. А. Шень . // Математическое Просвещение . — 2019. — Т. 24 . 21 января 2022 года.
  10. Сдвигом называется умножение или деление числа на целую степень основания системы счисления, «дописывание нулей».

Ссылки


Источник —

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