Cơ chế vận hành của thuật toán luỹ thừa nhanh trong python và trên máy tính Casio fx-880BTG

Thuật toán trên python.
 
def mod_pow(a, n, b):
res = 1
a = a % b # tối giản a
while n > 0:
if n % 2 == 1: # nếu n lẻ
res = (res * a) % b
a = (a * a) % b # bình phương a
n = n // 2 # chia n cho 2
return res
print(mod_pow(2028, 2027, 2025))
 

Vòng lặp để chạy thuật toán này có 11 vòng do .

Ta quan sát quá trình làm việc của 11 vòng này hạ từ 2027 xuống 1 sau 11 vòng.
 
Khởi tạo: res=1, a=3, n=2027.
 

Vòng lặp kết thúc, trả về res = 162. Vậy kết quả cuối cùng là 162.
 
 
Ký hiệu $a^2$ % b = $a$, nghĩa là lấy $a^2$ chia có dư cho b, gán dư vào $a$.
 

Dựa vào nhận xét trên ta xây dựng thuật toán luỹ thừa nhanh trên bảng tính như sau:
 
 
Tính $\lceil\log_2n\rceil$ (giá trị trần của $\log_2n$) (nghĩa là nếu $\log_2n$ là số thập phân ta ta lấy phần nguyên của nó cộng cho 1) để biết bảng tính sẽ có bao nhiêu dòng (mỗi dòng là một vòng lặp). Ví dụ $\lceil\log_22027\rceil =11$. Ngoài ra ta lấy $a$ gán vào biến nhớ $A$ và lấy $b$ gán vào biến nhớ $B$.
 
Tại $A_1$ ta nhập $n$ (cụ thể là số $2027$), từ $A_2$ đến $A_{11}$ ta điền công thức $\text{Int}(A_1\div 2)$ (ứng với n // 2 =n trong thuật toán).
 
Từ $B_1$ đến $B_{11}$ ta điền công thức $A_1-B\text{Int} (A_1\div B)$ để xuất ra số $0$ hoặc số $1$ tuỳ theo $n=A$ là chẵn hay lẻ.
 
Tại $D_1$ ta nhập phép tính $\fbox{$=A^2-B \text{Int}(A^2\div B)$}$ (phải có dấu $=$, kết quả sẽ là $1$ nếu $n$ chẵn (để bảo lưu Res) và bằng $A$ nếu $n$ lẻ (để cập nhật Res). Từ $D_2$ đến $D_{11}$ ta điền công thức: $D_1^2-B \text{Int}(D_1^2\div B)$
 
Cuối cùng nhưng quan trọng nhất đó là Res:

Tại $C_1$ ta nhập phép tính $=A^{B_1}$. Từ $C_2$ đến $C_{11}$ ta điền công thức $\fbox{$C_1D_1^{B_2}-B \text{Int}(C_1D_1^{B_2}\div B)$}$. ($C_1$ là Res, $D_1$ là $A$ luỹ thừa $B_2$ là để bảo lưu hay cập nhau tuỳ theo $n$ chẵn hay $n$ lẻ).
 
 

Gán $a$ và $b$ vào biến nhớ A, B.
 
Mở bảng tính:
 
Nhập liệu về $n$ :
 
Đưa con trỏ tới $B_1$ chọn điền công thức:
 

Tại $D_1$ nhập phép tính: .
 
Từ $D_2$ đến $D_{11}$ điền công thức:
 
Tại $C_1$ nhập phép tính và từ $C_2$ đến $C_{11}$ điền công thức (như trong hình):
.

Vậy dư của phép chia $2028^{2027}$ cho $2025$ là $\boldsymbol{162}$.

About TS. Nguyễn Thái Sơn

Nguyên trưởng Khoa Toán-Tin học ĐHSP TP HCM (1999-2009). Nguyên Giám đốc- Tổng biên tập NXB ĐHSP TP HCM (2009-2011). Nguyên Tổng thư ký Hội Toán học TP HCM (2008-2013).