大整数乘法-算法设计与分析

分治法-大整数乘法

输入：

正负零不限，两数长度也不限。输入完第一个数后，回车，输入第二个数，回车。

输出：

两个数相乘的结果

实现思路

1.用C++实现大整数乘法
2.算法性能优化

对于X*Y :
X: a b 分为高位部分a和低位部分b;
Y: c d 分为高位部分c和低位部分d;
由于X和Y的位数可能不同，因此高位部分和低位部分的划分标准是：
低位部分位数是n/2，其中n是X和Y中最少的位数。剩余的部分就是高位部分，因此：

对于代码实现:
数字用string类型表示;
需要设置大整数加（减）函数;
大整数乘法采用分治法;

代码：

#include<iostream>
using namespace std;

// 提前声明
string bigIntMulti(string X,string Y);


// 比较两个非负数大整数的大小
// 0 =
// 1 >
// -1 <
int cmpBigInt(string X,string Y)
{
    if(X.size()>Y.size())
        return 1;
    else if(X.size()<Y.size())
        return -1;
    else
    {
        for(int i=0;i<X.size();i++)
        {
            if(X[i]>Y[i])
                return 1;
            else if(X[i]<Y[i])
                return -1;
        }
        return 0;
    }
}

// 大整数加法
string bigIntAdd(string X,string Y)
{
    if(X[0]!='-'&&Y[0]!='-'||X[0]=='-'&&Y[0]=='-') // 全是正数或者全是负数
    {
        string shortNumber,longNumber;
        string result;
        int minLen=X.size();
        shortNumber=X;
        longNumber=Y;
        if(minLen>Y.size())
        {
            minLen=Y.size();
            shortNumber=Y;
            longNumber=X;
        }
        if(X[0]=='-'&&Y[0]=='-') // 全是负数要去掉负号计算
        {
            for(int i=1;i<shortNumber.size();i++)
                shortNumber[i-1]=shortNumber[i];
            shortNumber.erase(shortNumber.size()-1);
            for(int i=1;i<longNumber.size();i++)
                longNumber[i-1]=longNumber[i];
            longNumber.erase(longNumber.size()-1);
            minLen-=1;
        }
        int last=0; // 上一位的进位数
        int now=0; // 当前这一位的和与上一位进位数之和

        // 将短的数前补0对齐
        for(int i=0;i<longNumber.size()-minLen;i++)
            shortNumber='0'+shortNumber;
        
        // 相加计算
        for(int i=1;i<=longNumber.size();i++)
        {
            now=(shortNumber[shortNumber.size()-i]-'0')+(longNumber[longNumber.size()-i]-'0')+last;
            last=now/10;
            result=char(now%10+'0')+result;
        }
        // 如果还有进位
        if(last>0)
            result=char('0'+last)+result;
        if(X[0]=='-'&&Y[0]=='-')
            return '-'+result;
        return result;
    }
    else // 一个负数一个正数
    {
        // 求绝对值
        string absX=X,absY=Y;
        if(X[0]=='-')
        {
            for(int i=1;i<X.size();i++)
                absX[i-1]=X[i];
            absX.erase(X.size()-1);
        }
        if(Y[0]=='-')
        {
            for(int i=1;i<Y.size();i++)
                absY[i-1]=Y[i];
            absY.erase(Y.size()-1);
        }

        int cmpFlag=cmpBigInt(absX,absY); // 绝对值大小
        if(cmpFlag==0)
            return string("0");

        int biggerIsMinus=0; // 绝对值大的是否是负数
        string biggerAbs,smallerAbs; // 更大的绝对值 更小的绝对值
        if(cmpFlag>0)
        {
            biggerAbs=absX;
            smallerAbs=absY;
            if(X[0]=='-')
                biggerIsMinus=1;
            else 
                biggerIsMinus=0;
        }
        else
        {
            biggerAbs=absY;
            smallerAbs=absX;
            if(X[0]=='-')
                biggerIsMinus=0;
            else
                biggerIsMinus=1;
        }
        
        // 计算绝对值的差
        int borrow=0; // 低一位是否借位了
        int now=0; // 当前这一位被减数减去借位后再减去减数后的值
        string result;

        // 如果绝对值更小的更短则前面补全0
        int minLen=smallerAbs.size();
        for(int i=0;i<biggerAbs.size()-minLen;i++)
            smallerAbs='0'+smallerAbs;

        // 相减
        for(int i=biggerAbs.size()-1;i>=0;i--)
        {
            now=(biggerAbs[i]-'0')-borrow-(smallerAbs[i]-'0');
            if(now<0)
            {
                now+=10;
                borrow=1;
            }
            else
                borrow=0;
            result=char('0'+now)+result;
        }

        // 返回结果
        if(biggerIsMinus)
            return '-'+result;
        else
            return result;
    }
}


