Электромонтаж Ремонт и отделка Укладка напольных покрытий, теплые полы Тепловодоснабжение

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

01.10.2022

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

T ( n ) = O ( n log 2 ⁡ 3 ) , log 2 ⁡ 3 = 1,584 9 … {displaystyle T(n)=O(n^{log _{2}3}),quad log _{2}3=1{,}5849ldots } .

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

История

В 1960 году Андрей Колмогоров проводил семинар, посвящённый математическим задачам кибернетики. Одной из рассматриваемых на семинаре задач стало умножение двух n {displaystyle n} -разрядных целых чисел. Основным известным методом умножения в то время было умножение «в столбик», которое при алгоритмической реализации требовало O ( n 2 ) {displaystyle O(n^{2})} элементарных операций (сложений или умножений одноразрядных чисел). Колмогоров выдвинул гипотезу, что умножение «в столбик» является оптимальным алгоритмом умножения двух чисел в том смысле, что время работы любого метода умножения не меньше n 2 {displaystyle n^{2}} по порядку величины. На правдоподобность «гипотезы n 2 {displaystyle n^{2}} » указывало то, что метод умножения «в столбик» известен не менее четырёх тысячелетий, и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден. Однако, через неделю 23-летний Анатолий Карацуба предложил новый метод умножения двух n {displaystyle n} -значных чисел с оценкой времени работы O ( n log 2 ⁡ 3 ) {displaystyle O(n^{log _{2}3})} и тем самым опроверг «гипотезу n 2 {displaystyle n^{2}} ».

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

Описание метода

Два n {displaystyle n} -битовых числа можно представить в виде a x + b {displaystyle ax+b} , c x + d {displaystyle cx+d} , где x = 2 ⌈ n / 2 ⌉ {displaystyle x=2^{lceil {n/2} ceil }} ; a , b , c , d < 2 ⌈ n / 2 ⌉ {displaystyle a,b,c,d<2^{lceil {n/2} ceil }} .

Умножение на 2 ⌈ n / 2 ⌉ {displaystyle 2^{lceil {n/2} ceil }} (битовый сдвиг) и сложение делаются за постоянное время O ( 1 ) {displaystyle O(1)} . Поэтому задача умножения сводится к вычислению коэффициентов многочлена ( a x + b ) ( c x + d ) {displaystyle (ax+b)(cx+d)} . Используя тождество

( a + b ) ( c + d ) = a c + ( a d + b c ) + b d   , {displaystyle {color {green}(a+b)(c+d)}={color {red}ac}+{color {darkorange}(ad+bc)}+{color {blue}bd} ,}

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

( a x + b ) ( c x + d ) = a c x 2 + ( a d + b c ) x + b d = {displaystyle (ax+b)(cx+d)={color {red}ac}x^{2}+{color {darkorange}(ad+bc)}x+{color {blue}bd}=} = a c x 2 + ( ( a + b ) ( c + d ) − a c − b d ) x + b d   . {displaystyle ={color {red}ac}x^{2}+{color {darkorange}{Big (}}{{color {green}(a+b)(c+d)}-{color {red}ac}-{color {blue}bd}}{color {darkorange}{Big )}}x+{color {blue}bd} .}

В последнем выражении участвуют три произведения ( ⌈ n 2 ⌉ + 1 ) {displaystyle left({leftlceil {frac {n}{2}} ight ceil +1} ight)} -значных чисел. Если вычислять каждое из них по той же схеме, получится алгоритм с рекуррентной оценкой времени работы

T ( n ) = 3 T ( n 2 ) + O ( n ) = O ( n log 2 ⁡ 3 )   . {displaystyle T(n)=3Tleft({frac {n}{2}} ight)+O(n)=O(n^{log _{2}3}) .}

Для сравнения, аналогичный алгоритм, производящий отдельно все четыре умножения a c {displaystyle ac} , a d {displaystyle ad} , b c {displaystyle bc} , b d {displaystyle bd} , требовал бы обычного времени

T ( n ) = 4 T ( n 2 ) + O ( n ) = O ( n log 2 ⁡ 4 ) = O ( n 2 )   . {displaystyle T(n)=4Tleft({frac {n}{2}} ight)+O(n)=O(n^{log _{2}4})=O(n^{2}) .}

