分治法实现大数乘法
例如：
$$ 想要计算xx，x<10^4 \\假设我们的电脑只支持10以内的乘法和足够大位数的加法\\同时假设单次乘法和加法的复杂度相同\\ x = 950<10^{4}\\ 分解：x = 910^2+50\\ 9<10^2;50<10^2\\ 现在只需要计算四次两个<10^2的乘法，再分解\\ 9 = 010+9; 50= 510+0\\ 9 50= (010+9)(510+0)
$$
分析：
在上面提到的假设下
如果使用加法，那么950*950需要调用950次加法 ，消耗950个单位时间
但使用上面提到的乘法运算，我们将950分治两次，得到950 = 9102+5*10，都是10以内的数，那么最终的10以内的乘法的次数可以控制在50次以内，加法、减法也可以控制在50次以内，最终只消耗100个单位时间以内，对于更大的数这种优势会更明显
复杂度计算
$$ T(n)=\# of \, multiplication\\ T(n)=4T(n/2)+\theta(n)\\ T(n)=n+n/24+n/2/244+...\\ T(n)=n+2n+4n+....(共log_2n项)\\ 根据等比数列求和公式\\ T(n)=n\frac{1-2^{log_2n}}{1-2}=O(n^2) $$
上面的分治算法有很多种改进，一种最显而易见的改进是
实现了从每个节点分四枝降到了每个节点分三枝
其他改进算法比如
记住这张图就能记住$x_{i+1}$和$x_i$的递推公式