大数乘法的深入讨论一（模拟小学手算法）

  作为相继出现在ACM、华为腾讯等大厂的面试、笔试中的一道算法题，大数乘法还是挺需要深入研究一下的。因此，今天就来谈谈大数乘法。

问题引入

  首先，为什么会有大数的概念？我们知道，在计算机中，数的存储是有一定范围的（e.g.在一个32位编译器上，int型占4个字节，即32位，所以它的范围在[-2147483648, +2147483647]）。
  有范围就会有溢出，如果我要算的数过大，那么就很难用一般的计算方法得到正确结果。
  因此，我们引入一种新的思想——以字符串的形式输入，转成整形数组，再进行相应运算。

目前较为主流的大数乘法有：

  模拟手工算法；
  分治算法；
  FFT算法；
  ……
  下面，将分成三篇文章分别讨论这三种算法。我们首先从最简单的模拟手工算法开始。

模拟手工算法：

普通大数乘法的优点是空间复杂度低，实现简单，时间复杂度为O（N²）（逐位相乘）

算法思路

对比下图的手算步骤，我们的算法可总结成两步：
①逐位相乘（）
②对应相加

具体细节：

①判断正负号（相异为负）
②移除输入字符串中的符号位（若字符串第一位为'-'，用erase()函数删掉）
③字符串反转（数字高位在左，字符串低位在左，反转字符串便于计算）
④需要一个int数组存储各个位上的计算结果。
⑤两重for循环算出，并且进行移位操作（观察发现，经移位后的位置为i+j）
⑥对应相加，进位
⑦转成字符串输出

源码：

#include<bits/stdc++.h>
using namespace std;
string big_multiply(string a,string b);
int main(){
    string a,b;
    cout<<"输入待乘数：\n";
    while(cin>>a){
        cin>>b;
        cout<<big_multiply(a,b)<<endl<<"\n输入待乘数：\n";
    }
    return 0;
}
string big_multiply(string a,string b){
    string s_result="";//用作返回 
    vector <int> result(a.length()+b.length());//存储大数各位数值，进位计算 
    if((a[0]=='-'&&b[0]!='-')||(a[0]!='-'&&b[0]=='-')) s_result="-";//符号判断
    if(a[0]=='-') a.erase(0);
    if(b[0]=='-') b.erase(0);
    reverse(a.begin(),a.end());//反转，使得数的高位对应数组高位
    reverse(b.begin(),b.end());
    for(int i=0;i<a.length();i++){
        for(int j=0;j<b.length();j++){
            result[i+j]+=(a[i]-'0')*(b[j]-'0');
        }
    }
    for(int i=0;i<a.length()+b.length();i++){
            result[i+1]+=result[i]/10;
            result[i]=result[i]%10;
    }
    int index=result.size()-1;
    while(result[index]==0) index--;//找到非0的最高位
    for(int i=index;i>=0;i--){
        s_result+=result[i]+'0';
    } 
    return s_result;
}