Thuật toán tính lũy thừa nhanh. Giải thích một cách đơn giản

Khi được yêu cầu viết một hàm tính lũy thừa. Bạn sẽ làm như thế nào?

Đáp án khá đơn giản phải không, chỉ với một vòng lặp for thì có thể giải quyết tất cả. Nhưng như vậy liệu đã tối ưu chưa?

Gần đây mình có xem qua một vài chương của cuốn Nhập môn lập trình và tìm thấy một vài điều thú vị. Trong đó, có phương pháp tính lũy thừa nhanh mà mình muốn chia sẻ lại.

Cuốn sách Nhập môn Lập trình

Phương pháp thông thường

Với đề bài trên, cách làm dễ nhất là:

Để dễ dàng thử độ hiệu quả của thuật toán, mình dùng kiểu dữ liệu int64_t tức kiểu số nguyên sử dụng 64 bit (8 byte) để chứa dữ liệu và kiểu long tức kiểu số nguyên sử dụng 32 bit (4 byte) để chứa dữ liệu.

Nếu các bạn đã biết về phân tích độ phức tạp của thuật toán thì độ phức tạp của thuật toán trên là O(n) , có nghĩa là nếu n càng lớn thì thời gian tính toán xong của ta càng lâu. Nếu các bạn cho hàm trên chạy với n = 1 000 000 000 (1 tỷ cho bạn nào lười đếm). Máy mình chạy mất xấp xỉ 8 giây. Đây là một thời gian chờ tương đối lâu cho một chương trình. Hãy thử tưởng tượng bạn đã tạo một ứng dụng tính toán rất xuất sắc, nhưng mỗi khi người dùng cần tính lũy thừa với một số lớn thì 8 giây... mình nghĩ họ chỉ cần 5 giây để gỡ cài đặt ứng dụng của bạn và thay thế bằng một cái khác nhanh hơn.

Mong là bạn hiểu những gì mình đang muốn nhấn mạnh.

Bạn có thể tự mình xác nhận tôi nói ở trên bằng cách chạy đoạn code dưới đây ở máy bạn.

Phương pháp tính lũy thừa nhanh

Khái niệm

Trước khi sử dụng một thuật toán nào, mình luôn cố gắng trước hết tìm hiểu một cách hiểu khái niệm đằng sau thuật toán ấy. Và đó chính xác là những gì chúng ta sẽ làm ở đây.

Máy tính, dù sao cũng chỉ là một cỗ máy biết thực hiện hàng loạt những hành động đơn giản một cách nhanh chóng. Nếu bỏ The Flash vào một chiếc hộp rồi yêu cầu anh ta làm hàng loạt những tính toán đơn giản thì anh ta cũng có thể coi là một chiếc máy tính.

Hãy lấy giấy và bút ra. Chúng ta sẽ tính \$2^8\$ theo 2 cách:

1. Nhân 2 lần lượt. tức đầu tiên ta tính \$2\times2=4\$ rồi \$4\times2=8\$ và tiếp tục nhân 2 vào kết quả trước cho đến khi ta kiếm được đáp án cuối cùng là 256.
2. Hơi khác một chút, lần này bạn hãy bình phương cơ số và giảm số mũ đi một nửa, tức \$2^8\$ thành \$4^4\$ rồi \$16^2\$, cuối cùng \$16^2\$ là 256.

Theo bạn, cách nào nhanh hơn?

Nếu là mình, mình thấy cách số 2 tốn ít bước hơn và nhanh hơn. Với cách 2, ta cố gắng biến cơ số của ta lớn nhất và nhờ đó số mũ giảm đi đáng kể dẫn tới việc tính toán dễ hơn. Thay vì phải chật vật với việc nhân 2 tám lần, ta đơn giản hóa thành nhân 16 hai lần.

Thuật toán tính lũy thừa nhanh cũng vậy. Trong đó, ta cố gắng thay thế việc nhân nhiều lần một số nhỏ thành nhân 2 đến 3 số lớn lại với nhau (việc mà máy tính rất giỏi). Cách đơn giản được biểu diễn như sau:

Với  \$a^n=(a^2)^{\tfrac{n}{2}}\$                khi n là số chẵn
        \$a^n=a\times(a^2)^{\tfrac{n-1}{2}}\$     khi n là số lẻ

Hàm tính lũy thừa nhanh

Đây là bản cải tiến hàm tính lũy thừa của chúng ta. Với độ phức tạp là \$O( \log_2 (n))\$.

Nếu bạn vẫn chưa hiểu cách hoạt động của hàm. Mình sẽ lấy một ví dụ cụ thể. Giả sử ta muốn tính \$2^{12}\$. Vậy thì hàm của cúng ta sẽ làm như sau:

1. Do n=12 là số chẵn, nên ta chuyển từ tính \$2^{12}\$ sang tính \$4^6\$, biến result của ta vẫn mang giá trị là 1.
2. n=6 tiếp tục là số chẵn. Ta nhận ra có thể thay thế \$4^6\$ thành \$16^3\$.
3. n=3 là số lẻ. Ta biến n thành số chẵn bằng cách nhân a cho biến chứa kết quả. Bây giờ result = 16 và chúng ta tiếp tục tính \$16^2\$. Ta đơn giản hóa được thành \$256^1\$.
4. n=1 là số lẻ. Ta nhân 256 cho 16 có sẵn trong biến result thành 4096. Cập nhật \$n= 0.5\$ nhưng do cách tính toán số nguyên của máy tính, 0.5 sẽ chỉ được giữ lại phần nguyên là 0. Lúc này ta không cần quan tâm tới cơ số a vì \$a^0=1\$.
5. n=0. Ta thoát khỏi vòng lặp. Vậy kết quả của phép tính \$2^{12}=16\times256=4096\$

Nếu ta sử dụng thuật toán mới này với cùng phép thử ở trên (a=2 và n=1 tỷ) thì thời gian thực thi là ngay lập tức (Tuy nhiên, bạn không thể lấy được kết quả do hậu quả của việc tràn số). Nhưng thật tốt vì bây giờ bạn đã có một vũ khí mới để sử dụng nếu may mắn bạn làm việc cho các "ông lớn" công nghệ như Google, Facebook, Amazon,... . Khi mà những con số cần tính toán lên tới hàng chục tỷ và dữ liệu được lưu trữ bằng Petabyte ( \$2^{50}\$ byte).

Kết luận

Vậy là mình đã trình bày cho các bạn một phương pháp tính lũy thừa nhanh với cách hiểu của mình. Nếu các bạn thích bài viết, hãy theo dõi blog RootOnChair để tạo động lực cho mình viết tiếp những bài viết như vậy nhé. Cảm ơn các bạn.

*Bài viết được tham khảo từ giáo trình Nhập môn lập trình