这个系列主要是记一下目前效率较高或者比较出名的一些算法.
Karatsuba multiplication:
x=5678 then: a=56 b=67
y=1234 c=12 d=34
setps:
1: a*c = 672 ①
2: b*d=2652 ②
3: (a+b)(c+d)=6164 ③
4: ③-②-①=2840
5: 6720000 + 2652+284000 = 7006652
Recursive algorithm:
whrite: x= 10n/2 a+b y= 10 n/2 c+d
then x*y = 10nac+10n/2(ad+bc)+bd 这里，我们需要做4次乘法，在计算机中的cost并不理想，所以用到一个
Gauss's trick:
step1: recursively compute ac
step2： recurisively compute bd
step3: recurisively compute (a+c)*(c+d) then
ad+bc = (a+c)*(c+d) - ac - bd
upshot:only 3 recursive multiply calls.
note： 这里的n表示位数， 比如x是6位数，n=6， n/2=3，如果x=7，则n/2取4.
保留一个问题，这个是我比较困惑的， 如果x和y位数相差比较大这个算法还能不能用， 比如x是7位数，y是三位数，希望大神解答!
在计算机里，少做一次乘法的效率会提高不少，对于给定的n位大数，算法的复杂度不超过3nlog3 ≈ 3n1.585, 一般给定N位数，复杂度是n平方。