Thuật Toán Tính Lũy Thừa Nhanh. Giải Thích Một Cách đơn Giản

Trang chủ » Cách Viết Lũy Thừa Trong C++ » Thuật Toán Tính Lũy Thừa Nhanh. Giải Thích Một Cách đơn Giản

Có thể bạn quan tâm

Chuyển đến nội dung chính

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

Bởi Phạm Hồng Vinh vào tháng 11 23, 2018 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 programming

Nhận xét

  1. Unknownlúc 06:15 10 tháng 8, 2021

    Tuyệt vời!!

    Trả lờiXóaTrả lời
      Trả lời
  2. Nguyễn Xuânlúc 14:01 18 tháng 8, 2023

    Thuật toán hay quá! Mình muốn được tham khảo thêm về thuật toán tính giai thừa ạ!

    Trả lờiXóaTrả lời
      Trả lời
Thêm nhận xétTải thêm...

Đăng nhận xét

Bài đăng phổ biến từ blog này

Độc lập tuyến tính và phụ thuộc tuyến tính

Bởi Phạm Hồng Vinh vào tháng 9 03, 2019 Hình ảnh Chào mọi người! Hôm nay, mình sẽ nói về một thứ căn bản của căn bản nhất của Đại số tuyến tính đó là phụ thuộc tuyến tính và độc lập tuyến tính. Đây là khái niệm mình thấy làm nền tảng rất chắc để giải thích những lý thuyết khác của môn học này. Vậy thế nào là phụ thuộc hay độc lập tuyến tính? Về định nghĩa toán học, chúng được nêu như sau được nêu ra như sau: "Một tập hợp các vector được cho là phụ thuộc tuyến tính nếu ít nhất một vector có thể được biểu diễn dưới dạng tổ hợp tuyến tính của các vector còn lại. Nếu chúng không thể được biểu diễn dưới dạng tổ hợp tuyến tính, thì ta gọi những vector này độc lập tuyến tính với nhau." Tuy nhiên cách giải thích này vẫn còn khá hàn lâm. Hãy chia nhỏ nó ra và giải thích từng phần một theo một cách dễ hiểu hơn ở phần tiếp theo. Tổ hợp tuyến tính Giả sử chúng ta có 3 vector 𝐚 \boldsymbol{a} , 𝐛 \boldsymbol{b} , 𝐜 \boldsymbol{c} và để cho đơn giản, mình sẽ cho chúng thuộc ℝ 2 \mathbb{R}^2 . 𝐚 = [ 1 0 ] 𝐛 = [ 2 1 ] 𝐜 ... More »

Phép phân tích ma trận A=LU

Bởi Phạm Hồng Vinh vào tháng 6 28, 2019 Phép phân tích ma trận (hay Matrix Decomposition) là một phương pháp nhân tử hóa ma trận bằng cách tách ma trận đó ra thành phép nhân của nhiều ma trận khác nhau. Cũng giống như với một số tự nhiên, ta có thể tách số đó ra thành các nhân tử khác nhau như tách ra thành các thừa số nguyên tố để dễ dàng nhận biết được đặc điểm của con số ấy. Thì nhân tử hóa ma trận cũng được xây trên khái niệm tương tự. Phép phân tích ma trận đơn giản nhất là A = L U A=LU . Trong đó: A A là một ma trận bất kỳ. L L là ma trận tam giác dưới. (L là viết tắt của Lower trong Lower Triangle). U U là ma trận tam giác trên. (U là viết tắt của Upper trong Upper Triangle). A = L U A = LU Phép phân tích ma trận này rất đơn giản, đầu tiên ta thực hiện các phép biến đổi trên dòng để đưa A thành một ma trận bậc thang. Lúc đó, ma trận bậc thang chính là U. Tôi sẽ lấy một ma trận có kích thước 3x3 để làm ví dụ. A = [ 1 5 2 3 6 4 − 2 2 7 ] A = \begin{bmatrix} 1 & 5 & 2 \\ 3 & 6 & 4 \\ -2 ... More » About me

Phạm Hồng Vinh

I love technology, programming and reading. Sometimes, I write blog to share what I learnt. More about me
Trang Facebook
RootonChair Blog

Chủ đề

AI4 Book5 Linear Algebra2 Machine Learning14 Nhập môn Machine Learning10 programming10 Root talk3 Sharing15

Theo tháng

  • 2021 3
    • tháng 9 2021 2
    • tháng 8 2021 1
  • 2020 4
    • tháng 7 2020 1
    • tháng 2 2020 2
    • tháng 1 2020 1
  • 2019 27
    • tháng 9 2019 3
    • tháng 8 2019 3
    • tháng 7 2019 4
    • tháng 6 2019 5
    • tháng 5 2019 2
    • tháng 4 2019 1
    • tháng 3 2019 1
    • tháng 2 2019 4
    • tháng 1 2019 4
  • 2018 10
    • tháng 12 2018 2
    • tháng 11 2018 3
    • tháng 10 2018 1
    • tháng 9 2018 4
Hiện thêm

Bài đăng phổ biến

Phép phân tích ma trận A=LU

