1. Phát biểu

– Trong các ngôn ngữ lập trình đều có kiểu dữ liệu số nguyên (chẳng hạn kiểu integer trong Pascal, Int trong C…), nhưng nhìn chung các kiểu này đều có miền giá trị hạn chế (chẳng hạn từ -32768 đến 32767) nên khi có một ứng dụng trên số nguyên lớn (hàng chục, hàng trăm chữ số) thì kiểu số nguyên định sẵn không đáp ứng được. Trong trường hợp đó, người lập trình phải tìm một cấu trúc dữ liệu thích hợp để biểu diễn cho một số nguyên, chẳng hạn ta có thể dùng một chuỗi kí tự để biểu diễn cho một số nguyên, trong đó mỗi kí tự lưu trữ một chữ số. Để thao tác được trên các số nguyên được biểu diễn bởi một cấu trúc mới, người lập trình phải xây dựng các phép toán cho số nguyên như phép cộng, phép trừ, phép nhân… Sau đây ta sẽ đề cập đến bài toán nhân hai số nguyên lớn.

2. Giải thuật cho bài toán nhân số nguyên lớn

Xét bài toán nhân 2 số nguyên lớn X và Y, mỗi số có n chữ số.

Theo cách nhân thông thường mà ta đã được học ở phổ thông thì phép nhân được thực hiện như sau: nhân từng chữ số của Y với X (kết quả được dịch trái 1 vị trí sau mỗi lần nhân) sau đó cộng các kết quả lại. Ví dụ: X = 1426, Y = 3219, ta đặt tính nhân như sau:

                    1426

x     3219

————

12834

1426

2852

4278

————-

4590294

Việc nhân từng chữ số của X và Y tốn n2 phép nhân (vì X và Y có n chữ số). Nếu phép nhân tốn O(1) thời gian thì độ phức tạp giải thuật của giải thuật này là O(n2).

3. Giải thuật chia để trị cho bài toán nhân số nguyên lớn

Để đơn giản cho việc phân tích giải thuật ta giả sử n là lũy thừa của 2. Còn về phương diện lập trình, giải thuật cũng đúng trong trường hợp n bất kỳ.

Ý tưởng của giải thuật như sau:

  • Biểu diễn X và Y dưới dạng X = A10n/2 + B và Y = C10n/2 + D
  • Trong đó A, B, C, D là các số có n/2 chữ số. Ví dụ với X = 1234 thì A = 12 và B = 34 vì 12*102 + 34 = 1234 = X
  • Với cách biểu diễn này thì XY = AC10n + (AD + BC)10n/2 + BD (*)

Thay vì nhân trực tiếp 2 số có n chữ số, ta phân tích bài toán ban đầu thành một số bài toán nhân 2 số có n/2 chữ số. Sau đó, ta kết hợp các kết quả trung gian theo công thức (*). Việc phân chia này sẽ dẫn đến các bài toán nhân 2 số có 1 chữ số. Đây là bài toán cơ sở. Tóm lại:

  • Kích thước bài toán: số chữ số của X, Y
  • Phân tích: Chia bài toán ban đầu thành các bài toán nhân các số có n/2 chữ số. Quá trình phân chia dừng lại khi kích thước bài toán bằng 1.
  • Tổng hợp: Tổng hợp kết quả theo công thức (*).
4. Cải tiến giải thuậtTheo công thức (*) ở trên việc nhân 2 số nguyên có n chữ số được phân chia thành 4 phép nhân các số nguyên có n/2 chữ số, 3 phép cộng các số lớn hơn n  chữ số và 2 phép nhân với 10n và 10n/2. Phép cộng các số có lớn hơn n chữ số cần O(n). Phép nhân với 10n tốn O(n) (dịch trái n lần). Gọi T(n) là thời gian nhân 2 số có n chữ số ta có phương trình đệ quy sau:

  •  T(1) = 1
  •  T(n) = 4T(n/2) + cn

Giải hệ này ta được T(n) = O(n2). Ta không cải tiến được gío với giải thuật nhân thông thường.

Để cải tiến ta biến đổi công thức (*)  lại như sau:

XY = AC10+ [(A -B)(D-C) + AC + BD]10n/2 + BD (**)

Theo công thức này, ta chỉ cần 3 phép nhân các số nguyên có n/2 chữ số, 6 phép cộng trừ và 2 phép nhân với 10n, 10n/2. Ta có phương trình đệ quy sau:

  • T(1) = 1
  • T(n) = 3T(n/2) + cn

Giải phương trình ta được T(n) = O(nlog3) = O(n1.59). Rõ ràng cải tiến hơn giải thuật cũ rất nhiều.

5. Thuật toán thô

Big_Integer mult(X: Big_Integer, Y: Big_Integer, int n) {

Big_Integer m1, m2, m3, A, B, C, D;
int s; /* lưu dấu của tích XY */
s = sign(X)*sign(Y); /* sign(X) trả về 1 nếu X dương; -1 nếu X âm; 0 nếu X = 0*/
X = ABS(X);
Y = ABS(Y);
if (n == 1) return X*Y*s;
A = left(X, n/2);
B = right(X, n /2);
C = left(Y, n/2);
D = right(Y, n /2);
m1 = mult(A, C, n/2);
m2 = mult(A – B, D – C, n/2);
m3 = mult(B, D, n/2);
return s*(m1*10n + (m1 + m2 + m3)*10n/2 + m3);
}