Gửi lúc: 03/05/2019 16:11:35
Bookmark and Share

Thuật toán mới giúp tăng tốc độ nhân các số lớn

Hai nhà toán học từ Úc và Pháp vừa tìm ra một cách mới để nhân các số lớn nhanh hơn, giúp giải quyết một bài toán đã làm đau đầu các nhà toán học trong gần nửa thế kỷ.



Để nhân hai số lớn, chúng ta phải nhân từng chữ số của số thứ nhất với từng chữ số của só thứ hai. Khi nhân hai số mà mỗi số có N chữ số, chúng ta sẽ phải thực hiện N2 (hay N x N) phép nhân. Phương pháp này đã được sử dụng từ khoảng 4000 năm nay, từ thời của những người Babylon và Ai Cập cổ đại. Năm 1956, nhà toán học Liên Xô Kolmogorov phỏng đoán rằng đó là cách tốt nhất để nhân hai số. Ông cho rằng nếu có cách làm tốt hơn thì con người đã tìm ra nó. Nhưng chỉ vài năm sau, phỏng đoán của Kolmogorov đã được chứng minh là sai.

Năm 1960, Anatoly Karatsuba, một sinh viên toán 23 tuổi ở Nga, đã tìm ra thủ thuật đại số giúp giảm số phép nhân cần thực hiện. Để nhân hai số có 4 chữ số, thay vì phải thực hiện 4 x 4 = 16 phép nhân, chúng ta chỉ cần thực hiện 9 phép nhân khi sử dụng phương pháp của Karatsuba. Khi số chữ số càng lớn thì thời gian tiết kiệm được càng lớn. Với những số có hàng ngàn chữ số, Karatsuba giúp tốc độ nhân tăng tới 17 lần so với cách nhân thông thường.

Một trong những công việc cần tới phép nhân hai số lớn là mã hóa. Mỗi khi người dùng cần mã hóa thông tin trao đổi trên internet – khi truy cập dịch vụ ngân hàng điện tử hay tìm kiếm một thứ gì đó trên mạng – thiết bị của họ đều phải thực hiện những phép nhân với các số có hàng trăm hay hàng ngàn chữ số. Nhưng với những ứng dụng cần xử lý những số có hàng triệu hay hàng tỷ chữ số thì thuật toán của Karatsuba vẫn là quá chậm.

Một đột phá xuất hiện năm 1971, khi hai nhà toán học Đức là Arnold Schönhage và Volker Strassen đưa ra giải pháp sử dụng thuật toán biến đổi nhanh Fourier (FFT) để nhân các số lớn. FFT là một trong những thuật toán quan trọng nhất của thế kỷ 20. Một ứng dụng rất phổ biến của nó là âm nhạc số, mỗi khi người dùng nghe một tệp MP3, dùng dịch vụ nghe nhạc trực tuyến hay đài phát thanh số, đều có thuật toán FFT đứng đằng sau hậu trường để giải mã âm thanh.

Trong tài liệu công bố năm 1971, Schönhage và Strassen còn đưa ra một phỏng đoán quan trọng.

Nửa đầu của phỏng đoán là có thể nhân hai số có N chữ số bằng N x log (N) phép toán. Thuật toán của họ chưa thật sự đạt tới ngưỡng đó nhưng họ nghĩ rằng nó có thể được cải tiến. Trong các thập kỷ sau đó, một số nhà nghiên cứu đã tìm ra cách cải tiến thuật toán của Schönhage và Strassen. Đáng kể nhất là thuật toán năm 2007 của Martin Fürer (nhưng chính ông này cũng cho rằng việc tiếp tục cải tiến vượt quá khả năng của mình).

Nửa sau của phỏng đoán là phần chứng minh hơn rất nhiều: N x log (N) chính là giới hạn không thể vượt qua (hay không có thuật toán nhân số lớn nào có thể làm tốt hơn).

Vào giữa tháng 2/2019, Joris van der Hoeven (trường École Polytechnique, Pháp) và David Harvey (trường UNSW, Úc) đã công bố một tài liệu mô tả thuật toán nhân số lớn mới có thể đạt tới ngưỡng N x log (N), hoàn thành phần dễ của phỏng đoán Schönhage–Strassen. Thay vì dùng FFT một chiều – cách mà tất cả các công trình nghiên cứu về vấn đề này từ năm 1971 tới nay – thuật toán mới sử dụng FFT đa chiều. Cách làm này không phải mới xuất hiện: định dạng ảnh phổ biến JPEG dựa trên các phép FFT 2 chiều và FFT 3 chiều được sử dụng khá nhiều trong vật lý và kỹ thuật. Trong tài liệu mới công bố, hai nhà toán học đã sử dụng FFT với 1729 chiều – thứ có vẻ khá khó hình dung nhưng về mặt toán học thì không phức tạp hơn nhiều so với FFT 2 chiều.

Theo hai ông, việc nhân hai số với mỗi số có một tỷ chữ số bằng máy tính sẽ tốn hàng tháng. Nhưng với thuật toán Schönhage-Strassen, thời gian giảm xuống còn dưới 30 giây và với thuật toán mới được tìm ra thì thời gian còn giảm hơn nữa. Tuy nhiên, thuật toán mới chưa thể áp dụng trong thực tế vì cách chứng minh trong tài liệu mới chỉ đúng cho những số cực lớn. Theo tài liệu FAQ mà hai nhà toán học công bố, họ cũng không biết số lớn tới mức nào thì áp dụng được (tuy họ đưa ra một ví dụ khoảng 10214857091104455251940635045059417341952).

Hai nhà nghiên cứu hy vọng công trình nghiên cứu của họ sẽ được hoàn thiện tiếp và thuật toán sẽ có thể dùng cho những số với vài tỷ hay vài ngàn tỷ chữ số. Nếu điều này thành hiện thực thì thuật toán mới sẽ trở thành công cụ hữu ích cho công nghệ máy tính.

Công trình nghiên cứu mới này vẫn chưa được đánh giá, thẩm định bởi các nhà nghiên cứu trong ngành nhưng mọi người đều hy vọng nó sẽ được công nhận là đúng. Riêng về nửa sau của phỏng đoán, David Harvey và Joris van der Hoeven cùng mong rằng nó sẽ được chứng minh là sai (giống như phỏng đoán của Kolmogorov).

Nguyễn Anh Tuấn