Thuật toán nhanh nhất để thực hiện lũy thừa là gì?

Question

Thuật toán nhanh nhất để thực hiện lũy thừa là gì? Hãy giả sử các căn cứ số tự nhiên và số mũ vì mục đích đơn giản.

Thư viện toán học hiệu quả sẽ sử dụng cái gì?

(Khi tôi tìm kiếm nó, tôi chỉ nhận được kết quả liên quan đến các thuật toán chạy trong thời gian mũ.)

Answer 1

Đối với số mũ nhỏ Python sử dụng lũy ​​thừa nhị phân (một loại thuật toán bình phương và nhân) như có thể thấy tại dòng 2874 của http://svn.python.org/view/python/trunk/Objects/longobject.c?view=markup&pathrev=65518

Đối với số mũ lớn hơn, nó sử dụng lũy ​​thừa 2^5-ary (một kiểu thay thế lũy thừa bằng bình phương).

Nếu bạn chỉ quan tâm đến các chữ số quan trọng nhất của kết quả, thì bạn có thể tính toán nhanh chóng x^y = exp (y * log (x)).

Nếu bạn chỉ quan tâm đến các chữ số ít quan trọng nhất của kết quả (ví dụ cho một cuộc thi lập trình), thì bạn có thể tính toán số mũ modulo một số giá trị M. Ví dụ, lệnh Python pow (x, y, 1000) sẽ tính 3 chữ số cuối của x thành lũy thừa của y. Nó thực hiện điều này bằng phương pháp bình phương bằng phương pháp bình phương, nhưng lưu ý rằng điều này có thể nhanh hơn nhiều so với tính toán kết quả đầy đủ vì nó đảm bảo rằng các số trung gian không bao giờ lớn hơn M.

Như một bước ngoặt bổ sung (nếu bạn chỉ quan tâm đến các chữ số ít nhất signficant), bạn có thể sử dụng định lý Euler của http://en.wikipedia.org/wiki/Euler%27s_theorem để giảm kích thước của số mũ.

Answer 2

Nếu bạn có một số tự nhiên cho u và m đầu vào nhất định, để tính u^m bạn có thể áp dụng các thuật toán sau

q = m; 
prod = 1; 
current = u; 
while q > 0 do 
    if (q mod 2) = 1 then // detects the 1s in the binary expression of m 
      prod = current * prod; // picks up the relevant power 
      q--; 
    endif 
current = current * current; // u^i -> u^(2*i) 
q = q div 2 
enddo 

output = prod; 

Vì vậy, về cơ bản nếu bạn có, cho phép nói, u^23 bạn chuyển đổi 23 thành nhị phân -> 10111 (cơ sở 2) Sau đó, bạn nhận được u^23 = u^16 * u^4 * u^2 * u^1 (không có u^8 vì 2 chữ số từ trái sang phải là 0)

Độ phức tạp là O (log (m)) hoặc O (n) nếu bạn xem n là log (m) _10 + 1

Answer 3

Vấn đề với tất cả các phương pháp nhị phân ở trên là chúng chỉ giới hạn ở các số nguyên. Nếu bằng "lũy thừa", bạn có nghĩa là tính toán hàm e^x, tốt nhất tôi thấy là chuỗi công suất hội tụ nhanh và đa thức, hợp lý hoặc Pade xấp xỉ có giá trị trong phạm vi giới hạn.

Một điều chắc chắn: nếu bạn tìm thấy thuật toán cực nhanh cho e^x đến 96 chữ số thập phân, bạn cũng sẽ tìm thấy cách nhanh hơn để tính nhật ký (theo Newton-Raphson). Trong thực tế, Newton-Raphson hội tụ bậc hai, vì vậy bạn tăng gấp đôi số chữ số chính xác trong nhật ký của bạn với mỗi lần lặp. Đây là một yêu thích của Nate Grossman của UCLA trở lại trong những ngày Forth.

Quay lại ngày của máy tính bốn bang, tôi đã sử dụng e^x = (1 + x/1024)^10. Tất nhiên là phá vỡ cho x rất lớn hoặc rất nhỏ, nhưng bạn có thể thấy lý do tại sao nó hoạt động. Nếu bạn có nút gốc hình vuông, bạn có thể đảo ngược ý tưởng này để nhận logarit. Nhưng bạn không cần căn bậc hai cho hàm mũ.

Tôi tự hỏi nếu có một số đảo ngược của thuật toán AGM có thể làm hàm mũ ... Hmmm ....