Thuật toán Euclid mở rộng (Extended Euclidean Algorithm)¶
Trong khi thuật toán Euclid chỉ tính ước chung lớn nhất (GCD) của hai số nguyên $a$ và $b$, phiên bản mở rộng còn tìm cách biểu diễn GCD theo $a$ và $b$, tức là các hệ số $x$ và $y$ sao cho:
Quan trọng cần lưu ý là theo Đẳng thức Bézout, chúng ta luôn có thể tìm thấy một biểu diễn như vậy. Ví dụ, $\gcd(55, 80) = 5$, do đó chúng ta có thể biểu diễn $5$ dưới dạng tổ hợp tuyến tính với các số hạng $55$ và $80$: $55 \cdot 3 + 80 \cdot (-2) = 5$
Một dạng tổng quát hơn của bài toán đó được thảo luận trong bài viết về Phương trình Diophantine tuyến tính. Nó sẽ dựa trên thuật toán này.
Thuật toán (Algorithm)¶
Chúng ta sẽ ký hiệu GCD của $a$ và $b$ là $g$ trong phần này.
Những thay đổi so với thuật toán gốc rất đơn giản. Nếu chúng ta nhớ lại thuật toán, chúng ta có thể thấy rằng thuật toán kết thúc với $b = 0$ và $a = g$. Đối với các tham số này, chúng ta có thể dễ dàng tìm thấy các hệ số, cụ thể là $g \cdot 1 + 0 \cdot 0 = g$.
Bắt đầu từ các hệ số này $(x, y) = (1, 0)$, chúng ta có thể đi ngược lên các lời gọi đệ quy. Tất cả những gì chúng ta cần làm là tìm ra cách các hệ số $x$ và $y$ thay đổi trong quá trình chuyển đổi từ $(a, b)$ sang $(b, a \bmod b)$.
Giả sử chúng ta tìm thấy các hệ số $(x_1, y_1)$ cho $(b, a \bmod b)$:
và chúng ta muốn tìm cặp $(x, y)$ cho $(a, b)$:
Chúng ta có thể biểu diễn $a \bmod b$ như sau:
Thay thế biểu thức này vào phương trình hệ số của $(x_1, y_1)$ ta được:
và sau khi sắp xếp lại các số hạng:
Chúng ta đã tìm thấy các giá trị của $x$ và $y$:
Cài đặt (Implementation)¶
int gcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int x1, y1;
int d = gcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return d;
}
Hàm đệ quy ở trên trả về GCD và các giá trị của hệ số cho x và y (được truyền tham chiếu vào hàm).
Cài đặt này của thuật toán Euclid mở rộng tạo ra kết quả chính xác cho cả các số nguyên âm.
Phiên bản lặp (Iterative version)¶
Cũng có thể viết thuật toán Euclid mở rộng theo cách lặp. Vì nó tránh đệ quy, mã sẽ chạy nhanh hơn một chút so với mã đệ quy.
int gcd(int a, int b, int& x, int& y) {
x = 1, y = 0;
int x1 = 0, y1 = 1, a1 = a, b1 = b;
while (b1) {
int q = a1 / b1;
tie(x, x1) = make_tuple(x1, x - q * x1);
tie(y, y1) = make_tuple(y1, y - q * y1);
tie(a1, b1) = make_tuple(b1, a1 - q * b1);
}
return a1;
}
Nếu bạn nhìn kỹ vào các biến a1 và b1, bạn có thể nhận thấy rằng chúng nhận chính xác các giá trị giống như trong phiên bản lặp của thuật toán Euclid thông thường. Vì vậy, thuật toán ít nhất sẽ tính đúng GCD.
Để biết tại sao thuật toán tính đúng các hệ số, hãy xem xét rằng các bất biến sau đây giữ nguyên tại bất kỳ thời điểm nào (trước khi vòng lặp while bắt đầu và ở cuối mỗi lần lặp):
Gọi các giá trị ở cuối một lần lặp được ký hiệu bằng dấu phẩy ($'$), và giả sử $q = \frac{a_1}{b_1}$. Từ thuật toán Euclid, chúng ta có:
Để bất biến đầu tiên giữ nguyên, điều sau phải đúng:
Tương tự đối với bất biến thứ hai, điều sau phải giữ nguyên:
Bằng cách so sánh các hệ số của $a$ và $b$, các phương trình cập nhật cho mỗi biến có thể được suy ra, đảm bảo rằng các bất biến được duy trì trong suốt thuật toán.
Ở cuối chúng ta biết rằng $a_1$ chứa GCD, vì vậy $x \cdot a + y \cdot b = g$. Điều đó có nghĩa là chúng ta đã tìm thấy các hệ số cần thiết.
Bạn thậm chí có thể tối ưu hóa mã hơn nữa, và loại bỏ biến $a_1$ và $b_1$ khỏi mã, và chỉ sử dụng lại $a$ và $b$. Tuy nhiên nếu bạn làm vậy, bạn sẽ mất khả năng lập luận về các bất biến.