// 正大整数乘法
string positiveBigIntMulti(string X,string Y)
{
    // 小规模
    string shortNumber,longNumber;
    if(X.size()==1||Y.size()==1) // 有一个数只有1位时是最小的易于计算的规模
    {
        if(X.size()==1)
        {
            shortNumber=X;
            longNumber=Y;
        }
        else
        {
            shortNumber=Y;
            longNumber=X;
        }
        string result;
        int last=0; // 上一位的进位数
        int now=0; // 当前这一位的乘积和上一位进位的和
        for(int i=longNumber.size()-1;i>=0;i--)
        {
            now=(shortNumber[0]-'0')*(longNumber[i]-'0')+last;
            last=now/10; // 向前进位
            result=char('0'+now%10)+result;
        }
        // 对于最后的进位
        if(last>0)
            result=char('0'+last)+result;
        return result;
    }
    
    // 分解
    string a,b,c,d;
    int halfLen;
    // 考虑到可能存在X,Y长度不等到情况，halfLen是最短的长度的一半
    halfLen=X.size();
    if(Y.size()<X.size())
        halfLen=Y.size();
    halfLen=halfLen/2;
    
    for(int i=0;i<X.size()-halfLen;i++)
        a+=X[i];
    for(int i=X.size()-halfLen;i<X.size();i++)
        b+=X[i];
    for(int i=0;i<Y.size()-halfLen;i++)
        c+=Y[i];
    for(int i=Y.size()-halfLen;i<Y.size();i++)
        d+=Y[i];
    

    // 对分解的部分进行递归求解
    string power2N,power2Ndiv2; // 计算10的幂次
    for(int i=0;i<halfLen*2;i++)
        power2N+='0';
    for(int i=0;i<halfLen;i++)
        power2Ndiv2+='0';

    string ac=positiveBigIntMulti(a,c);
    string bd=positiveBigIntMulti(b,d);
    string aSubB=bigIntAdd(a,'-'+b);
    string dSubC=bigIntAdd(d,'-'+c);

    string result=bigIntAdd(ac+power2N,bigIntAdd(bigIntAdd(bigIntAdd(bigIntMulti(aSubB,dSubC),ac),bd)+power2Ndiv2,bd));

    // 返回结果
    return result;
}


// 返回0是出错，1是正确且结果是正数，2是正确且结果是负数
int isError(string X,string Y)
{
    for(int i=0;i<X.size();i++)
    {
        if(i==0&&X[i]=='-')
            continue;
        if(X[i]>'9'||X[i]<'0')
            return 0;
    }
    for(int i=0;i<Y.size();i++)
    {
        if(i==0&&Y[i]=='-')
            continue;
        if(Y[i]>'9'||Y[i]<'0')
            return 0;
    }
    // 考虑只有'-'的情况
    if(X.size()==1&&X[0]=='-'||Y.size()==1&&Y[0]=='-')
        return 0;
    if(X[0]=='-'&&Y[0]!='-'||Y[0]=='-'&&X[0]!='-')
        return 2;
    else
        return 1;
}


// 大整数乘法
string bigIntMulti(string X,string Y)
{
    int errorFlag=isError(X,Y);
    if(errorFlag==0)
        return "Input error!\n";

    // 输入正确

    if(X.size()==1&&X[0]=='0'||Y.size()==1&&Y[0]=='0') // 因数为0的情况
        return string("0");

    if(X[0]=='-') // 去除负号
    {
        for(int i=1;i<X.size();i++)
            X[i-1]=X[i];
        X.erase(X.size()-1);
    }
    if(Y[0]=='-') // 去除负号
    {
        for(int i=1;i<Y.size();i++)
            Y[i-1]=Y[i];
        Y.erase(Y.size()-1);
    }

    // 正数结果
    string positiveResult=positiveBigIntMulti(X,Y);

    if(errorFlag==2)
        return '-'+positiveResult;
    else
        return positiveResult;
}


int main()
{
    string X,Y;
    cout<<"Please input integers (Positive and negative are not limited and the lengths of two numbers can be unequal)\nX\nY\n";
    cin>>X>>Y;
    
    string result=bigIntMulti(X,Y);
    cout<<result<<endl;

    return 0;
}

注：本博客代码来源于算法随堂作业，不是很完备，仅供参考。