Phương pháp chia và chinh phục cho phép nhân
Tất cả chúng ta đều học cách nhân hai số khi còn nhỏ. Trong trường hợp chúng ta quên (😄), hãy xem cách nhân hai số 19 và 95.
Nhân 19 và 95 yêu cầu 4 (2²) phép toán cơ bản như hình trên. Tương tự, nhân 123 và 456 sẽ yêu cầu 9 (3²) phép toán cơ bản. Do đó, nếu chúng ta tổng quát hóa, cho hai số có n chữ số, thì phương pháp truyền thống này yêu cầu n² phép nhân sơ cấp. Do đó, độ phức tạp về thời gian của cách tiếp cận ngây thơ này là O (n²).
Đây có phải là cách duy nhất có thể để nhân hai số không? 🤔
Năm 1960, một nhà toán học người Nga tên là Anatoly Alexeyevich Karatsuba đã khám phá ra một thuật toán mới để nhân hai số. Hãy để chúng tôi xem xét cách thức hoạt động của thuật toán này.
Thuật toán Karatsuba
Hãy xét hai số có 4 chữ số x và y trong đó x = 1234 và y = 5678. Trước hết, ta nên chia số có n chữ số thành n / số có 2 chữ số như hình dưới đây.
a và c đại diện cho n / 2 chữ số đầu tiên của x và y . Tương tự, b và d đại diện cho n / 2 chữ số cuối cùng của x và y
Thuật toán Karatsuba bao gồm 4 bước chính.
Cuối cùng, nhân đầu ra của bước 1 với 10ⁿ, đầu ra của bước 4 với 10 ^ (n / 2), và cộng cả hai với kết quả của bước 2 (như hình dưới đây).
Nếu bạn nhân 1234 với 5678, câu trả lời sẽ là 7006652. Có vẻ khá dễ dàng phải không !!!
Nhưng, điều này hoạt động như thế nào? 🤔
Hãy để chúng tôi phá vỡ điều này. Như đã nói ở trên, cho x = 1234 và y = 5678. Chúng ta cũng đã xác định a = 12, b = 34, c = 56 và d = 78.
Nếu chúng ta viết x và y theo a, b, c và d:
Bây giờ, nếu chúng ta nhân x và y:
Chúng ta đã tính ac ở bước 1 và bd ở bước 2. Ở bước 3, chúng ta đã tính (a + b). (C + d) = ac + ad + bc + bd. Để nhận được (ad + bc), chúng ta nên trừ đi ac và bd. Đó là những gì chúng tôi đang làm trong bước 4. Nếu chúng tôi tóm tắt,
Bây giờ, tất cả 4 bước mà chúng ta đã làm trước đó đều có ý nghĩa.
Triển khai Python của thuật toán Karatsuba
Việc triển khai này sử dụng đệ quy. Các bước 1, 2 và 3 được thực hiện ở dòng 21, 22 và 23. Cuối cùng, kết quả của bước 4 được trả về ở dòng 25. Các cuộc gọi đệ quy phải có điều kiện kết thúc. Ở đây, khi các giá trị của a, b, c và d trở thành các chữ số đơn (0-9), thì đệ quy kết thúc (dòng 8 và 9).
Một câu hỏi thú vị cần hỏi vào thời điểm này sẽ là:
Chúng ta cần tính ac, ad, bc và bd. ac và bd được tính ở bước 1 và 2. Chúng ta cũng có thể tính được ad và bc trong hai bước bổ sung. Nhưng thay vào đó, chúng ta nhân (a + b). (C + d) rồi trừ ac và bd. Tại sao? 🤔
Lý do là để giảm số lượng cuộc gọi đệ quy. Việc triển khai hiện tại chỉ yêu cầu ba lần gọi đệ quy. Nếu chúng ta tính riêng ad và bc, số lần gọi đệ quy sẽ trở thành 4. Giữ số lượng lệnh gọi đệ quy ở mức tối thiểu sẽ mang lại hiệu suất tốt hơn.
Thuật toán Karatsuba tốt hơn cách tiếp cận truyền thống như thế nào?
Trước đó, chúng ta đã thấy rằng phương pháp truyền thống có độ phức tạp là O (n²). Bây giờ, chúng ta hãy thử tìm ra độ phức tạp về thời gian của thuật toán Karatsuba.
Cho 2 số có n chữ số, thuật toán lặp lại ba lần trên n / số có 2 chữ số. Do đó, độ phức tạp có thể được biểu thị như sau:
Nếu chúng ta giải quyết được điều này, thì độ phức tạp về thời gian sẽ là:
log₂³ xấp xỉ bằng 1,585 <2. Do đó, với n đủ lớn, thuật toán Karatsuba sẽ hoạt động tốt hơn (ít thời gian chạy hơn) so với cách tiếp cận ngây thơ truyền thống.
Hy vọng bạn thích bài viết !!!
Tài liệu tham khảo: https://www.youtube.com/watch?v=JCbZayFr9RE
Xem thêm một số bài viết khác về toán học: Tại Đây
