卡拉楚巴算法
Karatsuba算法、Karatsuba乘法、卡拉楚巴乘法、卡拉楚巴算法(俄語:Алгоритм Карацубы),是一種快速乘法算法,由1960年阿納托利·阿列克謝耶維奇·卡拉楚巴提出並於1962年發表。[1][2][3]它將兩個位數字相乘所需的一位數乘法次數減少到了至多(如果是2的乘方,則正好為)。因此它比要次個位數乘法的經典算法要快。例如,對於兩個1024位的數相乘(),卡拉楚巴算法需要次個位數乘法,而經典算法需要次。Toom–Cook算法是此算法更快速的泛型。對於充分大的,Schönhage-Strassen演算法甚至更快,算法的時間複雜度為。
值得一提的是,卡拉楚巴算法是第一個比小學二次乘法算法漸進快速的算法。
算法
基本步驟
卡拉楚巴算法主要是用於兩個大數的乘法,極大提高了運算效率,相較於普通乘法降低了複雜度,並在其中運用了遞歸的思想。基本的原理和做法是將位數很多的兩個大數和分成位數較少的數,每個數都是原來和位數的一半。這樣處理之後,簡化為做三次乘法,並附帶少量的加法操作和移位操作。
示例
要計算12345和6789的乘積:
- 12345 = 12 · 1000 + 345
- 6789 = 6 · 1000 + 789
對只有三個數進行運算的乘法結果:
- z2 = 12 × 6 = 72
- z0 = 345 × 789 = 272205
- z1 = (12 + 345) × (6 + 789) − z2 − z0 = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538
將三部分結果相加並相應地移位:
- 結果 = z2 · (Bm)2 + z1 · (Bm)1 + z0 · (Bm)0, i.e.
- 結果 = 72 · 10002 + 11538 · 1000 + 272205 = 83810205.
注意:中間第三次乘法運算的輸入域小於前兩次乘法的兩倍,其輸出域小於前兩次乘法的四倍,並且基數為1000的進位是根據前兩次乘法計算的,在計算這兩個減法時必須考慮。
實現
偽代碼實現
procedure karatsuba(num1, num2)
if (num1 < 10) or (num2 < 10)
return num1*num2
/* calculates the size of the numbers */
m = max(size_base10(num1), size_base10(num2))
m2 = m/2
/* split the digit sequences about the middle */
high1, low1 = split_at(num1, m2)
high2, low2 = split_at(num2, m2)
/* 3 calls made to numbers approximately half the size */
z0 = karatsuba(low1,low2)
z1 = karatsuba((low1+high1),(low2+high2))
z2 = karatsuba(high1,high2)
return (z2*10^(2*m2))+((z1-z2-z0)*10^(m2))+(z0)
Python代碼實現
# Python 2 and 3
def karatsuba(num1, num2):
num1Str, num2Str = str(num1), str(num2)
if num1Str[0] == '-': return -karatsuba(-num1, num2)
if num2Str[0] == '-': return -karatsuba(num1, -num2)
if num1 < 10 or num2 < 10: return num1 * num2
maxLength = max(len(num1Str), len(num2Str))
num1Str = ''.join(list('0' * maxLength)[:-len(num1Str)] + list(num1Str))
num2Str = ''.join(list('0' * maxLength)[:-len(num2Str)] + list(num2Str))
splitPosition = maxLength // 2
high1, low1 = int(num1Str[:-splitPosition]), int(num1Str[-splitPosition:])
high2, low2 = int(num2Str[:-splitPosition]), int(num2Str[-splitPosition:])
z0, z2 = karatsuba(low1, low2), karatsuba(high1, high2)
z1 = karatsuba((low1 + high1), (low2 + high2))
return z2 * 10 ** (2 * splitPosition) + (z1 - z2 - z0) * 10 ** (splitPosition) + z0
參考文獻
- ^ A. Karatsuba and Yu. Ofman. Multiplication of Many-Digital Numbers by Automatic Computers. Proceedings of the USSR Academy of Sciences. 1962, 145: 293–294.
- ^ A. A. Karatsuba. The Complexity of Computations (PDF). Proceedings of the Steklov Institute of Mathematics. 1995, 211: 169–183 [2013-07-25]. (原始內容存檔 (PDF)於2020-03-26).
- ^ Knuth D.E.(1969)The art of computer programming. v.2. Addison-Wesley Publ.Co., 724 pp.
- 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.