Binary GCD: Tối ưu hóa thuật toán tính ước chung lớn nhất nhanh hơn gấp đôi std::gcd

Trong khoa học máy tính, việc tìm ước chung lớn nhất (Greatest Common Divisor - GCD) của hai số nguyên là một bài toán cơ bản. Hầu hết các lập trình viên đều sử dụng thuật toán Euclid hoặc hàm std::gcd có sẵn trong C++. Tuy nhiên, có một phương pháp khác ít được phổ biến hơn trong sách giáo khoa nhưng lại mang lại hiệu suất vượt trội: thuật toán Binary GCD.

Bài viết này sẽ đi sâu vào lý do tại sao std::gcd chưa phải là tối ưu và cách chúng ta có thể xây dựng một phiên bản nhanh gấp đôi bằng cách hiểu rõ về phần cứng.

Thuật toán Euclid và vấn đề về hiệu suất

Thuật toán Euclid dựa trên nguyên tắc đơn giản: gcd(a, b) = gcd(b, a % b). Quá trình này lặp lại cho khi b bằng 0. Mặc dù có độ phức tạp thời gian là logarit, nhưng vấn đề nằm ở chỗ nó được thực hiện như thế nào trên phần cứng.

Khi biên dịch thuật toán này ra assembly, lệnh tốn nhiều thời gian nhất là idiv (phép chia nguyên). Trên các bộ vi xử lý hiện đại, kể cả x86, phép chia nguyên là một thao tác cực kỳ chậm, thường tốn hàng chục chu kỳ xung nhịp (cycles). Khi chạy công cụ phân tích hiệu năng perf, bạn sẽ thấy phần lớn thời gian CPU bị tiêu hao tại dòng lệnh này.

Biểu đồ minh họa thuật toán Euclid

Giải pháp thay thế: Binary GCD

Thuật toán Binary GCD (còn gọi là thuật toán Stein) được phát hiện từ thời cổ đại nhưng được Josef Stein tái khám phá vào năm 1967 để sử dụng trên các máy tính không có lệnh chia hoặc có lệnh chia rất chậm.

Thay vì dùng phép chia và modulo, thuật toán này chỉ dựa vào các thao tác bitwise: dịch chuyển (shift), so sánh và trừ. Các thao tác này thường chỉ tốn 1 chu kỳ trên CPU. Thuật toán dựa trên các nhận thức sau:

• Nếu cả a và b đều chẵn, thì gcd(a, b) = 2 * gcd(a/2, b/2).
• Nếu a chẵn và b lẻ, thì gcd(a, b) = gcd(a/2, b).
• Nếu cả a và b đều lẻ, thì gcd(a, b) = gcd(|a-b|, min(a, b)).

Tối ưu hóa triển khai

Nếu chuyển đổi trực tiếp các quy tắc trên thành code C++ với nhiều câu lệnh if-else để kiểm tra chẵn/lẻ, hiệu suất thực tế thậm chí còn chậm hơn std::gcd do chi phí rẽ nhánh (branching). Để đạt được tốc độ tối đa, chúng ta cần áp dụng một số kỹ thuật tối ưu hóa sâu.

Thứ nhất, thay vì chia cho 2 nhiều lần, chúng ta sử dụng hàm __builtin_ctz (count trailing zeros) có sẵn trên các CPU hiện đại. Hàm này đếm số lượng bit 0 ở cuối số nguyên, cho phép chúng ta dịch chuyển phải (right-shift) một lần bằng lũy thừa lớn nhất của 2.

Thứ hai, chúng ta đơn giản hóa vòng lặp chính để loại bỏ các rẽ nhánh không cần thiết. Bằng cách tận dụng tính chất của các số chẵn và lẻ sau mỗi phép trừ, vòng lặp có thể được viết lại gọn gàng hơn.

Đây là đoạn code đã được tối ưu hóa:

int gcd(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;
    int az = __builtin_ctz(a);
    int bz = __builtin_ctz(b);
    int shift = std::min(az, bz);
    b >>= bz;
    while (a != 0) {
        a >>= az;
        int diff = b - a;
        az = __builtin_ctz(diff);
        b = std::min(a, b);
        a = std::abs(diff);
    }
    return b << shift;
}

Phân tích đồ thị phụ thuộc

Để hiểu tại sao phiên bản này nhanh hơn, chúng ta cần nhìn vào đồ thị phụ thuộc (dependency graph) của các lệnh trong vòng lặp. Các bộ vi xử lý hiện đại có thể thực thi nhiều lệnh song song, nhưng tốc độ tổng thể bị giới hạn bởi "đường đi quan trọng" (critical path) - tổng độ trễ của các lệnh phụ thuộc tuần tự.

Trong đoạn code tối ưu hóa, chúng ta đã giảm thiểu độ trễ này bằng cách tính toán __builtin_ctz trực tiếp trên hiệu số diff mà không cần chờ kết quả của phép lấy giá trị tuyệt đối.

Đồ thị phụ thuộc ban đầu

Bằng cách nhận ra rằng số âm chia hết cho $2^k$ vẫn có $k$ số 0 ở cuối biểu diễn nhị phân, chúng ta không cần đợi tính abs(diff) trước khi gọi ctz. Điều này rút ngắn đồ thị phụ thuộc như sau:

Đồ thị phụ thuộc sau khi tối ưu

Kết quả

Phiên bản cuối cùng của thuật toán Binary GCD chạy trong khoảng 91ns, nhanh hơn khoảng 2 lần so với std::gcd của C++ tiêu chuẩn. Đây là một minh chứng rõ ràng cho việc hiểu rõ kiến trúc phần cứng (như tốc độ của các lệnh assembly) có thể giúp các lập trình viên viết ra phần mềm hiệu quả hơn nhiều so với việc chỉ dựa vào các thuật toán sách giáo khoa.