Chưa đầy một tuần, Anatoly Karatsuba tìm ra cách nhân số lớn nhanh hơn cách nhân đặt tính, bác bỏ phỏng đoán của Kolmogorov

19/10/2026 · VietTechies · Biên tập

Mùa thu năm 1960, Andrey Kolmogorov, một trong những nhà toán học lớn của thế kỷ 20, nêu một phỏng đoán về phép nhân tại buổi thảo luận chuyên đề do ông chủ trì ở Đại học Quốc gia Moskva. Ông cho rằng nhân hai số có n chữ số cần số bước tính toán cỡ n², như cách nhân đặt tính, và không có phương pháp nào tốt hơn về căn bản. Chưa đầy một tuần sau, Anatoly Karatsuba, sinh viên toán 23 tuổi, tìm ra một phương pháp nhân nhanh hơn cách nhân đặt tính — ngày nay gọi là thuật toán Karatsuba.

Theo lời Karatsuba kể, ông đang tìm cách chứng minh một cận dưới — tức phép nhân phải cần ít nhất một số bước nhất định, kiểu giới hạn mà Kolmogorov đã phỏng đoán. Thuật toán ông định dùng cho chứng minh ấy hóa ra chỉ cần khoảng n^1,58 bước. Ông mang kết quả đến gặp Kolmogorov.

Năm 1995, Karatsuba nhớ lại rằng Kolmogorov “rất kích động vì điều này trái với phỏng đoán rất hợp lý của ông”. Tại buổi thảo luận chuyên đề tiếp theo, chính Kolmogorov trình bày phương pháp ấy với những người tham dự, “và đến đây thì chuỗi thảo luận chuyên đề kết thúc”.

Ngày nay, thuật toán ấy chạy bên trong bản triển khai tiêu chuẩn của Python mỗi khi hai số nguyên đủ lớn được nhân với nhau. Đây cũng là phương pháp đầu tiên trong chuỗi phương pháp nhân nhanh hơn, một hướng nghiên cứu đạt cột mốc mới vào năm 2019.

Phỏng đoán n² của Kolmogorov nói gì

Cách nhân đặt tính nhân từng chữ số của số này với từng chữ số của số kia. Hai số có bốn chữ số cần 16 phép nhân một chữ số; khi độ dài của cả hai số tăng gấp đôi, khối lượng tính toán tăng gấp bốn. Phỏng đoán của Kolmogorov cho rằng mọi phương pháp đều có mức tăng n² như vậy.

Có thể Kolmogorov đã nêu phỏng đoán này trước năm 1960. David Harvey, một trong hai nhà toán học đứng sau kết quả năm 2019, viết rằng Kolmogorov đưa ra phỏng đoán “vào khoảng năm 1956”; còn theo lời Karatsuba, Kolmogorov nêu phỏng đoán tại buổi thảo luận chuyên đề năm 1960. Những chi tiết về tuần lễ ấy, gồm phản ứng kích động của Kolmogorov và việc chuỗi thảo luận chuyên đề kết thúc, đều đến từ lời kể của chính Karatsuba, công bố 35 năm sau.

Ba phép nhân thay vì bốn

Mẹo của Karatsuba có thể minh họa bằng hai số có hai chữ số. Để nhân 12 với 34, cách nhân đặt tính cần bốn phép nhân một chữ số: 1 × 3, 1 × 4, 2 × 3 và 2 × 4. Phương pháp của Karatsuba cần ba:

1 × 3 = 3, tích của hai chữ số đầu;
2 × 4 = 8, tích của hai chữ số cuối;
(1 + 2) × (3 + 4) = 3 × 7 = 21, tích của hai tổng chữ số.

Lấy tích thứ ba trừ hai tích đầu, ta còn 21 − 3 − 8 = 10, đúng bằng số hạng ở giữa, 1 × 4 + 2 × 3. Ghép các phần lại sẽ ra đáp án: 3 trăm, 10 chục và 8 đơn vị, hay 300 + 100 + 8 = 408.

Với số có hai chữ số, bớt được một trong bốn phép nhân có vẻ chẳng đáng kể. Mẹo này có giá trị vì vẫn có thể chia các số dài theo cùng cách đó. Tách mỗi số thành nửa chứa các chữ số hàng cao và nửa chứa các chữ số hàng thấp, ba tích cần tính sẽ trở thành phép nhân các số chỉ dài bằng một nửa. Mỗi số ấy lại có thể tiếp tục được chia theo cùng cách.

Với các số dài, những phép cộng và trừ thêm vào tốn ít công tính toán so với các phép nhân mà chúng giúp tiết kiệm. Theo cách đếm của Harvey, hai số có bốn chữ số cần chín phép nhân một chữ số thay vì 16; với các số có một nghìn chữ số, số phép nhân giảm khoảng 17 lần. Khi độ dài của cả hai số tăng gấp đôi, số phép nhân một chữ số tăng gấp ba thay vì gấp bốn, nên chi phí tính toán tăng theo n mũ log₂ 3 (số mũ xấp xỉ 1,58), thay vì n².