Примеры

Для удобства изложения будем использовать десятичную систему, то есть аргументы многочлена вида x = 10 k {displaystyle x=10^{k}} вместо x = 2 k {displaystyle x=2^{k}} . Цветовая разметка цифр не связана с предыдущим разделом, а обозначает лишь, из какого числа вычленяется та или иная часть.

Вычислим 1213 ⋅ 2311 {displaystyle {color {red}1213}cdot {color {blue}2311}} :

  • заметим, что 12 + 13 = 25 ,   23 + 11 = 34 {displaystyle {color {red}12}+{color {red}13}=25, {color {blue}23}+{color {blue}11}=34} и вычислим 25 ⋅ 34 {displaystyle {color {darkorange}25}cdot {color {magenta}34}} :
    • заметим, что 2 + 5 = 7 ,   3 + 4 = 7 {displaystyle {color {darkorange}2}+{color {darkorange}5}=7, {color {magenta}3}+{color {magenta}4}=7} и вычислим 7 ⋅ 7 = 49 {displaystyle 7cdot 7=49}
    • вычислим 2 ⋅ 3 = 6 {displaystyle {color {darkorange}2}cdot {color {magenta}3}=6}
    • вычислим 5 ⋅ 4 = 20 {displaystyle {color {darkorange}5}cdot {color {magenta}4}=20}
    • складывая результаты, получим, что 25 ⋅ 34 = 6 ⋅ 10 2 + ( 49 − 6 − 20 ) ⋅ 10 + 20 = 850 {displaystyle {color {darkorange}25}cdot {color {magenta}34}=6cdot 10^{2}+(49-6-20)cdot 10+20=850}
  • вычислим 12 ⋅ 23 {displaystyle {color {red}12}cdot {color {blue}23}} как 12 ⋅ 23 {displaystyle {color {darkorange}12}cdot {color {magenta}23}} :
    • заметим, что 1 + 2 = 3 ,   2 + 3 = 5 {displaystyle {color {darkorange}1}+{color {darkorange}2}=3, {color {magenta}2}+{color {magenta}3}=5} и вычислим 3 ⋅ 5 = 15 {displaystyle 3cdot 5=15}
    • вычислим 1 ⋅ 2 = 2 {displaystyle {color {darkorange}1}cdot {color {magenta}2}=2}
    • вычислим 2 ⋅ 3 = 6 {displaystyle {color {darkorange}2}cdot {color {magenta}3}=6}
    • складывая результаты, получим, что 12 ⋅ 23 = 2 ⋅ 10 2 + ( 15 − 2 − 6 ) ⋅ 10 + 6 = 276 {displaystyle {color {darkorange}12}cdot {color {magenta}23}=2cdot 10^{2}+(15-2-6)cdot 10+6=276}
  • вычислим 13 ⋅ 11 {displaystyle {color {red}13}cdot {color {blue}11}} как 13 ⋅ 11 {displaystyle {color {darkorange}13}cdot {color {magenta}11}} :
    • заметим, что 1 + 3 = 4 ,   1 + 1 = 2 {displaystyle {color {darkorange}1}+{color {darkorange}3}=4, {color {magenta}1}+{color {magenta}1}=2} и вычислим 4 ⋅ 2 = 8 {displaystyle 4cdot 2=8}
    • вычислим 1 ⋅ 1 = 1 {displaystyle {color {darkorange}1}cdot {color {magenta}1}=1}
    • вычислим 3 ⋅ 1 = 3 {displaystyle {color {darkorange}3}cdot {color {magenta}1}=3}
    • складывая результаты, получим, что 13 ⋅ 11 = 1 ⋅ 10 2 + ( 8 − 1 − 3 ) ⋅ 10 + 3 = 143 {displaystyle {color {darkorange}13}cdot {color {magenta}11}=1cdot 10^{2}+(8-1-3)cdot 10+3=143}
  • складывая результаты, получим, что 1213 ⋅ 2311 = 276 ⋅ 10 4 + ( 850 − 276 − 143 ) ⋅ 10 2 + 143 = 2803243 {displaystyle {color {red}1213}cdot {color {blue}2311}=276cdot 10^{4}+(850-276-143)cdot 10^{2}+143=2803243}

Имя:*
E-Mail:
Комментарий: