Интернет магазин китайских планшетных компьютеров

Компьютеры - Умножение Карацубы

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

Этот подход открыл новое направление в вычислительной математике .

История

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

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

M = O.

В 1956 году А. Н. Колмогоров сформулировал гипотезу, что нижняя оценка для M при любом методе умножения есть также величина порядка n. На правдоподобность гипотезы n указывал тот факт, что метод умножения «в столбик» известен не менее четырёх тысячелетий, и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден. Однако, в 1960 году Анатолий Карацуба нашёл новый метод умножения двух n-значных чисел с оценкой сложности

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

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

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