Thuật toán Stein để tìm GCD trong C ++

Thuật toán của Stein được sử dụng để khám phá GCD của các số khi nó tính ước số chính quy tốt nhất của hai số nguyên không âm. Nó thay thế phép chia bằng các chuyển động toán học, các kỳ thi và phép trừ. Trong trường hợp cả a và b bằng 0, gcd bằng 0 gcd (0, 0) =0. Thuật toán cho GCD (a, b) như sau;

Thuật toán

START
   Step-1: check If both a and b are 0, gcd is zero gcd(0, 0) = 0.
   Step-2: then gcd(a, 0) = a and gcd(0, b) = b because everything divides 0.
   Step-3: check If a and b are both even, gcd(a, b) = 2*gcd(a/2, b/2) because 2 is a common divisor. Multiplication with 2 can be done with a bitwise shift operator.
   Step-4: If a is even and b is odd, gcd(a, b) = gcd(a/2, b). Similarly, if a is odd and b is even, then gcd(a, b) = gcd(a, b/2). It is because 2 is not a common divisor.
   Step-5: If both a and b are odd, then gcd(a, b) = gcd(|a-b|/2, b). Note that difference of two odd numbers is even
   Step-6: Repeat steps 3–5 until a = b, or until a = 0.
END

Theo quan điểm của thuật toán trên để tính toán GCD của 2 số, mã C ++ sau đây được viết dưới dạng;

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int funGCD(int x, int y){
   if (x == 0)
      return y;
   if (y == 0)
      return x;
   int k;
   for (k = 0; ((x | y) && 1) == 0; ++k){
      x >>= 1;
      y >>= 1;
   }
   while ((x > 1) == 0)
      x >>= 1;
   do {
      while ((y > 1) == 0)
         y >>= 1;
         if (x > y)
            swap(x, y); // Swap u and v.
         y = (y - x);
   }
   while (y != 0);
      return x << k;
}
int main(){
   int a = 24, b = 18;
   printf("Calculated GCD of numbers (24,18) is= %d\n", funGCD(a, b));
   return 0;
}

Đầu ra

Cuối cùng, GCD của hai số được cung cấp 24 và 18 được tính bằng 6 bằng cách áp dụng Thuật toán của Stein như sau;

Calculated GCD of numbers (24,18) is= 6