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.

Advertisements

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: