二进制GCD - 太慢算法

根据维基百科（http://en.wikipedia.org/wiki/Binary_GCD_algorithm），我试图为bignums编写二进制GCD（最多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; 
}

我还使用自己的bitset减法功能：

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本身速度很快），但我得到的反馈是我的程序太慢了。

来源

2012-12-03 Mateusz Kowalski

您是否尝试通过分析查看瓶颈位置？ –

欢迎来到Stack Overflow，程序员的**问题**和**答案**网站！你有问题吗？ –

您已将bignum表示为基数2（二进制）数字的数组。

真正的bignum库不使用2的基数。它们使用更大的基数，因为CPU具有一次操作多于一位的指令。通常你会使用256的底座（2 ），65536（2 ），4294967296（2 ），或18446744073709551616（2 ）如果您的目标是最大速度和最小尺寸，或如果必须存储精确的小数部分，则为100（每个数字一个字节），10000（每个数字两个字节），1000000000（每个数字四个字节）或10000000000000000000（每个数字八个字节）的基数。

您需要使用类似vector<uint32_t>或vector<uint64_t>作为您的标准，并且一次以32位或64位运行，而不是一次只运行1位。

来源

2012-12-03 22:40:55

因此，使用2^32（例如）base而不是二进制会更快，我理解它是否正确？ –

是的，因为那时你可以一次操作32位。 –

二进制GCD - 太慢算法

回答

相关问题