Lũy thừa nhị phân (Binary Exponentiation)

2) Ý tưởng cốt lõi

Viết ~n~ ở hệ nhị phân: $$ n=\sum_{i=0}^{k} \texttt{bit}_i\cdot 2^i,\quad \texttt{bit}_i\in\{0,1\} $$ Khi đó: $$ a^n=\prod_{\texttt{bit}_i=1} a^{2^i} $$

Ta tạo dãy ~a, a^2, a^4, a^8, \dots~ bằng bình phương liên tiếp, và chỉ nhân vào kết quả khi bit tương ứng của ~n~ bằng ~1~.

Độ phức tạp:

• Thời gian: ~O(\log n)~
• Bộ nhớ: ~O(1)~ (bản lặp)