Использование алгоритма Евклида для поиска GCF (GCD)

Question

Я пытаюсь написать функцию, чтобы найти gcd из двух чисел, используя алгоритм Евклида, который я нашел here.

Из большего числа вычитайте меньшее количество столько раз, сколько сможете, пока не получите число, меньшее, чем небольшое число. (или без получения отрицательного ответа) Теперь, используя исходное небольшое число и результат, меньшее число, повторите процесс. Повторяйте это до тех пор, пока последний результат не будет равен нулю, а GCF будет последним результатом небольшого числа. Также см. Наш Калькулятор Алгоритмов Евклида.
Пример: Найти GCF (18, 27)
27 - 18 = 9
18 - 9 = 9
9 - 9 = 0
Таким образом, наибольший общий делитель 18 и 27: 9, наименьший результат, который мы имели, прежде чем мы достигли 0.

Следуя этим инструкциям, я написал функцию:

int hcf(int a, int b) 
{ 
    int small = (a < b)? a : b; 
    int big = (a > b)? a : b; 
    int res; 
    int gcf; 

    cout << "small = " << small << "\n"; 
    cout << "big = " << big << "\n"; 

    while ((res = big - small) > small && res > 0) { 
      cout << "res = " << res << "\n"; 
    } 
    while ((gcf = small - res) > 0) { 
     cout << "gcf = " << gcf << "\n"; 
    } 


    return gcf; 
} 

Однако второй цикл, кажется, б бесконечно. Может ли кто-нибудь объяснить, почему?

Я знаю, что на самом деле сайт показывает код (PHP), но я пытаюсь написать этот код, используя только инструкции, которые они дают.

Answer 1

Конечно, этот цикл бесконечен:

while ((gcf = small - res) > 0) { 
    cout << "gcf = " << gcf << "\n"; 
} 

small и res не меняются в цикле, так gcf не либо. Этот цикл эквивалентен:

gcf = small - res; 
while (gcf > 0) { 
    cout << "gcf = " << gcf << "\n"; 
} 

который, вероятно, более ясен.

Я бы порт, алгоритм кодирования следующим образом:

int gcd(int a, int b) { 
    while (a != b) { 
     if (a > b) { 
      a -= b; 
     } 
     else { 
      b -= a; 
     } 
    } 
    return a; 
} 

Хотя обычно gcd реализуется с использованием мод, так как это намного быстрее:

int gcd(int a, int b) { 
    return (b == 0) ? a : gcd(b, a % b); 
}