两个n位数的运算

问题描述：设X, Y是两个n位的十进制数，求X*Y。

问题分析：

1.X，Y都是同等位数的十进制数。
2.因为位数为n位，所以有可能很大，不能进行直接的计算，所以必须想办法拆分。
3.可以使用分治算法，因为我的老师正好在讲解分治算法，所以练习一下。

例子：18*26

分析：

18=1*10+8； 26=2*10+6；

解法1：

18*26=1*2*10*10+（8*2+1*6）*10+6*8； （1）

因此可以写出其计算模型：

写出其递归时间分析公式：

最后求得T(n)=O(n2);

解法2：

对（1）进行优化：（ab*cd中：ad+bc=(a-b)*(d-c))
18*26=1*2*10*10+（（1-8）*（6-2）+1*2+8*6）*10+6*8； （2）

（为什么说是优化呢？因为对计算机硬件而言，的确是做出了优化；在（1）中，除了乘以十，进行了四次乘法；在（2）中，除了乘以十，做了五次乘法，不过有两个是重复的，可以直接在CPU的寄存器或者存储器直接调用，而不需要反复计算；相当于就是做三次运算）（看起来优化不大，对吧，等下看看实际效果。）（该思想由他提出：Anatoly Karatsuba）

计算模型：

递归的时间分析：

最后可求得T(n）=O(n^1.59)（这已经是低阶与高阶的差距了。）

补充完整：递归的结束公式：
当输入规模为1的时候，返回该值；

伪码描述：

DIVIDE_CONQUER(x,y,n){  //x,y:代表待处理的数字；n：表示x，y为n位整数
    if x==0 || y==0  //针对尾数为0的情况
        return 0
    else if n==1
        return x*y
    else
        x1=x/(pow(10,n/2));
        x0=x%(pow(10,n/2));
        y1=y/(pow(10,n/2)); y2=y/(pow(10,n/2));
        z1=DIVIDE_CONQUER(x1,y1,n/2);
        z2=DIVIDE_CONQURR(x0,y0,n/2);
        z3=DIVIDE_CONQUER((x1-x0),(y0-y1),n/2)+z1+z2;
        return z1*pow(10,n)+z3*pow(10,n/2)+z3;
    }