c++ - 非常大的A除以非常大的B

Closed. This question is off-topic。它当前不接受答案。












想改善这个问题吗？ Update the question，所以它是用于堆栈溢出的on-topic。

9年前关闭。



Improve this question




我已经进行了长数乘法，长数加法，长数减法和长数除法的功能。但是分裂需要很长时间，如何改进呢？这是我的代码:

/// removes unnecessary zeros
vector<int> zero(vector<int> a)
{
    bool f=false;
    int size=0;
    for(int i=a.size()-1;i>=0;i--)
    {
        if(a[i]!=0)
        {
            f=true;
            size=i;
            break;
        }
    }
    if(f)
    {
        vector<int> b(size+1);
        for(int i=0;i<size+1;i++)
            b[i]=a[size-i];
        return b;
    }
    else
        return a;
}
/// a+b
vector<int> sum(vector<int> a,vector<int> b)
{
    if(a.size()>b.size())
    {
        vector<int> rez(3000);
        int a_end=a.size()-1;
        int remainder=0,k=0,ans;
        for(int i=b.size()-1;i>=0;i--)
        {
            ans=a[a_end]+b[i]+remainder;
            if(ans>9)
            {
                rez[k]=ans%10;
                remainder=ans/10;
            }
            else
            {
                rez[k]=ans;
                remainder=0;
            }
            k++;
            a_end--;
        }
        int kk=k;
        for(int i=a.size();i>kk;i--)
        {
            ans=a[a_end]+remainder;
            if(ans>9)
            {
                rez[k]=ans%10;
                remainder=ans/10;
            }
            else
            {
                rez[k]=ans;
                remainder=0;
            }
            k++;
            a_end--;
        }
        if(remainder!=0)
            rez[k]=remainder;
        return zero(rez);
    }
    else
    {
        vector<int> rez(3000);
        int b_end=b.size()-1;
        int remainder=0,k=0,ans;
        for(int i=a.size()-1;i>=0;i--)
        {
            ans=b[b_end]+a[i]+remainder;
            if(ans>9)
            {
                rez[k]=ans%10;
                remainder=ans/10;
            }
            else
            {
                rez[k]=ans;
                remainder=0;
            }
            k++;
            b_end--;
        }
        int kk=k;
        for(int i=b.size();i>kk;i--)
        {
            ans=b[b_end]+remainder;
            if(ans>9)
            {
                rez[k]=ans%10;
                remainder=ans/10;
            }
            else
            {
                rez[k]=ans;
                remainder=0;
            }
            k++;
            b_end--;
        }
        if(remainder!=0)
            rez[k]=remainder;

        return zero(rez);
    }
}
/// a & b comparison
int compare(vector<int> a,vector<int> b)
{
    if(a.size()>b.size())
        return 1;
    if(b.size()>a.size())
        return 2;
    int r=0;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]>b[i])
        {
            r=1;
            break;
        }
        if(b[i]>a[i])
        {
            r=2;
            break;
        }
    }
    return r;
}
/// a-b
vector<int> subtraction(vector<int> a,vector<int> b)
{
    vector<int> rez(1000);
    int a_end=a.size()-1;
    int k=0,ans;
    for(int i=b.size()-1;i>=0;i--)
    {
        ans=a[a_end]-b[i];
        if(ans<0)
        {
            rez[k]=10+ans;
            a[a_end-1]--;
        }
        else
            rez[k]=ans;
        k++;
        a_end--;
    }
    int kk=k;
    for(int i=a.size();i>kk;i--)
    {
        ans=a[a_end];
        if(ans<0)
        {
            rez[k]=10+ans;
            a[a_end-1]--;
        }
        else
            rez[k]=ans;
        k++;
        a_end--;
    }
    return zero(rez);
}
/// a div b
vector<int> div(vector<int> a,vector<int> b)
{
    vector<int> rez(a.size());
    rez=a;
    int comp=-1;
    vector<int> count(1000);
    vector<int> one(1);
    one[0]=1;
    while(comp!=0 || comp!=2)
    {
        comp=compare(rez,b);
        if(comp==0)
            break;
        rez=subtraction(rez,b);
        count=sum(count,one);
    }
    count=sum(count,one);
    return count;
}

最佳答案

您的大量实现可能很慢。通常，您可能应该使用base-216(在32位计算机中)而不是使用base-10，即在计算机的每个字中使用一半的位。

这样可以确保乘法不会溢出32位寄存器。开始实现normalize函数，该函数将对大数进行标准化(即，对于每个存储的数字，请检查其是否溢出216，以及是否确实将余数应用于下一个数字)。由于数字的范围较大，因此您将需要更少的内存，以及更少的模和除法运算。此外，基数为2的幂，模和除法运算比基数为10的方法快得多。

然后，所有操作都可以基本上按元素执行。加法将保留两位数中较大的一位，然后逐位相加，最后对结果进行归一化。

在您的除法函数中，它将删除许多 vector 复制。当前，您正在创建一个3000 int的 vector ，该 vector 将在循环的每次迭代中进行复制和处理，您可能要考虑实现一个就位+=(vector,int)操作，该操作将修改该 vector ，而不是在所有复制时都创建一个新的 vector 。