Tính mod của tổng và tích với số nguyên lớn

Trong lập trình khi tính toán số học thường xảy ra hiện tượng tràn số. Đó là hiện tượng xảy ra khi một phép tính số học cố gắng tạo ra một giá trị số nằm ngoài phạm vi có thể được biểu diễn với một số bit nhất định – có thể lớn hơn giá trị lớn nhất hay nhỏ hơn giá trị nhỏ hơn được thể hiện.

Khi lập trình để tránh hiện tượng tràn số khi thực hiện phép toán số học kết quả của bài toán thường được mod cho 1 số P bất kì nào đó (P nằm trong phạm vi lưu trữ của biến và thường là số nguyên tố đủ lớn). Khi tính toán hai phép toán thường xảy ra tràn số nhiều nhất đó là phép cộng và phép nhân.

Bài toán: Tính mod của 2 số nguyên integer a và b cho P ( P cũng là integer)
Phạm vi của biến integer (trong C/C++): -2147483648 tới 2147483647
Ví dụ: a = 2000000000 (2 tỷ) và b = a; P = 2000000009

Nhắc lại: (a + b) % P = (a % P + b % P) % P

Lúc này cần 1 cách tính hiệu quả hơn để tính (a + b) % P

• Đặt a1 = a % P
• Đặt b1 = b % P
• Đặt d = P - b1 ( d < P)
• Nếu a1 < d thì a1 + b1 = a1 + P -d < P ( do a1 < d). Do đó kết quả sẽ là a1 + b1
• Nếu a1 >= d thì a1 + b1 > P Do đó kết quả sẽ là a1 + b1 - P = a1 - d

int summod(int a, int b, int P)
{
    a %= P;
    b %= P;
    int d = P - b;
    return a < d? a+b: a-d;
}

Để tính mod của tích a * b. Xét b làm 2 trường hợp

• b chia hết cho 2: a * b = a * b/2 + a * b/2

• b không chia hết cho 2: a * b = a * b/2 + a * b/2 + a
  

Dễ thấy bài toán lúc này đã quy về dạng tính mod của tổng.
Lúc này ta chỉ cần tính a * b/2 % P. Mà a * b/2 % P lại có thể tính được dựa vào lời giải bài toán con khi tính a * b/4.
Lúc này ta có thể dùng phương pháp chia để trị sử dụng hàm đệ quy để lấy lời giải bài toán con nhỏ hơn. Với lời giải của bài toán con cơ sở khi b = 1 thì a * b = a. Gọi F(a, b) là kết quả của a * b % P

• Với b = 1. thì F (a,b) = a
• Với b > 1. Xét 2 trường hợp
• • b chia hết cho 2: F ( a, b) = (F(a, b/2) + F(a, b/2)) % P
• • b không chia hết cho 2 F( a, b) = (F(a, b/2) + F(a, b/2) + a) % P

int mulmod(int a, int b, int P)
{
    if (b == 1)
        return a%= P;
    int a1 = mulmod(a, b/2);
    a1 = mulmod(a1, a1);
    if (b%2)
        return addmod(a1, a);
    return a1;
}

Với việc dùng chia để trị thủ tục đệ quy có độ sâu log b (Khi b = 1 tỷ thì log b = 10). Do đó với b lớn thì hàm mulmod vẫn thực hiện tốt để cho ra kết quả.