0

ウィキペディア ( http://en.wikipedia.org/wiki/Binary_GCD_algorithm ) によると、bignum (最大 5000 桁) のバイナリ GCD を作成しようとしていました。

私のGCD自体は次のようになります。

bitset<N> gcd(bitset<N> u, bitset<N> v) {
    bitset<N> one (string("1"));
    bitset<N> zero (string("0"));

    int shift;

    if (u == 0) return v;
    if (v == 0) return u;

    for (shift = 0; ((u | v) & one) == zero; ++shift) {
        u >>= 1;
        v >>= 1;
    }

    while ((u & one) == zero) u >>= 1;

    do {
        while ((v & one) == zero) v >>= 1;

        if (u.to_string() > v.to_string()) {
            bitset<N> t = v;
            v = u;
            u = t;
        }

        bitsetSubtract(v,u);
    } while (v != 0);

    return u << shift;
}

私は独自のビットセット減算関数も使用しています:

void bitsetSubtract(bitset<N> &x, const bitset<N> &y) {
    bool borrow = false;

    for (int i = 0; i < N; i++) {
        if (borrow) {
            if (x[i]) {
                x[i] = y[i];
                borrow = y[i];
            } else {
                x[i] = !y[i];
                borrow = true;
            }
        } else {
            if (x[i]) {
                x[i] = !y[i];
                borrow = false;
            } else {
                x[i] = y[i];
                borrow = y[i];
            }
        }
    }
}

このアルゴリズムの速度を改善する場所は見当たりません (バイナリ GCD 自体は高速です) が、プログラムが遅すぎるというフィードバックが寄せられています。

4

1 に答える 1

6

bignum を基数 2 (バイナリ) の数字の配列として表しました。

実際の bignum ライブラリは 2 の基数を使用しません。CPU には一度に複数のビットを操作する命令があるため、より大きな基数を使用します。通常、目標が最大速度と最小サイズである場合、または100の基数( 1バイトで1 桁あたり 2 バイト)、10000 (1 桁あたり 2 バイト)、1000000000 (1 桁あたり 4 バイト)、または 1000000000000000000 (1 桁あたり 8 バイト)。

vector<uint32_t>orのようなものをvector<uint64_t>bignumとして使用し、一度に1ビットだけでなく、一度に32ビットまたは64ビットで操作する必要があります。

于 2012-12-03T22:40:55.213 に答える