Tính lũy thừa nhanh bằng bình phương và nhân
Bình phương và nhân là thuật toán dùng để tính nhanh lũy thừa với cơ số tự nhiên. Thuật toán thường được áp dụng trong trường hợp cần tính lũy thừa và lấy dư theo một module nào đó.
Công thức truy hồi
Thông thường, khi tính \(x^{21}\), ta phải thực hiện 21 bước. Tuy nhiên, ta thấy: \(x^{21} = x (x^{10})^2\) nên chỉ cần tính đến \(x^{10}\), sau đó bình phương và nhân thêm cho \(x\).
Ý tưởng trên dẫn đến công thức sau:
\[\large x^n = \begin{cases} (x^{\frac{n}{2}})^2 & \quad \text{khi } n \text{ chẵn}\\ x(x^{\frac{n-1}{2}})^2 & \quad \text{khi } n \text{ lẻ}\\ \end{cases}\]Độ phức tạp:
Do \(n\) giảm theo lũy thừa của 2 nên độ phức tạp của thuật toán là \(O(\log n)\).
Cài đặt
Vì kết quả lũy thừa thường rất lớn nên ta sẽ tính phần dư khi chia cho \(M\). Khi cài đặt cần chú ý tránh tràn số.
Cài đặt đệ quy
#define M 10000
int pow(int x, int n) {
if (n == 0) return 1;
int temp = pow(x, n/2);
if (n % 2 == 0) return temp * temp % M;
return temp * temp % M * x % M;
}
Cài đặt không đệ quy
Giả sử \(n\) có dạng nhị phân là \(b_m b_{m-1}...b_2 b_1 b_0\), ta có:
\[\large x^n = x^{b_0 2^0 + b_1 2^1 +...+ b_m 2^m} = x^{b_0} x^{2b_1} x^{4b_2} x^{8b_3} x^{16b_4} ...\]Ta sẽ lưu các giá trị \(x, x^2, x^4, x^8, ...\) trong biến temp. Đoạn code như sau:
int pow(int x, int n) {
int res = 1;
int temp = x;
while (n > 0) {
if (n & 1) res = res * temp % M;
n >>= 1;
temp = temp * temp % M;
}
return res;
}