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

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

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

.

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

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

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

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

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

Пусть есть два -значных двоичных числа и , где  — чётное число и . То есть, и получены из старших разрядов и , а и  — из младших.

В таких обозначениях произведение чисел и может быть переписано как

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

Время работы полученной процедуры может быть оценено по основной теореме о рекуррентных оценках:

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

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

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

Рассмотрим задачу умножения двух восьмизначных (в десятичной записи) чисел: и .

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

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

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

Для их умножения применяется тот же алгоритм: представляется как и так далее.

На практике алгоритм становится эффективнее обычного умножения при умножении чисел длиной порядка сотен двоичных (десятков десятичных) разрядов, на числах меньшей длины алгоритм не даёт существенного преимущества из-за большего, чем в наивном алгоритме, числа требуемых сложений, вычитаний и сдвигов.

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

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

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

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