卡拉楚巴算法

Karatsuba 算法、Karatsuba 乘法、卡拉楚巴乘法、卡拉楚巴算法（俄語：Алгоритм Карацубы）， 是一種快速乘法算法，由一九六空年阿納托利 ・ 阿列克謝呢維奇 ・ 卡拉楚巴提出並且佇一九六二年發表。伊將這兩个 $ n $ 位數字相乘所需要的一位數乘法次數減到上濟 $ 三 n ^ { \ log _ { 二 } 三 } \ approx 三 n ^ { 一爿五八五 } $（若是 $ n $ 是二的所在，愛做拄好的為 $ n ^ { \ log _ { 二 } 三 } $）。 因此伊比欲 $ n ^ { 二 } $ 次個位數乘法的經典算法愛緊。比如講，對兩个一千空二十四位的數相乘（$ n=一千空二十四=二 ^ { 十 } $）， 卡拉楚巴算法需要 $ 三 ^ { 十 }=五交九千空四十九 $ 次個位數乘法，經典算法需要 $ ( 二 ^ { 十 } ) ^ { 二 }=一百空四石八千五百七十六 $ 次。Toom–Cook 算法是此算法閣較緊的泛型。對充分大的 $ n ( n \ gg 一 ) $，Schönhage-Strassen 做算法甚至閣較緊，算法的時間複雜度做 $ O ( n \ log n \ log \ log n ) $。

價值咧講的是，㧎拉楚巴算法是第一个比小學二擺乘法算法漸漸進快速的算法。

算法

基本步數

㧎拉楚巴算法主要是用佇兩个大數的乘法，真大提高了運算效率，佮普通乘法比較低複雜度，並佇咧其中運用著遞歸的思想。基本的原理佮做法是將位數真濟的兩个大數 $ x $ 和 $ y $ 分做位數較少的數，逐家攏是原來 $ x $ 和 $ y $ 位數的一半。按呢處理了後，簡化為做三擺乘法，閣附帶少量的加法操作佮移位操作。

示例

愛計算一鼻兩千三百四十五佮六千七百八十九的乘積：

一孵兩千三百四十五=十二·_ 一千 _ + 三百四十五

六千七百八十九=六·_ 一千 _ + 七百八十九嘿干焦三个數進行運算的乘法結果：

_ z _ 二=十二 × 六=七十二

_ z _ 零=三百四十五 × 七仔八十九=二十七石兩千兩百空五

_ z _ 一=( 十二 + 三百四十五 ) × ( 六 + 七仔八十九 ) − _ z _ 二 − _ z _ 零=三仔五十七 × 七仔九十五 − 七十二 − 二十七石兩千兩百空五=二十八學三千八百十五 − 七十二 − 二十七石兩千兩百空五=一爿一千五百三十八葩將三部份結果相加並相應地移位：

結果=_ z _ 二·( _ B _ m ) 二 + _ z _ 一·( _ B _ m ) 一 + _ z _ 零·( _ B _ m ) 零 , i . e .

結果=七十二 ・ _ 一千 _ 二 + 一孵一千五百三十八·_ 一千 _ + 二十七石兩千兩百空五=八千三百八十一孵空兩百空五 .

注意：中央第三擺乘法運算的輸入域小於前兩擺乘法的兩倍，其實輸出域較細佇前兩擺乘法的四倍，並且基數為一千的進位是根據前兩改的乘法計算的，佇咧計算這兩个減法的時著愛考慮。

參考文獻

• Karatsuba's Algorithm for Polynomial Multiplication
• 埃里克 ・ 韋斯坦因為 . Karatsuba Multiplication . MathWorld .
• Bernstein , D . J . , " Multidigit multiplication for mathematicians " . Covers Karatsuba and many other multiplication algorithms .

外部鏈接

• 卡拉楚巴多項式乘法算法
• 埃里克 ・ 韋斯坦因為 . Karatsuba Multiplication（卡拉楚巴乘法）. MathWorld .
• Bernstein , D . J . , " Multidigit multiplication for mathematicians " . Covers Karatsuba and many other multiplication algorithms .