关于大数的乘法

关于计算两个非常大的数字的乘法（求解大数的n次方，浮点数的高精度的乘法或幂都可以归类到这个问题）的方法，经常可以见到。今天我又一次看到这道题，所以这里就将我想到的方法记录下来，以备将来使用。

首先，回顾一下常见的普通大小的整数乘法，我们人肉计算是竖式计算的方式，这种方式也可以看做将两个乘数都分成一位位的，然后分别相乘计算，也就是

x = abcdef
y = mnpqrs
x * y = (abcdef) * (mnpqrs)
      = （a*10^5+b*10^4+...+f） * (m*10^5+n*10^4+...+s)
      = ....(这一步就是竖式的一位位的计算)

然后我们再来想想大数于普通int型数的不同是什么？

以下表示大数的方法简单的以10进制字符串的形式表示和存储，其他存储方式可能也可以。（比如2进制可能更合适，但十进制在手写时比较直观）

如果大数以0结尾，可以先分解成x*10^k，用x计算后，尾部加上k个0即可。以下会有一些乘以10^k的地方，使用这种方法计算就可以很简单的实现。

int 型的计算是分成长度个1位数*10^k的和，然后拆开计算求和。int型整数(32bit)之所以方便被计算机计算的原因就是分成的位数(10进制，最多10位）足够小，在内存中方便直接存储。反过来也就是大数（比如一个长100的10进制整数）如果按一位位的10进制基本单元来算的话，分成的单元个数太多，不好直接计算。

那怎么解决这个问题呢？很简单，不要一位位的分，而是一个单元许多位的分，或者不要按10进制计算，按一亿进制计算（举例）

本篇文章暂时只考虑第一种方法，即将一个大数x分成若干个单元，每个单元有若干位，使得分成的单元个数足够小到方便计算机计算。

为简单起见，假设每次分成2个单元，尽量均分，即将10进制显示的字符串长度为n的大数x分成前一半长度[n/2]位的数a*10^(n-[n/2])和后一半长度(n-[n/2])位的数b。

也就是

x = a*10^(n-[n/2]) + b

a 和 b的长度都是x的一半左右（如果x的长度足够小，比如小于10，在int范围内，则a = 0, x = b）

另一个乘数是长度m的大数y,可以同样分解成 y = c*10^(m-[m/2]) + d

然后 x * y 就可以分解成几个长度差不多缩小一半的数（或大数）的乘积的和了。

如果分解出的单元的乘法依然是大数乘法，用同样方法递归到长度足够小为止即可。

接下来只剩下一个问题了，就是上面计算了分解单元的大数和后，还要将他们加起来，这就是大数求和问题了。

大数求和这个问题很简单，只要把大数x按10进制位的int/short的数组形式存储，数组长度就是大数的10进制字符串的长度即可。大数相加只要将两个数组逐位相加并考虑进位即可，（负数，大数相减的问题差不多，使用同样方式）。

至此，大数相乘的问题就解决了。

关于代码实现，之后会加上。