14-06-2024
Умножение Карацубы — метод быстрого умножения, который позволяет перемножать два n-значных числа со сложностью вычисления:
Этот подход открыл новое направление в вычислительной математике [1][2].
Содержание |
Проблема оценки количества битовых операций, достаточного для вычисления произведения двух n-значных чисел, или проблема роста функции сложности умножения при является нетривиальной проблемой теории быстрых вычислений.
Перемножение двух n-значных целых чисел обычным школьным методом «в столбик» сводится, по сути, к сложению n n-значных чисел. Поэтому для сложности этого «школьного» или «наивного» метода имеем оценку сверху:
В 1956 году А. Н. Колмогоров сформулировал гипотезу, что нижняя оценка для при любом методе умножения есть также величина порядка (так называемая «гипотеза » Колмогорова). На правдоподобность гипотезы указывал тот факт, что метод умножения «в столбик» известен не менее четырёх тысячелетий (например, этим методом пользовались шумеры), и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден. Однако, в 1960 году Анатолий Карацуба[3][4][5][6] нашёл новый метод умножения двух n-значных чисел с оценкой сложности
и тем самым опроверг «гипотезу ».
Впоследствии метод Карацубы был обобщён до парадигмы «разделяй и властвуй», другими важными примерами которой являются метод двоичного разбиения (англ.), двоичный поиск, метод бисекции и др.
Ниже представлены два варианта (из многих) умножения Карацубы.
Этот вариант основан на формуле
Поскольку , то умножение двух чисел и эквивалентно по сложности выполнения возведению в квадрат.
Пусть есть -значное число, то есть
где .
Будем считать для простоты, что . Представляя в виде
где
и
находим:
Числа и являются -значными. Число может иметь знаков. В этом случае представим его в виде , где есть -значное число, — однозначное число. Тогда
Обозначим — количество операций, достаточное для возведения -значного числа в квадрат по формуле (1). Из (1) следует, что для справедливо неравенство:
где есть абсолютная константа. Действительно, правая часть (1) содержит сумму трёх квадратов -значных чисел, , которые для своего вычисления требуют операций. Все остальные вычисления в правой части (1), а именно умножение на , пять сложений и одно вычитание не более чем -значных чисел требуют по порядку не более операций. Отсюда следует (2). Применяя (2) последовательно к
и принимая во внимание, что
получаем
Тем самым для количества операций, достаточного для возведения -значного числа в квадрат по формуле (1) выполняется оценка:
Если же не является степенью двух, то определяя целое число неравенствами , представим как -значное число, то есть полагаем последние знаков равными нулю:
Все остальные рассуждения остаются в силе и для получается такая же верхняя оценка по порядку величины .
Это непосредственное умножение двух -значных чисел, основанное на формуле
Пусть, как и раньше , , и — два -значных числа. Представляя и в виде
где — -значные числа, находим:
Таким образом, в этом случае формула (1) заменяется формулой (3). Если теперь обозначить символом количество операций, достаточное для умножения двух -значных чисел по формуле (3), то для выполняется неравенство (2), и, следовательно, справедливо неравенство:
Отметим, что представленный выше первый способ умножения можно трактовать как алгоритм вычисления с точностью до знаков функции в некоторой точке .
Если разбивать не на два, а на большее количество слагаемых, то можно получать асимптотически лучшие оценки сложности вычисления произведения (возведения в квадрат).
Метод умножения Шёнхаге — Штрассена имеет меньшую асимптотическую сложность, чем алгоритм Карацубы.
Умножение карацубы с++, умножение карацубы си реализация, умножение карацубы онлайн, умножение карацубы для двоичных чисел.
Файл:A Single Man.jpg, Нур ад-Дин, Файл:The Shield Teamwork.jpg.