• TOÁN 10
    • Đề kiểm tra
    • Đề thi giữa HK1
    • Đề thi HK1
    • Đề thi giữa HK2
    • Đề thi HK2
    • Đề thi khảo sát
    • Tài liệu học tập
    • Bài tập toán 10
    • Giáo án Toán 10
    • Chuyên đề toán 10
  • TOÁN 11
    • Đề kiểm tra
    • Đề thi giữa HK1
    • Đề thi HK1
    • Đề thi giữa HK2
    • Đề thi HK2
    • Đề thi khảo sát
    • Tài liệu học tập
    • Bài tập toán 11
    • Giáo án Toán 11
    • Chuyên đề toán 11
  • TOÁN 12
    • Đề kiểm tra
    • Đề thi giữa HK1
    • Đề thi HK1
    • Đề thi giữa HK2
    • Đề thi HK2
    • Đề thi khảo sát
    • Tài liệu học tập
    • Bài tập toán 12
    • Chuyên đề toán 12
    • Giáo án Toán 12
  • TÀI LIỆU
    • Sách Giáo Khoa
    • Công Thức Toán
    • Tài Liệu Ôn Thi HSG
    • Tài liệu ôn thi ĐGNL
    • Tài Liệu Ôn Thi TN THPT
    • Tài Liệu Máy Tính Casio
  • ĐỀ THI
    • Đề ôn thi THPT
    • Đề thi HSG THPT
    • Đề thi thử TN THPT
    • Đề thi ĐGNL & ĐGTD
    • Đề Thi TN THPT Quốc Gia
  • BLOG TỔNG HỢP
    • Blog Tin Tức
    • Blog Toán học
    • Tạp chí Epsilon
    • Tài liệu ngữ văn
  • THI ONLINE
    • Thi thử TN THPT
No Result
View All Result
No Result
View All Result
Home Blog Tổng Hợp Blog Toán học

Thuật toán Karatsuba để Nhân hai số nguyên

vted by vted
01/02/2022
in Blog Toán học
Reading Time: 5 mins read
0
Share on FacebookShare on TelegramShare on QR Code

Mục lục

  1. Phương pháp chia và chinh phục cho phép nhân
  2. Thuật toán Karatsuba
  3. Triển khai Python của thuật toán Karatsuba
  4. Thuật toán Karatsuba tốt hơn cách tiếp cận truyền thống như thế nào?

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

Related Posts

460 BÀI TOÁN VUI LUYỆN TRÍ THÔNG MINH
Blog Toán học

460 BÀI TOÁN VUI LUYỆN TRÍ THÔNG MINH

04/06/2022
PHƯƠNG PHÁP QUY NẠP TOÁN HỌC
Blog Toán học

PHƯƠNG PHÁP QUY NẠP TOÁN HỌC

09/04/2022
CHUYÊN KHẢO ĐA THỨC
Blog Toán học

CHUYÊN KHẢO ĐA THỨC

07/04/2022
CÁC BÀI TẬP VÀ CHUYÊN ĐỀ TAM GIÁC ĐỒNG DẠNG
Blog Toán học

CÁC BÀI TẬP VÀ CHUYÊN ĐỀ TAM GIÁC ĐỒNG DẠNG

07/04/2022
TOÁN HỌC SIÊU HAY
Blog Toán học

TOÁN HỌC SIÊU HAY

22/03/2022
Lý thuyết sơ cấp của các số
Blog Toán học

Lý thuyết sơ cấp của các số

22/03/2022

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Tìm kiếm

No Result
View All Result

Bài Viết Mới Nhất

Đề thi thử Toán tốt nghiệp THPT 2023 lần 1 trường Đinh Tiên Hoàng – Ninh Bình

Đề thi chọn học sinh giỏi Toán THPT vòng tỉnh năm 2022 – 2023 sở GD&ĐT Vĩnh Long

Đề chọn HSG trường Toán 12 năm 2022 – 2023 trường chuyên Phan Bội Châu – Nghệ An

Bài giảng phương pháp trải hình trên mặt phẳng – Trần Thị Hiền

Hệ thống bài tập trắc nghiệm xác suất

ĐH Bách Khoa Hà Nội công bố dạng câu hỏi và ví dụ mẫu về đề thi Đánh giá tư duy năm 2023

Bộ GD công bố dự thảo quy chế thi tốt nghiệp THPT 2023

Toàn văn dự thảo Thông tư sửa đổi, bổ sung Quy chế thi tốt nghiệp THPT

Đề kiểm tra kiến thức Toán 12 năm 2022 – 2023 trường THPT chuyên KHTN – Hà Nội

Đề chọn đội tuyển HSG Toán 10 năm 2022 – 2023 trường THPT chuyên Bến Tre

Load More

About Us

VTED.net là một thư viện online nơi bạn có thể tải xuống các tài liệu, đề thi, sách... thuộc các môn học của khối lớp trung học hấp dẫn, nổi bật với các loại file pdf, word, ... miễn phí.

Recent Posts

  • Đề thi thử Toán tốt nghiệp THPT 2023 lần 1 trường Đinh Tiên Hoàng – Ninh Bình
  • Đề thi chọn học sinh giỏi Toán THPT vòng tỉnh năm 2022 – 2023 sở GD&ĐT Vĩnh Long
  • Đề chọn HSG trường Toán 12 năm 2022 – 2023 trường chuyên Phan Bội Châu – Nghệ An
  • Bài giảng phương pháp trải hình trên mặt phẳng – Trần Thị Hiền

Fanpage

Tài liệu Toán THPT
  • Giới Thiệu
  • Liên Hệ
  • Bản Quyền

Copyright © 2023 | Bản quyền thuộc về VTED.net

No Result
View All Result
  • TOÁN 10
    • Đề kiểm tra
    • Đề thi giữa HK1
    • Đề thi HK1
    • Đề thi giữa HK2
    • Đề thi HK2
    • Đề thi khảo sát
    • Tài liệu học tập
    • Bài tập toán 10
    • Giáo án Toán 10
    • Chuyên đề toán 10
  • TOÁN 11
    • Đề kiểm tra
    • Đề thi giữa HK1
    • Đề thi HK1
    • Đề thi giữa HK2
    • Đề thi HK2
    • Đề thi khảo sát
    • Tài liệu học tập
    • Bài tập toán 11
    • Giáo án Toán 11
    • Chuyên đề toán 11
  • TOÁN 12
    • Đề kiểm tra
    • Đề thi giữa HK1
    • Đề thi HK1
    • Đề thi giữa HK2
    • Đề thi HK2
    • Đề thi khảo sát
    • Tài liệu học tập
    • Bài tập toán 12
    • Chuyên đề toán 12
    • Giáo án Toán 12
  • TÀI LIỆU
    • Sách Giáo Khoa
    • Công Thức Toán
    • Tài Liệu Ôn Thi HSG
    • Tài liệu ôn thi ĐGNL
    • Tài Liệu Ôn Thi TN THPT
    • Tài Liệu Máy Tính Casio
  • ĐỀ THI
    • Đề ôn thi THPT
    • Đề thi HSG THPT
    • Đề thi thử TN THPT
    • Đề thi ĐGNL & ĐGTD
    • Đề Thi TN THPT Quốc Gia
  • BLOG TỔNG HỢP
    • Blog Tin Tức
    • Blog Toán học
    • Tạp chí Epsilon
    • Tài liệu ngữ văn
  • THI ONLINE
    • Thi thử TN THPT

Copyright © 2023 | Bản quyền thuộc về VTED.net