Karatsuba乘法是一種快速乘法。此算法在1960年由Anatolii Alexeevitch Karatsuba 提出，並於1962年得以發表。此算法主要用於兩個大數相乘。普通乘法的複雜度是n2，而Karatsuba算法的複雜度僅為3n^log3≈3n^1.585（log3是以2為底的）。
算法描述,步驟簡介,實例展示,效率分析,編程實現,c語言：,python：,偽代碼描述,
算法描述
步驟簡介
Karatsuba算法主要套用於兩個大數的相乘，原理是將大數分成兩段後變成較小的數位，然後做3次乘法，並附帶少量的加法操作和移位操作。
現有兩個大數，x，y。
首先將x，y分別拆開成為兩部分，可得x1，x0，y1，y0。他們的關係如下：
x = x1 * 10 + x0；
y = y1 * 10 + y0。其中m為正整數，m < n，且x0，y0 小於 10。
那么 xy = (x1 * 10 + x0)(y1 * 10 + y0)
=z2 * 10 + z1 * 10 + z0，其中：
z2 = x1 * y1；
z1 = x1 * y0 + x0 * y1；
z0 = x0 * y0。
此步驟共需4次乘法，但是由Karatsuba改進以後僅需要3次乘法。因為：
z1 = x1 * y0+ x0 * y1
z1 = (x1 + x0) * (y1 + y0) - x1 * y1 - x0 * y0，
故z1 便可以由一次乘法及加減法得到。
實例展示
設x = 12345，y=6789，令m=3。那么有：
12345 = 12 * 1000 + 345；
6789 = 6 * 1000 + 789。
下面計算：
z2 = 12 * 6 = 72；
z0 = 345 * 789 = 272205；
z1 = (12 + 345) * (6 + 789) - z2 - z0 = 11538。
然後我們按照移位公式（xy = z2 * 10^(2m) + z1 * 10^(m) + z0）可得：
xy = 72 * 1000 + 11538 * 1000 + 272205 = 83810205。
效率分析
對於給定的n位大數，算法的複雜度不超過3n≈ 3n。
編程實現
c語言：
bigint mult(bigint a, bigint b){ bigint c; c.len = a.len + b.len ; for(int i=1; i <= c.len; i++) c.s[i] = 0; for(int i=1; i <= a.len; i++) for(int j=1; j <= b.len; j++) c.s[i+j-1] += a.s[i]*b.s[j]; for(int i=1; i<= c.len ; i++) { c.s[i+1] += c.s[i]/10; c.s[i] %= 10; }}python：
在以前的python2中,整型分為int和long,也就是整型和長整型, 長整型不存在溢出問題, 即可以存放任意大小的數值. 在python3 中,統一使用長整型.因此python整數運算不需要考慮數據類型；
其次，在python源碼：Objects/longobject.c中有對long整型的實現，其中對於數字的相加，內部就是實現了此Karatsuba算法，實現於k_mul，對源碼感興趣對可以了解
static PyLongObject *k_mul(PyLongObject *a, PyLongObject *b){ Py_ssize_t asize = Py_ABS(Py_SIZE(a)); Py_ssize_t bsize = Py_ABS(Py_SIZE(b)); ..... .....}偽代碼描述
procedure Karatsuba(num1,num2) if (num1<10) or (num2<10) return num1 * num2 /*calculates the size of the numbers*/ m = max(size(num1),size(num2)) m2 = m/2 high1, low1 = split_at(num1, m2) high2, low2 = split_at(num2, m2) /*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^(m)) + ((z1 - z2 - z0）* 10^(m/2)) + (z0)
