CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Thuật toán Karatsuba-Ofman nhân 2 số nguyên n-bit

Posted by Trần Quốc Long on Tháng Một 10, 2009

Để nhân 2 số nguyên, ta thường dùng quy tắc nhân từng chữ số của một số với số còn lại theo từng hàng rồi cộng kết quả lại. Nếu n là số bít (trong hệ nhị phân, hoặc số chữ số trong hệ thập phân) của 2 số thì thuật toán được học từ thời phổ thông này cần sử dụng O(n^2) phép tính (cộng và nhân bằng bảng cửu chương) để tính ra kết quả cuối cùng.

Ví dụ:

123 \times 345 = 5\times 123 + 40\times 123 + 300\times 123
= 615 + 4920 + 36900 = 42435

Karatsuba-Ofman đã áp dụng kỹ thuật chia để trị để tăng tốc thuật toán nhân 2 số nguyên này. Thuật toán của 2 ông như sau:

procedure KO(A, B)

Input: 2 số A, Bn bit.
Output: Tích C = A\times B.
Giả sử n = 2^k, nếu cần thêm các chữ số {0} vào đằng trước A, B.

  1. If n=1 return C = A\times B (tính bằng bảng cửu chương).
  2. else chia A, B thành các phần có n/2-bit: A_1, A_2, B_1, B_2.
    Như vậy: A=2^{n/2}A_1+A_2, B=2^{n/2}B_1+B_2 còn
    C = 2^n A_1B_1 + 2^{n/2} (A_1B_2+A_2B_1)+A_2B_2
  3. D = KO(A_1, B_1) = A_1\times B_1
  4. E = KO(A_2, B_2) = A_2\times B_2
  5. F = KO(A_1-A_2, B_1-B_2) = (A_1-A_2)\times (B_1-B_2)
  6. G = D+E-F = A_1\times B_2+A_2\times B_1
  7. return C = 2^n D + 2^{n/2} G + E = A\times B

Qua các bước của thuật toán Karatsuba-Ofman, ta có thể dễ dàng thấy được tính đúng đắn của thuật toán, nghĩa là thuật toán luôn trả lại C=A\times B. Bây giờ ta tìm hiểu độ phức tạp của thuật toán trên. Gọi T(n) là số tính toán cần thiết để nhân 2 số n-bit bằng thủ tục KO(A,B) ở trên. Ta có

T(n) = 3T(n/2)+O(n)

trong đó 3T(n/2) là số tính toán của các bước 3,4,5 (nhân các số có n/2 bit) còn O(n) là số tính toán của các bước còn lại. Để ý là bước 7 thực chất chỉ gồm phép dịch trái (shift left) các số D,G,E và phép cộng để tính C. Áp dụng định lý tổng quát ta tính được

T(n) = \Theta(n^{\log_2 3}) = \Theta(n^{1,58})

Như vậy, thuật toán nhân 2 số nguyên của Karatsuba-Ofman cũng có độ phức tạp thuật toán đa thức nhưng có bậc 1,58 nhỏ hơn 2. Với n lớn (cỡ vài nghìn hoặc vài chục nghìn), thuật toán Karatsuba-Ofman giảm đáng kể thời gian nhân 2 số nguyên. Năm 1963, Toom chứng minh rằng có thể nhân 2 số nguyên với độ phức tạp O(n^{1+\epsilon}) với \epsilon >0 bất kì.

Nếu ta viết

A=a_0 + a_1x + \ldots a_{n-1}x^{n-1}
B=b_0 + b_1x + \ldots b_{n-1}x^{n-1}

trong đó a_i, b_i là các chữ số, x là hệ cơ sở (ở đây, x=2). Khi đó C=A\times B  có thể hiểu là việc tính giá trị của phép nhân 2 đa thức A,B tại x. Với nhận xét này, Schönhage và Strassen đã sử dụng phép biến đổi Fourier nhanh (FFT – Fast Fourier Transform) để tạo ra thuật toán nhân 2 số nguyên với độ phức tạp O(n\log n\log\log n). Hai ông còn đưa ra giả thuyết là có tồn tại thuật toán nhân 2 số nguyên với độ phức tạp O(n\log n) nhưng đến nay vẫn chưa có thuật toán nào như vậy được tìm ra.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: