바이너리 GCD - 너무 느린 알고리즘

Question

위키 피 디아 (http://en.wikipedia.org/wiki/Binary_GCD_algorithm)에 따르면 나는 bignums (최대 5000 자리) 용 바이너리 GCD를 작성하려고했습니다.

내 GCD 자체는 다음과 같습니다 : I 이진 알고리즘의 속도를 (개선하기 위해 어떤 장소가 표시되지 않습니다

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]; 
      } 
     } 
    } 
} 

:

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; 
} 

가 나는 또한 자신의 비트 세트 공제 기능을 사용하고 있습니다 GCD 자체가 빠름).하지만 내 프로그램이 너무 느리다는 의견을 받고 있습니다.

Answer 1

bignum을 기본 2 (이진수) 배열로 표시했습니다.

실제 bignum 라이브러리는 2의 밑수를 사용하지 않습니다. CPU는 한 번에 두 비트 이상을 조작하는 명령을 가지고 있기 때문에 더 큰 기본을 사용합니다. 일반적으로 당신은 당신의 목표는 최대 속도와 최소 크기, 또는 경우 256의 기본 (2 ⁸), 65536 (2 ¹⁶), 4294967296 (2 ³²), 또는 18,446,744,073,709,551,616 (2 ⁶⁴)를 사용하는 것 정확한 십진수를 저장해야하는 경우에는 100 (한 자릿수 당 1 바이트), 10000 (한 자릿수 당 2 바이트), 1000000000 (한 자릿수 당 4 바이트) 또는 10000000000000000000 (한 자릿수 당 8 바이트)의 기준이됩니다.

귀하의 bignum으로 vector<uint32_t> 또는 vector<uint64_t>과 같은 것을 사용해야하며 한 번에 1 비트 대신 32 비트 또는 64 비트를 한꺼번에 사용해야합니다.