Лучшие вопросы
Таймлайн
Чат
Перспективы
Алгоритм Карацубы
Из Википедии, свободной энциклопедии
Remove ads
Умножение Карацубы — метод быстрого умножения, позволяющий перемножать два -значных числа с битовой вычислительной сложностью .
Изобретён Анатолием Карацубой в 1960 году. Является исторически первым алгоритмом умножения, превосходящим тривиальный по асимптотической сложности[1][2][3][4].
Remove ads
История
Суммиров вкратце
Перспектива
В 1960 году Колмогоров проводил семинар, посвящённый математическим задачам кибернетики. Одной из рассматриваемых на семинаре задач стало умножение двух -разрядных целых чисел. Основным известным методом умножения в то время было умножение «в столбик», которое при алгоритмической реализации требовало элементарных операций (сложений или умножений одноразрядных чисел). Колмогоров выдвинул гипотезу, что умножение «в столбик» является оптимальным алгоритмом умножения двух чисел в том смысле, что время работы любого метода умножения не меньше по порядку величины. На правдоподобность «гипотезы » указывало то, что метод умножения «в столбик» известен не менее четырёх тысячелетий, и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден. Однако, через неделю 23-летний Карацуба[5][6][7][8] предложил новый метод умножения двух -значных чисел с оценкой времени работы и тем самым опроверг «гипотезу ».
Метод Карацубы относится к алгоритмам вида «разделяй и властвуй», наравне с такими алгоритмами как двоичный поиск, быстрая сортировка и др. Формулы рекурсивного сведения, используемые в методе Карацубы, были известны ещё Чарльзу Бэббиджу, который, однако, не обратил внимания на возможность использования лишь трёх рекурсивных умножений вместо четырёх[9].
Remove ads
Алгоритм
Суммиров вкратце
Перспектива

Два -битовых числа можно представить в виде , , где и .
Умножение на (битовый сдвиг) и сложение делаются за постоянное время . Поэтому задача умножения сводится к вычислению коэффициентов многочлена . Используя тождество:
- ,
этот многочлен можно представить в виде:
- .
В последнем выражении участвуют три произведения -значных чисел. Если вычислять каждое из них по той же схеме, получится алгоритм с рекуррентной оценкой времени работы:
- .
Для сравнения, аналогичный алгоритм, производящий отдельно все четыре умножения , , , , требовал бы обычного времени:
- .
Remove ads
Примеры
Для умножения двух восьмизначных (в десятичной записи) чисел и каждое из них представляется в виде суммы двух чисел вдвое меньшей разрядности, одно из которых взято со сдвигом[10]:
Раскрывая скобки, произведение и можно переписать как:
Карацуба нашёл, что вместо четырёх умножений вдвое более коротких чисел, можно делать лишь три: , и , в результате чего выражение преобразуется к виду:
- .
Для умножения укороченных вдвое чисел применяется тот же алгоритм: представляется как и так далее. На практике для достаточно коротких чисел применяется уже обычное умножение как более эффективное.
Подход работает в любой системе счисления, в том числе и в двоичной, используемой вычислительной техникой. Например, вычисление произведения двух 4096-битных двоичных чисел методом Карацубы требует элементарных однобитовых умножений вместо при умножении наивным методом.
Remove ads
Примечания
Ссылки
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads