Phép nhân Ấn Độ và phép tính luỹ thừa

1. Đặt vấn đề

Cho một bài toán đơn giản sau:

Tính giá trị của \(((3 * 10^{18}) * (3 * 10^{18})) \% 10^9\).

• Nếu thực hiện nhân hết các thừa số lại rồi mới chia lấy dư để ra kết quả, thì khi đó phép nhân của hai thừa số sẽ vượt quá khả năng biểu diễn của kiểu số nguyên 64 bit, phép toán sẽ sai hoàn toàn.
• Ta có thể nhanh chóng tính ra kết quả của phép toán này bằng việc sử dụng tính chất của phép đồng dư:
  • \((a+b) \% c = ((a\%c) + (b\%c)) \% c\).
  • \((a-b) \% c = ((a\%c) – (b\%c)) \% c\).
  • \((a * b) \% c = ((a\%c) * (b\%c)) \% c\).
• Vì \((3∗10^{18}) \; \% \; 10^9 < 10^9\), nên \(((3∗10^{18}) \; \% \; 10^9) * ((3∗10^{18}) \; \% \; 10^9) < 10^{18}\).

Vậy phép toán trên hoàn toàn sử dụng được nếu sử dụng tính chất đồng dư
Nhưng nếu giá trị lấy kết quả chia dư là \(10^{18}\) thì sao?

Khi đó \((3∗10^{18}) \; \% \; 10^{18} < 10^{18}\) và nếu mũ \(2\) lên sẽ bị tràn số tương tự bên trên đã giải thích.

2. Phép nhân Ấn Độ

Ta có công thức

\(a * b = \begin{cases} a * \frac{b}{2} + a * \frac{b}{2}, \; nếu \; b \; chẵn \\ a * \frac{b}{2} + a * \frac{b}{2} + a, \; nếu \; b \; lẻ \end{cases}\)

Với công thức trên, ta có thể chuyển phép nhân thành phép cộng hai số \(10^{18}\) và không bị tràn số.

Code phép nhân Ấn Độ bằng đệ quy

long long nhan(long long a,long long b, long long mod){
    if (b == 0) return 0;
    long long t = nhan(a, b / 2, mod);
    t = (t + t) % mod;
    if (b % 2 == 1)
        t = (t + a) % mod;
    return t;
}

Khi muốn nhân hai số, ta chỉ việc gọi nhan(a,b,mod) . Ví dụ bên trên ta chỉ cần gọi hàm \(nhan (3∗10^{18}, 3∗10^{18}, 10^{18})\);

Đánh giá độ phức tạp của phép nhân Ấn Độ

Do sau mỗi lần gọi hàm nhan, giá trị của b bị giảm đi một nửa, nên thuật toán có độ phức tạp là \(O(log b)\).

3. Phép tính lũy thừa

Bằng việc sửa đổi code, phương pháp này có thể được áp dụng để giải một bài toán tương tự, đó là tìm số mũ cực lớn của một số cho trước.

Để tính \(a^b \; \% \; mod\)

Ta có công thức:
\( a^b = \begin{cases} a^{\frac{b}{2}} * a^{\frac{b}{2}}, \; nếu \; b \; chẵn \\ a^{\frac{b}{2}} * a^{\frac{b}{2}} * a, \; nếu \; b \; lẻ \end{cases}\)

Code phép tính lũy thừa bằng đệ quy

long long power(long long a,long long b, long long mod){
    if (b == 0) return 1;
    long long t = power(a, b / 2, mod);
    t = (t * t) % mod;
    if (b % 2 == 1)
        t = (t * a) % mod;
    return t;
}

Đánh giá độ phức tạp của phép tính lũy thừa

Độ phức tạp của thuật toán này cũng chỉ là \(O(log b)\) do \(b\) cũng giảm 1 nửa sau mỗi lần gọi đệ quy.

Chú ý nếu lấy số mod lớn thì phải áp dụng nhân Ấn Độ thay vì phép nhân thông thường, độ phức tạp sẽ trở thành \(O((logb)^2)\)

Kết luận

• Khi gặp một bài toán cần tính tích các số mà kết quả lấy số dư cho một số lớn hơn \(10^9\), ta sử dụng phép nhân Ấn Độ với độ phức tạp \(O(log(mod))\) để giải quyết
• Khi cần tính luỹ thừa của hai số nguyên, ta nên tự viết làm luỹ thừa như bên trên. Mặc dù trong ngôn ngữ C++ đã hỗ trợ hàm pow để tính luỹ thừa, tuy nhiên, hàm này trả về kết quả là một số thực và khi kết quả quá lớn ~ \(10^{18}\) có thể xảy ra sai số, dẫn đến kết quả sai.

3. Luyện tập

Đây là một số bài tập luyện tập trong sách Competitive Programming Basic của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn

Xem thêm tại: https://www.facebook.com/codedreamedu