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

Thuật toán Stein dùng để tìm GCD của các số vì nó tính ước chung lớn nhất của hai số nguyên không âm. Nó thay thế phép chia bằng dịch bit, so sánh và trừ. Nếu cả a và b đều là 0, gcd là 0: gcd(0, 0) = 0. Thuật toán GCD(a,b) như sau:

Thuật toán

BẮT ĐẦU
    Bước-1: Kiểm tra nếu cả a và b đều là 0, gcd = 0.
    Bước-2: Khi đó gcd(a, 0) = a và gcd(0, b) = b vì mọi số đều chia hết 0.
    Bước-3: Kiểm tra nếu a và b đều chẵn, gcd(a, b) = 2*gcd(a/2, b/2) vì 2 là ước chung. Nhân 2 có thể dùng dịch bit.
    Bước-4: Nếu a chẵn b lẻ, gcd(a, b) = gcd(a/2, b). Tương tự a lẻ b chẵn thì gcd(a, b) = gcd(a, b/2). Vì 2 không phải ước chung.
    Bước-5: Nếu cả a và b đều lẻ, gcd(a, b) = gcd(|a-b|/2, b). Lưu ý hiệu hai số lẻ là số chẵn.
    Bước-6: Lặp lại bước 3-5 cho đến a = b, hoặc a = 0.
KẾT THÚC

Theo thuật toán trên tính GCD 2 số, mã C++ sau được viết:

Ví dụ mã C++

#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); // Hoán đổi u và v.
        y = (y - x);
    } while (y != 0);
    return x << k;
}

int main(){
    int a = 24, b = 18;
    printf("GCD tính được của (24,18) là= %d\n", funGCD(a, b));
    return 0;
}

Đầu ra

Cuối cùng, GCD của hai số 24 và 18 được tính là 6 bằng thuật toán Stein như sau:

GCD tính được của (24,18) là= 6