Lịch sử của thuật toán Euclid

Thuật toán Euclid là một trong những thuật toán cổ nhất được biết đến, từ khi nó xuất hiện trong cuốn Euclid’s Elements khoảng năm 300 trước công nguyên. Euclid khởi đầu đã trình bày rõ ràng vấn đề về phương diện hình học, như vấn đề tìm ra một thước đo chung cho độ dài hai đường thẳng, và thuật toán của ông đã xử lý bằng cách lặp lại phép trừ đoạn dài hơn cho đoạn ngắn hơn. Tuy nhiên, thuật toán đã hầu như không được phát hiện ra bởi Euclid và nó đã có thể được biết đến sớm hơn 200 năm. Nó cũng đã được biết đến bởi Eudoxus of Cnidus (khoảng năm 375 trước công nguyên) và Aristotle (khoảng năm 330 trước công nguyên).

Mô tả thuật toán

Cho 2 số tự nhiên a và b, không đồng thời bằng 0: kiểm tra nếu b bằng 0, thì a là ước chung lớn nhất (UCLN). Nếu không, lặp lại xử lý sử dụng b và phần còn lại sau khi lấy a chia cho b. Phần còn lại sau khi chia a cho b thường được viết là a mod b.

Các thuật toán này có thể sử dụng trong bất kì hoàn cảnh nào khi còn phần dư. Điều này bao gồm các nhóm đa thức như nhóm số nguyên Gauxơ. Thuật toán không chỉ áp dụng cho số tự nhiên mà còn áp dụng cho nhiều trường hợp tổng quát khác sẽ được mô tả chi tiết sau.

Sử dụng đệ quy

Sử dụng đệ quy, thuật toán có thể phát biểu như sau:

Sử dụng tính lặp lại

Thuật toán Euclid mở rộng

Bằng cách theo dõi thương tìm được trong suốt thuật toán, ta có thể xác định các số nguyên p và q với ap+bq=gcd(a,b). Điều này được biết đến như là thuật toán Euclid mở rộng.

Thuật toán nguyên bản

Thuật toán nguyên bản được mô tả bởi Euclid đã giải quyết vấn đề về phương diện hình học, sử dụng lặp phép trừ đúng hơn là phép mod

Chú ý rằng trong khi b có thể là 0 thì a không thể là 0, nếu không nó sẽ trở thành vòng lặp vô hạn. Thuật toán này không yêu cầu 1 biến phụ t.

Một ví dụ

Giả sử tính toán UCLN của 1071 và 1029 là 21. Nhắc lại “mod” nghĩa là phần dư sau phép chia.

Với thuật toán đệ quy sau:

Với thuật toán lặp:

Nhận xét rằng a b trong mỗi lần gọi. Nếu ban đầu, b > a, không có vấn đề gì, trước hết ta chỉ cần hoán đổi 2 giá trị cho nhau, sau đó các bước hoàn toàn tương tự.

Chứng minh

Giả thiết a và b là các số tự nhiên mà UCLN phải xác định. Bây giờ, giả thiết b > 0, và phần dư của phép chia a cho b là r. Do đó a = qb + r với q là thương của phép chia.

Bất kì phép chia thông thường nào của a và b cũng cho một số dư r. Để thấy sự đúng đắn đó, ta coi r có thể được viết là r = a – qb. Bây giờ nếu có một ước chung d của a và b, như vậy a = sd và b = td, khi đó r = (s-qt)d, ta có thể thấy rằng r chia hết cho d.

Những phân tích trên là đúng cho bất kì số chia d nào, vì thế, UCLN của a và b cũng là UCLN của b và r. Do đó nếu ta tiếp tục tìm UCLN với các số b và r. Khi giá trị tuyệt đối của r nhỏ hơn b, ta sẽ tiến tới rn+1 = 0 sau nhiều bước.

Thời gian chạy

