迭代實現Euclid算法用C

Question

我有使用迭代，不遞歸2種實現Euclid算法的。 一種是常見的：

void myXEuclid(int a, int b) 
{ 
    int prevx = 1, x = 0; 
    int prevy = 0, y = 1; 
    int q, r; 

    while (b) 
    { 
     q = a/b; 
     r = a % b; 

     int tmp = x; 
     x = prevx - q * x; 
     prevx = tmp; 

     tmp = y; 
     y = prevy - q * y; 
     prevy = tmp; 

     a = b; 
     b = r; 
    } 
    printf("prevx = %d, prevy = %d\n", prevx, prevy); 
} 

我真的不明白的地方的初始化來自：

int prevx = 1, x = 0; 
int prevy = 0, y = 1; 

不管怎樣，我還是可以從上面的代碼片段正確的答案。但是在RSA算法中，當我做A * B mod n = 1時，我必須確保B是最小的非負數。因此，這裏出現的下一個混亂的實施歐幾里德的算法，也使用迭代：

int Euc(int A, int B) 
{ 
    int a = A, b = B; 
    int quotient, remainder, lastY; 
    int x = 0, y = 1; 

    int X = 1, Y = 1; 

    while (a) 
    { 
     quotient = b/a; 
     remainder = b % a; 
     b = a; 
     a = remainder; 
     lastY = y; 
     y *= quotient; 

     if (X == Y) 
     { 
      if (x >= y) 
      { 
       y = x - y; 
      } 
      else 
      { 
       y = y - x; 
       Y = 0; 
      } 
     } 
     else 
     { 
      y = x + y; 
      X = 1 - X; 
      Y = 1 - Y; 
     } 

     x = lastY; 
    } 

    if (X == 0) 
    { 
     x = B - x; 
    } 

    return x; 
} 

我不知道是什麼資本變量X和Y指何地，同樣，他們的初始化從何而來。但是上面的函數可以返回符合方程A * x mod B = 1的x，並且它是最小的非負函數。

我能理解遞歸之一。但不是迭代的。說實話，我好幾天沒睡好。

我不是來自講英語的國家。所以，如果你能幫助我，請詳細解釋。謝謝。留言Merci。

Answer 1

在這裏有點用C闡述約GCD算法和不同的實現解釋/ C++

http://512algorithms.blogspot.co.il/