執行指數運算的最快算法是什麼？

Question

執行指數運算的最快算法是什麼？爲簡單起見，我們假設自然數基和指數。

高效的數學庫會使用什麼？

（當我尋找它，我只是得到的結果有關，在指數時間運行的算法。）

Answer 1

對於小指數Python使用二進制冪（按平方一類冪）爲能在輸電線上看到2874 of http://svn.python.org/view/python/trunk/Objects/longobject.c?view=markup&pathrev=65518

對於較大的指數，它使用2^5-ary指數（通過平方的一種替代類型的指數運算）。

如果你只關心結果的最高有效位，那麼你可以很快計算x^y = exp（y * log（x））。

如果你只關心結果的最低有效位數（例如對於編程競賽），那麼你可以計算指數模某個值M.例如，Python命令pow（x，y，1000）將計算x的最後3位數字作爲y的冪。它是通過平方法的冪運算得到的，但請注意，這比計算完整結果要快得多，因爲它確保中間數字永遠不會大於M.

作爲額外的扭曲（如果您只是對最不重要的數字感興趣），可以使用歐拉定理http://en.wikipedia.org/wiki/Euler%27s_theorem來減小指數的大小。

Answer 2

如果你有一個給定的自然數u和給定的輸入M，計算ü^ M你可以應用下面的算法

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; 

所以基本上，如果你有，可以說，U^23 你將23轉換爲二進制 - > 10111（base 2） 然後，您得到u^23 = u^16 * u^4 * u^2 * u^1（no u^8，因爲從左至右的2位數字爲0）

的複雜度爲O（日誌（M））或O（N）如果考慮n至被登錄（M）_10 + 1

Answer 3

上述所有二進制方法的問題在於它們僅限於整數。如果通過「求冪」指的是計算e^x函數，我所見過的最好的冪級數是快速收斂的，以及在有限範圍內有效的多項式，理性或帕德近似。有一件事是肯定的：如果你找到一個e^x到閃存的小數點後96位的快速算法，你也可以找到更快的計算日誌的方法（Newton-Raphson）。事實上，Newton-Raphson以二次方式收斂，因此每次迭代都會使日誌中的精度位數增加一倍。這是加州大學洛杉磯分校Nate Grossman在第四天的最愛。在過去的四開式計算器的時代，我曾經使用e^x =（1 + x/1024）^ 10。當然，這可以分解爲非常大或非常小的x，但是你可以看到它爲什麼起作用。如果你有一個平方根按鈕，你可以改變這個想法來獲得對數。但是你不需要指數函數的平方根。

我不知道是否有股東周年大會上的算法，可以做指數函數...哼哼的一些反轉....