Ai viết bài báo Karatsuba–Ofman năm 1962

Phương pháp này xuất hiện năm 1962 trên Doklady Akademii Nauk SSSR, kỷ yếu của Viện Hàn lâm Khoa học Liên Xô, dưới một nhan đề tiếng Nga có nghĩa là “Nhân các số có nhiều chữ số bằng máy tính tự động”. Dòng tên tác giả ghi A. Karatsuba và Yu. Ofman.

Theo những bản thuật lại dựa trên hồi ức năm 1995 của Karatsuba, chính Kolmogorov đã viết bài báo. Bài báo gồm hai kết quả riêng biệt về phép nhân — thuật toán của Karatsuba và một kết quả của Yuri Ofman — và Karatsuba chỉ biết đến bài báo khi nhận được các bản in riêng từ nhà xuất bản. Một số bài báo vẫn gọi phương pháp này là thuật toán Karatsuba–Ofman, nhưng theo những lời kể ấy, mẹo dùng ba phép nhân là của Karatsuba.

Những bước tiến sau thuật toán Karatsuba

Khi giới hạn n² đã bị phá vỡ, những người khác tiếp tục tiến xa hơn. Andrei Toom vào năm 1963 và Stephen Cook trong luận án tại Harvard năm 1966 đã mở rộng cách chia từ hai phần sang nhiều phần hơn, tạo nên họ phương pháp ngày nay gọi là phép nhân Toom–Cook. Năm 1971, Arnold Schönhage và Volker Strassen dùng phép biến đổi Fourier nhanh để đạt số bước n × log n × log(log n), rồi phỏng đoán rằng có thể đạt n × log n.

Harvey và Joris van der Hoeven công bố một thuật toán n × log n ngày 18 tháng 3 năm 2019; bài báo được đăng trên Annals of Mathematics năm 2021. Harvey viết rằng chứng minh ấy “chỉ áp dụng được cho những số lớn đến mức phi lý”.

Thuật toán Karatsuba đang chạy ở đâu

Phương pháp Karatsuba nằm trong phần mã xử lý số nguyên của các ngôn ngữ phổ biến, nhưng chỉ được dùng khi vượt một ngưỡng nhất định. Mã nguồn CPython, bản triển khai tiêu chuẩn của Python, cho biết chương trình dùng “thuật toán nhân đặt tính O(N**2), trừ khi cả hai toán hạng đều có nhiều hơn KARATSUBA_CUTOFF chữ số”, và đặt ngưỡng đó ở 70 chữ số theo cách biểu diễn nội bộ.

Lớp BigInteger của Java, dùng để xử lý các số nguyên lớn hơn nhiều so với khả năng của những kiểu số nguyên có sẵn trong Java, đã dùng Karatsuba từ Java 8. Lớp này vẫn dùng cách nhân đặt tính khi một trong hai số ngắn hơn 80 từ máy, mỗi từ 32 bit; dùng Karatsuba khi cả hai số đều có ít nhất 80 từ máy và đều dưới 240; rồi chuyển sang Toom–Cook chia ba phần khi vượt ngưỡng đó. Theo chú thích trong mã, ngưỡng 80 “cho kết quả tốt qua thực nghiệm”, và mã mô tả Karatsuba là “hiệu quả hơn với các số lớn” so với cách nhân đặt tính. Với các số ngắn, cả hai ngôn ngữ đều giữ phương pháp cũ vì Karatsuba “có một phần chi phí phụ”, như mã Java ghi chú.

Phỏng đoán n² cho thấy gì về những giới hạn chưa được chứng minh

Theo lời Karatsuba, phỏng đoán của Kolmogorov rất hợp lý. Harvey diễn đạt như sau: “Kolmogorov cảm thấy rằng nếu có một cách tính tắt thì chắc hẳn người ta đã tìm ra rồi.” Điều phỏng đoán còn thiếu là một chứng minh rằng không phương pháp nào khác có thể làm tốt hơn. Và chính trong lúc tìm cách đưa ra chứng minh ấy, Karatsuba đã tìm thấy phương pháp nhanh hơn.

Bản thân mẹo này là một cách làm có thể áp dụng lại: khi một phép toán chiếm phần lớn chi phí tính toán, một đẳng thức đại số có thể thay nó bằng những phép toán ít tốn kém hơn. Karatsuba dùng thêm vài phép cộng để bớt một phép nhân, và phần tiết kiệm ấy cứ nhân lên qua mỗi cấp chia nhỏ.

Một giới hạn mới chỉ được quan sát, chưa được chứng minh, chỉ mô tả những phương pháp mà người ta đã thử cho đến lúc đó, chứ không phải mọi phương pháp có thể tồn tại.

Chuỗi thảo luận chuyên đề của Kolmogorov kết thúc ngay tại buổi ông trình bày phương pháp ấy. Còn phương pháp thì vẫn tiếp tục: hơn sáu thập niên sau, CPython vẫn chuyển sang cách chia của Karatsuba khi cả hai số vượt 70 chữ số theo cách biểu diễn nội bộ.

Bài liên quan

Đọc bằng ngôn ngữ khác: English