Cách nhân nhanh nhất? Vẫn chưa rõ, nhưng chúng ta đang tiến gần hơn

Phép nhân hiện diện khắp nơi trong điện toán — mã hóa, AI, xử lý âm thanh, v.v. Và trong nhiều thập kỷ, các nhà toán học tin rằng thuật toán xếp chồng ở trường phổ thông (O(n²)) là nhanh nhất có thể. Rồi một sinh viên 23 tuổi đã phá vỡ niềm tin đó, châm ngòi cho một cuộc đua vẫn tiếp diễn đến ngày nay.

Nút thắt của phép xếp chồng

Thuật toán cổ điển nhân mọi chữ số của số này với mọi chữ số của số kia. Nhân đôi số chữ số sẽ tăng gấp bốn lần khối lượng công việc — O(n²). Với số có hàng nghìn chữ số, đó là một triệu phép nhân một chữ số. Chấp nhận được với số nhỏ, nhưng là cơn ác mộng ở quy mô lớn.

Mẹo của Karatsuba: Đánh đổi phép nhân lấy phép cộng

Năm 1960, Anatoly Karatsuba nhận ra rằng bạn có thể thay thế một số phép nhân bằng các phép cộng rẻ hơn. Với số có hai chữ số, thay vì bốn phép nhân, bạn chỉ cần ba, cộng thêm vài phép cộng. Áp dụng đệ quy, điều này giảm độ phức tạp xuống O(n^1.585). Python ngày nay sử dụng thuật toán này cho các số trên khoảng 630 chữ số thập phân.

Thuật toán Harvey–van der Hoeven

Năm 2019, David Harvey và Joris van der Hoeven công bố một thuật toán chạy với độ phức tạp O(n log n) — gần như nhanh bằng việc chỉ đọc các số. Nhưng có một điểm hạn chế: nó chỉ vượt trội hơn Karatsuba đối với các số lớn đến mức thiên văn, không bao giờ xuất hiện trong thực tế. Đây là một thuật toán thiên hà: đẹp về mặt lý thuyết, nhưng vô dụng trong thực tiễn.

Điều gì tiếp theo?

Giới hạn O(n log n) gần như tối ưu một cách hấp dẫn, nhưng chưa ai chứng minh được đó là mức sàn. Câu hỏi vẫn còn bỏ ngỏ — và mỗi hiểu biết mới đều đẩy lùi giới hạn về những gì máy tính có thể làm hiệu quả.