根据维基百科 (http://en.wikipedia.org/wiki/Binary_GCD_algorithm),我正在尝试为 bignums(最多 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 本身很快),但我收到反馈说我的程序太慢了。
最佳答案
您已将 bignum 表示为 base-2(二进制)数字的数组。
真正的 bignum 库不使用 2 的基数。它们使用更大的基数,因为 CPU 的指令一次操作不止一位。通常,您会使用 256 (28)、65536 (216)、4294967296 (232) 或 18446744073709551616 (2 64) 如果您的目标是最大速度和最小大小,或者以 100(每个数字一个字节)、10000(每个数字两个字节)、1000000000(每个数字四个字节)为基数,或 10000000000000000000(每个数字八个字节)如果您必须存储精确的小数部分。
你需要使用类似 vector<uint32_t>
的东西或 vector<uint64_t>
作为您的 bignum,一次对 32 位或 64 位进行运算,而不是一次仅对 1 位进行运算。
关于c++ - 二进制 GCD - 算法太慢,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13692766/