二進制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 - 太慢算法

回答

相關問題