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 ミリ秒かかりました。悪い改善ではありません:)

残念ながら、長い割り算を何年も使っていなかったので、やり方を忘れていました。私はすぐに、長い除算を再学習してから実装しようとしている、最もプロフェッショナルな Web サイトを見つけました。私はこれを使用しました: http://www.coolmath4kids.com/long-division/long-division-lesson-1.html . はい、そうですハハハ。サイトは実際に役に立ちました。数時間以内にアルゴリズムを修正しました。

もちろん、その Web サイトを使用する必要はありませんが、アルゴリズムを改善する必要があります。これを実行するには、長い除算よりも効率的な方法がありますが、効率と実装の容易さのバランスが取れているのは長い除算であることがわかりました。

于 2011-11-27T12:37:37.237 に答える
1

あなたの大きな数の実装全体はおそらくかなり遅いでしょう。原則として、基数 10 を使用する代わりに、基数 2 の16 (32 ビット マシンで) を使用する必要があります。つまり、マシンの各ワードのビットの半分を使用します。

これにより、乗算が 32 ビット レジスタをオーバーフローしないことが保証されます。大きな数を正規化normalizeする関数の実装を開始します(つまり、格納された各数字について、2 16をオーバーフローするかどうかをチェックし、次の数字に剰余を適用するかどうかを確認します)。数字の範囲が広いため、必要なメモリが少なくなり、モジュロ演算と除算演算が少なくなります。さらに、基数が 2 の累乗であるため、モジュロ演算と除算演算は基数 10 のアプローチよりもはるかに高速です。

その後、すべての操作は基本的に要素ごとに実行できます。加算は、2 つのうち大きい方よりも 1 桁多い数を確保し、次に桁ごとに加算し、最後に結果を正規化します。

除算関数では、多くのベクトル コピーが削除されます。int現在、ループの各反復でコピーおよび処理される3000 のベクターを作成してい+=(vector,int)ます。すべてのコピーで新しいベクターを作成するのではなく、ベクターを変更するインプレース操作の実装を検討することをお勧めします。

于 2011-11-27T12:31:38.773 に答える
1

低速の除算アルゴリズムを使用しており、高速の除算アルゴリズムがありますhttp://en.wikipedia.org/wiki/Division_%28digital%29

于 2011-11-27T12:30:05.817 に答える