Лучшие вопросы
Таймлайн
Чат
Перспективы

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

Из Википедии, свободной энциклопедии

Remove ads

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

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

Remove ads

История

Суммиров вкратце
Перспектива

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

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

Remove ads

Алгоритм

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

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

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

,

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

.

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

.

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

.
Remove ads

Примеры

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

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

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

.

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

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

Remove ads

Примечания

Ссылки

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads