Умножение Карацубы

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

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

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

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

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

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

Перемножение двух n-значных целых чисел обычным школьным методом «в столбик» сводится, по сути, к сложению n n-значных чисел. Поэтому для сложности этого «школьного» или «наивного» метода имеем оценку сверху:

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

и тем самым опроверг «гипотезу ».

Впоследствии метод Карацубы был обобщён до парадигмы «разделяй и властвуй», другими важными примерами которой являются метод двоичного разбиения (англ.), двоичный поиск, метод бисекции и др.

Ниже представлены два варианта (из многих) умножения Карацубы.

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

Первый вариант[править | править вики-текст]

Этот вариант основан на формуле

Поскольку , то умножение двух чисел и эквивалентно по сложности выполнения возведению в квадрат.

Пусть есть -значное число, то есть

где .

Будем считать для простоты, что . Представляя в виде

где

и

находим:

Числа и являются -значными. Число может иметь знаков. В этом случае представим его в виде , где есть -значное число, — однозначное число. Тогда

Обозначим — количество операций, достаточное для возведения -значного числа в квадрат по формуле (1). Из (1) следует, что для справедливо неравенство:

где есть абсолютная константа. Действительно, правая часть (1) содержит сумму трёх квадратов -значных чисел, , которые для своего вычисления требуют операций. Все остальные вычисления в правой части (1), а именно умножение на , пять сложений и одно вычитание не более чем -значных чисел требуют по порядку не более операций. Отсюда следует (2). Применяя (2) последовательно к

и принимая во внимание, что

получаем

Тем самым для количества операций, достаточного для возведения -значного числа в квадрат по формуле (1) выполняется оценка:

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

Все остальные рассуждения остаются в силе, и для получается такая же верхняя оценка по порядку величины .

Второй вариант[править | править вики-текст]

Это непосредственное умножение двух -значных чисел, основанное на формуле

Пусть, как и раньше , , и — два -значных числа. Представляя и в виде

где -значные числа, находим:

Таким образом, в этом случае формула (1) заменяется формулой (3). Если теперь обозначить символом количество операций, достаточное для умножения двух -значных чисел по формуле (3), то для выполняется неравенство (2), и, следовательно, справедливо неравенство:

Замечания[править | править вики-текст]

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

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

Метод умножения Шёнхаге — Штрассена имеет меньшую асимптотическую сложность, чем алгоритм Карацубы.

См. также[править | править вики-текст]

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

  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.

Ссылки[править | править вики-текст]