Khi phân tích thời gian chạy của thuật toán Euclid, ta bỏ qua các phép chia có đầu và là 2 số Fibonacci liên tiếp (vì tỉ số của chúng hội tụ rất chậm …), và trường hợp tồi nhất O(n) phép chia, trong đó n là số số đầu vào. Độ phức tạp của thuật toán trên thực tế là O(n²). Lý do là, phép chia 2 số n-bit mất O(n(m+1)) thời gian, m là độ dài thương số. Lưu ý rằng việc tính toán UCLN gcd(a,b), a và b là n bit, a₀,…,a_k là thứ tự các số được đưa ra bởi thuật toán và n0,…,nk là độ dài của chúng. Khi k = O(n) và thời gian chạy bị hạn chế bởi:

Điều này tốt hơn nhiều so với thuật toán Euclid cổ điển, phép toán module được thực hiện hiệu quả sử dụng phép trừ lặp với O(2n) bước. Bởi vậy, dạng này của thuật toán yêu cầu O(2nn) thời gian cho số có n số, hoặc O(mlogm) thời gian cho số m. Thuật toán Euclid được sử dụng rộng rãi trên thực tế, đặc biệt với những số nhỏ, do sự đơn giản của nó. Một thuật toán lựa chọn , thuật toán GCD nhị phân (binary GCD algorithm), khai thác sự biểu diễn nhị phân sử dụng cho máy tính để loại bỏ bớt phép chia, và vì thế tăng hiệu suất tính toán.

Có những thuật toán phức tạp hơn có thể giảm thời gian chạy xuống O(n(log_n)²(loglog_n)).

Mối liên quan với continued fractions

Các thương số xuất hiện khi thuật toán Euclid được áp dụng cho các đầu vào a và b là những số xuất hiện hoàn toàn chính xác trong sự biểu diễn liên phân số a/b. Ví dụ a = 1071 và b = 1029 được sử dụng ở trên. Ở đây chỉ tính toán với những thương số thấy rõ nhất:

1071 = 1029 x 1 + 42

1029 = 42 x 24 + 21

42 = 21 x 2 + 0

Theo đó,

Phương thức này áp dụng cho các đầu vào tùy ý a và b (≠ 0), nếu a/b là số vô tỉ thì thuật toán Euclid không kết thúc, nhưng thứ tự tính toán của thương số vẫn biểu diễn liên phân số a/b.

Các thương số 1,24,2 là các hình vuông được lồng vào một hình chữ nhật R có chiều dài là 1071 và chiều rộng là 1029 theo cách sau:

(1) Có 1 hình vuông 1029x1029 trong R đã được cắt xén còn lại hình chữ nhật R1 42x1029

(2) Có 24 hình vuông 42x42 trong R1 đã được cắt xén còn lại hình chữ nhật R2 21x42

(3) Có 2 hình vuông 21x21 trong R2, vừa đủ.

Thuật toán Euclid trực quan “các hình vuông” ứng dụng cho một hình chữ nhật R bất kì. Nếu chiều dài/chiều rộng của R là một số vô tỉ, thì thuật toán Euclid trực quan mở rộng cho một liên phân số trực quan.

Khái quát về phạm vi của thuật toán Euclid

Thuật toán Euclid có thể áp dụng cho các nhóm số khác, không chỉ cho số tự nhiên. Trường hợp cá biệt là các số nguyên Gaussian và các nhóm đa thức. Một ví dụ, xem xét nhóm đa thức với hệ số hữu tỷ. Trong nhóm này, phép chia với phần dư được thực hiện sử dụng phép chia đa thức.

Ta tính UCLN của

x⁴ − 4x³ + 4x² − 3x + 14 = (x² − 5x + 7)(x² + x + 2)

và

x⁴ + 8x³ + 12x² + 17x + 6 = (x² + 7x + 3)(x² + x + 2)

Thuật toán đưa ra các giá trị sau:

School@net (Theo Nguyễn Thị Xuân)