Nguồn: Algorithmica HPC
Tóm tắt
Binary GCD (hay Stein’s algorithm) là biến thể hiệu quả của thuật toán Euclid để tính ước chung lớn nhất, tận dụng các phép tính bit thay vì phép chia modulo tốn kém. Thay vì dùng a % b, thuật toán sử dụng phép dịch bit và phép trừ — những phép tính có độ trễ thấp hơn nhiều trên CPU hiện đại.
Bài viết trên Algorithmica (dự án giáo dục HPC của Sergey Slotin) trình bày chi tiết các bước tối ưu hóa: loại bỏ số chẵn bằng cách dịch bit, tránh phân nhánh không cần thiết, và cách CPU hiện đại xử lý các nhánh dự đoán. Phân tích độ phức tạp cho thấy Binary GCD có số bước lặp tương đương Euclid nhưng mỗi bước rẻ hơn đáng kể về mặt phần cứng.
Đây là một phần của cuốn sách giáo khoa mở về High Performance Computing, tập trung vào việc viết mã C/C++ khai thác tối đa kiến trúc CPU hiện đại. Các kỹ thuật được trình bày có ứng dụng thực tiễn trong cryptography, số học số nguyên lớn, và các hệ thống đòi hỏi hiệu năng cao.