Bởi Phạm Hồng Vinh vào tháng 6 28, 2019 Phép phân tích ma trận (hay Matrix Decomposition) là một phương pháp nhân tử hóa ma trận bằng cách tách ma trận đó ra thành phép nhân của nhiều ma trận khác nhau. Cũng giống như với một số tự nhiên, ta có thể tách số đó ra thành các nhân tử khác nhau như tách ra thành các thừa số nguyên tố để dễ dàng nhận biết được đặc điểm của con số ấy. Thì nhân tử hóa ma trận cũng được xây trên khái niệm tương tự. Phép phân tích ma trận đơn giản nhất là A = L U A=LU . Trong đó: A A là một ma trận bất kỳ. L L là ma trận tam giác dưới. (L là viết tắt của Lower trong Lower Triangle). U U là ma trận tam giác trên. (U là viết tắt của Upper trong Upper Triangle). A = L U A = LU Phép phân tích ma trận này rất đơn giản, đầu tiên ta thực hiện các phép biến đổi trên dòng để đưa A thành một ma trận bậc thang. Lúc đó, ma trận bậc thang chính là U. Tôi sẽ lấy một ma trận có kích thước 3x3 để làm ví dụ. A = [ 1 5 2 3 6 4 − 2 2 7 ] A = \begin{bmatrix} 1 & 5 & 2 \\ 3 & 6 & 4 \\ -2 ... More »

Độc lập tuyến tính và phụ thuộc tuyến tính

Bởi Phạm Hồng Vinh vào tháng 9 03, 2019 Hình ảnh Chào mọi người! Hôm nay, mình sẽ nói về một thứ căn bản của căn bản nhất của Đại số tuyến tính đó là phụ thuộc tuyến tính và độc lập tuyến tính. Đây là khái niệm mình thấy làm nền tảng rất chắc để giải thích những lý thuyết khác của môn học này. Vậy thế nào là phụ thuộc hay độc lập tuyến tính? Về định nghĩa toán học, chúng được nêu như sau được nêu ra như sau: "Một tập hợp các vector được cho là phụ thuộc tuyến tính nếu ít nhất một vector có thể được biểu diễn dưới dạng tổ hợp tuyến tính của các vector còn lại. Nếu chúng không thể được biểu diễn dưới dạng tổ hợp tuyến tính, thì ta gọi những vector này độc lập tuyến tính với nhau." Tuy nhiên cách giải thích này vẫn còn khá hàn lâm. Hãy chia nhỏ nó ra và giải thích từng phần một theo một cách dễ hiểu hơn ở phần tiếp theo. Tổ hợp tuyến tính Giả sử chúng ta có 3 vector 𝐚 \boldsymbol{a} , 𝐛 \boldsymbol{b} , 𝐜 \boldsymbol{c} và để cho đơn giản, mình sẽ cho chúng thuộc ℝ 2 \mathbb{R}^2 . 𝐚 = [ 1 0 ] 𝐛 = [ 2 1 ] 𝐜 ... More »

[Nhập môn Machine Learning] Bài 7: Vector hóa thuật toán

Bởi Phạm Hồng Vinh vào tháng 7 22, 2019 Hình ảnh Chúng ta đã đi được khá xa trong những bài vừa qua. Ta đã biết đến phương pháp tối ưu phổ biến nhất trong Machine Learning chính là Gradient Descent và sử dụng nó trong Linear Regression. Bây giờ, ta cần lùi bước lại để có được cái nhìn toàn cảnh về những việc mà ta đã làm. Đồng thời, tìm hiểu thêm một phương pháp cài đặt (implement) phổ biến hơn cho các thuật toán Machine Learning đó là vector hóa. Cái nhìn tổng quan của các thuật toán Machine Learning Đối với Linear Regression, có 3 thành phần chính mà chúng ta đã học được đó chính là: Model : hay chúng ta còn gọi là Hypothesis Function. Lost Function : đôi khi cũng được nhắc đến với cái tên Cost Function như tôi đã làm. Optimizer : là một thuật toán tối ưu. Ba thành phần trên cũng chính là một bộ khung chung cho các thuật toán thuộc supervised learning trong Machine Learning mà bạn sẽ gặp sau này (hay thậm chí cả Deep Learning nữa). Trong đó, ta có một model để thực hiện các dự đoán, một lost function để đo tính chính xá... More »

Hướng dẫn đăng ký khóa học trên Coursera và edX miễn phí

Bởi Phạm Hồng Vinh vào tháng 12 30, 2018 Hình ảnh Chào các bạn, cũng sắp Tết rồi và chắc mọi người rất mong ngóng khoảng thời gian nghỉ Tết phía trước để bắt đầu kế hoạch "ăn-ngủ-chơi" của mình. Được nghỉ mấy tuần liền mà có vài việc cứ làm hoài cũng chán phải không? Sao chúng ta không tận dụng thời gian rảnh rỗi đó để học hỏi thêm một điều gì đó mới mẻ, tự nâng cấp kiến thức của bản thân trong khi mà không bị áp lực từ việc học tập hay đi làm. Nếu như bạn có ý định như vậy vào kỳ nghỉ này, hãy đọc bài viết này. Giới thiệu về Coursera và edX Cả edX và Coursera đều là nền tảng cung cấp các khóa học trực tuyến về nhiều lĩnh vực từ các trường đại học danh tiếng trên thế giới. Mục tiêu của cả hai tổ chức này đều giống nhau đó là mang kiến thức từ các trường đại học ra toàn thế giới, khiến chúng dễ dàng được tiếp cận bởi bất kỳ ai. Trong đó, Coursera được sáng lập bởi hai giáo sư Stanford là Andrew Ng và Daphne Koller vào năm 2012. Cũng vào tháng 5 năm đó, hai trường đại học danh tiếng thế giới là Harvard và M... More »

Từ khóa » Cách Viết Lũy Thừa Trong C++