karatsuba算法原理及python实现
karatsuba algorithm 计算大数乘法：
暴力解法是：
其中都将x,y分成一半，x1是高位，x0是低位，对y也是这样，r是进制的权重，十进制就是10。
可知需要四次的乘法操作，复杂度将为Θ(N)
让：
最后的式子z = 的右边实际上变成了三项，我们总共做三次的乘法，因此有等式
Θ(N)是加法的操作时间，3次乘法因此有3T(n/2)，最后计算出来的时间是θ( nlog23) = θ( n 1.5849625··)
比上面的暴力解法要好。如果分成3份或者更多可能效果更好，例如分成3份最终运行时间是θ( nlog35)
更加好。
python代码测试：
可以清楚看出时间的差距。