Trong chúng ta không ai còn xa lạ với khái niệm và ứng dụng của phép nhân. Chúng tôi đã được làm quen với nó trong những năm đầu đời và kể từ đó, nó đã trở thành một phần không thể thiếu trong cuộc sống của chúng tôi
Từ việc ước tính những con số cơ bản nhất như số tiền bạn sẽ trả cho một thuê bao Netflix trong cả năm cho đến tính toán chính xác độ dài của vũ trụ quan sát được, phép nhân được áp dụng ở mọi nơi
Khá dễ dàng để tính xem Netflix sẽ tiêu tốn bao nhiêu tiền trong khoảng thời gian 12 tháng bằng cách nhân chi phí của một tháng với 12, nhưng còn việc nhân hai số rất lớn, với hàng nghìn chữ số thì sao?
Giả sử a có 2¹⁰ chữ số và b có 2¹⁰. Nhân những số lớn như vậy mà không có sự trợ giúp của máy tính có thể không hiệu quả, dễ mắc lỗi và nói thẳng ra là nhàm chán. Và do đó, chúng tôi sử dụng máy tính để tính tổng, hoặc trong trường hợp này, tích của các số lớn
Thuật toán nhân tiêu chuẩn
Thuật toán nhân tiêu chuẩn hoặc Thuật toán cấp trường cho phép nhân là thuật toán phổ biến nhất và được cho là phổ biến nhất được sử dụng để nhân hai số
Thuật toán trường lớp
Như chúng ta có thể quan sát rõ ràng từ ví dụ trên, Thuật toán nhân tiêu chuẩn thực hiện n² phép nhân một chữ số để đạt được giải pháp, trong đó n là số chữ số trong số
Độ phức tạp về thời gian của Thuật toán chuẩn là O[n²]. Nếu bạn chưa quen với Big O, hãy đọc thêm về nó tại đây
Tuy nhiên, sử dụng cùng một thuật toán cho các số có 2¹⁰ chữ số sẽ mất thời gian O[2²⁰] và rõ ràng là không hiệu quả lắm
Nhưng tồn tại các thuật toán để tính toán hiệu quả các sản phẩm có số lượng rất lớn. Tuy nhiên, cần lưu ý rằng các thuật toán này hoạt động đối với các số có vài nghìn chữ số. Đối với các số nhỏ hơn, Thuật toán nhân tiêu chuẩn là cách hiệu quả nhất để nhân
Thuật toán nhân Karatsuba
Thuật toán Karatsuba là một thuật toán nhân nhanh được Anatoly Karatsuba phát hiện vào năm 1960. So với Thuật toán nhân tiêu chuẩn, Thuật toán Karatsuba có thời gian chạy là O[n¹⋅⁵⁸], trong đó n là số chữ số của các số. Nó sử dụng phương pháp chia để trị để nhân hai số có n chữ số
Đối với hai số có 2¹⁰ chữ số, Thuật toán Karatsuba thực hiện 3¹⁰ [ =59.049] phép nhân một chữ số, rõ ràng là nhanh hơn so với Thuật toán chuẩn vốn cần 2²⁰ [= 1.048.576] phép nhân
Để hiểu toàn diện hơn, hãy đọc thuật toán và triển khai trong Java và
phép nhân Toom-Cook
Toom-Cook là một thuật toán nhân được đặt theo tên của Andrei Toom và Stephen Cook, người đã giới thiệu thuật toán
Cho hai số nguyên lớn, Toom-Cook chia nó thành các số nguyên nhỏ hơn gồm k phần nhỏ hơn có độ dài l mỗi phần và thực hiện các thao tác trên các phần đó. Toom-3 là một ví dụ của Toom-Cook trong đó k = 3. Thời gian chạy của Thuật toán Toom-3 đáng kể là O[n¹⋅⁴⁶]. Nó là sự khái quát hóa nhanh hơn của Thuật toán Karatsuba
Do chi phí hoạt động của nó, Toom-Cook chậm hơn Thuật toán tiêu chuẩn cho các số nhỏ hơn và do đó được sử dụng cho các phép nhân loại trung gian
Để hiểu toàn diện hơn, hãy đọc thuật toán và triển khai trong C++
Thuật toán Schonhage–Strassen
Thuật toán Schönhage–Strassen là một thuật toán nhân nhanh tiệm cận cho các số nguyên lớn. Nó được phát triển bởi Arnold Schönhage và Volker Strassen vào năm 1971
Đối với các số có n chữ số, độ phức tạp thời gian chạy của thuật toán Schönhage–Strassen là O[n• log n• log log n]. Nó sử dụng phép biến đổi Fourier nhanh đệ quy
Trong thực tế, thuật toán Schönhage–Strassen bắt đầu hoạt động tốt hơn các phương pháp cũ hơn như phép nhân Karatsuba và Toom–Cook cho các số vượt quá 2^[2¹⁵] đến 2^[2¹⁷] [10.000 đến 40.000 chữ số thập phân]
Để hiểu toàn diện hơn, hãy đọc thuật toán và triển khai trong và
Ghi chú. Thuật toán Schönhage–Strassen là phương pháp nhân tiệm cận nhanh nhất được biết đến từ năm 1971 cho đến năm 2007, khi một phương pháp mới, thuật toán Fürer, được công bố với độ phức tạp tiệm cận thấp hơn;
Bạn cần sử dụng ngôn ngữ có kiểu dữ liệu hỗ trợ số nguyên lớn. Vì Python3 thực sự không có bất kỳ giới hạn trên nào cho số nguyên. Đó sẽ là ngôn ngữ tốt nhất
Hơn nữa, Java có lớp bigInteger mà bạn cũng có thể thực hiện các phép tính liên quan đến giá trị lớn