Lũy thừa nhanh bằng chia để trị

Xét $a\ne0$ và số nguyên n≥0. Cơ sở là $a^0=1$. Nếu n=2k thì $a^n=(a^k)^2$; nếu n=2k+1 thì $a^n=a(a^k)^2$. Vì vậy chỉ cần tính một lần $b=a^{\lfloor n/2\rfloor}$, rồi dùng b ở cả hai thừa số. Việc lưu b giúp tránh tính lại cùng một bài toán nhỏ.

Bản nhân lần lượt khởi đầu p=1 rồi nhân p với a đúng n lần, nên có n phép nhân; với n=13 là 13 lần. Khi tính tay có thể bắt đầu ngay từ a và bỏ một phép nhân với 1, nên số đếm khác với mã khởi đầu p=1. Theo mô hình của sách coi mỗi phép tính cơ bản có chi phí hằng số, bản nhanh chỉ có một bài toán nhỏ với số mũ n//2 và không quá hai phép nhân để kết hợp. Số mức tăng theo $\log n$, cho bậc $O(\log n)$ thay vì $O(n)$ của bản nhân lần lượt. Số đếm ấy không tự là số mili giây thực chạy. Nếu viết hai lời gọi power_fast(a,n//2) riêng để nhân với nhau, cùng kết quả nhỏ bị tính lại; đó không còn là cách lưu b đang phân tích.