1

我已经做了一个长数乘法、长数加法、长数减法和长数除法的函数。但是分割需要很长时间，如何改进呢？这是我的代码：

/// 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;
}
4

3 回答 3

2

您的问题是您反复减去，这意味着您正在为大量数字运行大量迭代。这将导致非常糟糕的性能。

我在年初（在大学作业中）遇到了这个确切的问题。我估计我最初的除法（使用重复减法）需要大约 100 年才能完成。我实现了长除法（与手动除数的方法相同），相同的计算耗时约 5 毫秒。不错的改进:)

不幸的是，我多年来没有使用长除法，所以我忘记了如何去做。我很快找到了我能找到的最专业的网站，试图重新学习，然后实施长除法。我用这个： http: //www.coolmath4kids.com/long-division/long-division-lesson-1.html。是的，没错哈哈哈。该网站实际上有所帮助。我在几个小时内就修好了我的算法。

显然你不必使用那个网站，但你必须让你的算法更好。有比长除法更有效的方法，但我发现长除法可以在效率和易于实施之间取得良好的平衡。

于 2011-11-27T12:37:37.237 回答
1

你用的是慢除法算法，还有快除法算法http://en.wikipedia.org/wiki/Division_%28digital%29

于 2011-11-27T12:30:05.817 回答
1

您的整个大数字实施可能很慢。作为一般规则，您应该使用 base-2 16（在 32 位机器中）而不是使用 base-10，也就是说，使用机器每个字中的一半位。

这确保了乘法不会溢出 32 位寄存器。开始实现一个normalize函数来规范化大数（即，为每个存储的数字检查它是否溢出 2 16以及是否将余数应用于下一个数字）。因为数字的范围更大，所以您需要更少的内存，以及更少的模和除法运算。此外，由于底数是 2 的幂，模数和除法运算比使用以 10 为底的方法要快得多。

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

在您的除法功能中，它将删除大量矢量复制。目前，您正在创建一个 3000 的向量，该向量int在循环的每次迭代中都会被复制和处理，您可能需要考虑实现一个+=(vector,int)将修改向量的就地操作，而不是创建一个包含所有复制的新向量。

于 2011-11-27T12:31:38.773 回答