爲什麼Math.pow（int，int）比我的天真執行慢？

昨天我看到一個問題，爲什麼Math.pow(int,int)這麼慢，但這個問題措辭不佳，沒有顯示研究工作，所以很快就關閉了。爲什麼Math.pow（int，int）比我的天真執行慢？

我做了一些自己的測試，發現Math.pow方法實際上運行速度相對於我自己的天真實現（甚至不是一個特別高效的實現）在處理整數參數時運行得非常慢。下面是我跑測試這個代碼：

class PowerTest { 

    public static double myPow(int base, int exponent) { 
     if(base == 0) return 0; 
     if(exponent == 0) return 1; 
     int absExponent = (exponent < 0)? exponent * -1 : exponent; 
     double result = base; 
     for(int i = 1; i < absExponent; i++) { 
      result *= base; 
     } 
     if(exponent < 1) result = 1/result; 
     return result; 
    } 

    public static void main(String args[]) { 
     long startTime, endTime; 

     startTime = System.nanoTime(); 
     for(int i = 0; i < 5000000; i++) { 
      Math.pow(2,2); 
     } 
     endTime = System.nanoTime(); 
     System.out.printf("Math.pow took %d milliseconds.\n", (endTime - startTime)/1000000); 

     startTime = System.nanoTime(); 
     for(int i = 0; i < 5000000; i++) { 
      myPow(2,2); 
     } 
     endTime = System.nanoTime(); 
     System.out.printf("myPow took %d milliseconds.\n", (endTime - startTime)/1000000); 
    } 

}

在我的電腦（在Intel CPU x86_64的Linux）的，輸出幾乎總是報道，Math.pow了10毫秒，而myPow了2ms的。這偶爾會在這裏或那裏出現一毫秒的波動，但Math.pow的運行速度大約是，比平均速度慢了5倍。

我做了一些研究，並根據grepcode，Math.pow只提供與(double, double)類型簽名的方法，它是推遲到StrictMath.pow方法，它是一個本地方法調用。

Math庫只提供處理雙打的pow函數的事實似乎表示可能的回答此問題。顯然，一個必須處理double類型的基類或指數的可能性的冪運算法則比我的只處理整數的算法需要更長的時間來執行。但最終歸結爲依賴於體系結構的本機代碼（它幾乎總是比JVM字節代碼運行得更快，在我的情況下可能是C或彙編）。 似乎在這個級別上，如果可能的話，將優化檢查數據類型並運行更簡單的算法。

鑑於此信息，爲什麼本機Math.pow方法的運行速度比給定整數參數時未優化和天真的myPow方法慢得多？

來源

2016-01-06 Woodrow Barlow

我對此評論： int absExponent =（exponent <0）？指數* -1：指數; 你不需要'*'： int absExponent =（exponent <0）？ - 指數：指數; –

這甚至不是最優（整數）功率算法 - 有效的算法是if（absExponent＆1 == 0）{result * = result; absExponent >> = 1}' - 即它運行在'O（log n）'而不是'O（n）'時間。 – Alnitak

由於你的實現在指數上使用循環，所以計算正方形是一個非常偏頗的基準。你爲什麼不在2⁸中嘗試這兩種方法:)（當然，你可以用一種不那麼幼稚的算法做得更好，但即使如此，2 15也可能會給你一個不同的結果。） – rici

正如其他人所說，你不能忽略使用double，因爲浮點運算幾乎肯定會變慢。然而，這不是唯一的原因 - 如果你改變你的實現來使用它，它仍然更快。

這是因爲兩件事情：第一是2^2（指數，而不是XOR）是一個非常快速的計算進行，那麼你的算法是蠻好用的爲 - 嘗試使用從Random#nextInt（或nextDouble）兩個值你會發現Math#pow實際上更快。

另一個原因是調用本機方法會產生開銷，這在這裏實際上是有意義的，因爲2^2計算起來非常快，而且您多次調用Math#pow。有關詳細信息，請參見What makes JNI calls slow?。

來源

2016-01-06 16:50:34 Toby

啊哈！我用'nextInt（1000）'調用替換了所有的參數，現在'Math.pow'方法比我的實現運行速度快得多。所以事實證明這是一個糟糕的測試案例。 –

沒有pow(int,int)函數。您正在比較蘋果和橘子，並假設您可以忽略浮點數。

來源

2016-01-06 16:43:06 erickson

，但它會傳遞給本地代碼。當然優化會在本地進行？ –

@WoodrowBarlow傳遞給本地代碼的值是'double'。你是否建議如果本地代碼檢測不到小數部分，應該使用備用路徑？參數被轉換爲整型並用積分算子操作的路徑？ – erickson

好吧，當然。有沒有理由爲什麼這是一個壞主意？如果這是一個壞主意，爲什麼不用一個整型變量重載pow方法？對我來說，這似乎是一個高價值的優化，但我明白，有可能是我失蹤的東西。 –

Math.pow速度很慢，因爲它涉及一般意義上的等式，使用分數冪將它提升到給定的冪。這是計算時需要經歷的查找，需要更多時間。

簡單地將數字相乘通常會更快，因爲Java中的本地調用效率更高。

編輯：也可能值得注意的是，數學函數使用雙精度，這比使用整數還需要更長的時間。

來源

2016-01-06 16:46:59

Math.pow(x, y)是可能是實現爲exp(y log x)。這允許分數指數，並且非常快。

但是，如果您只需要小的積極積分參數，您就可以通過編寫自己的版本來打敗這種表現。

可以說Java可以爲你做這個檢查，但是對於那些內置版本更快的大整數來說可能會有一點意義。它也必須定義一個適當的整體回報類型和溢出的風險是顯而易見的。定義圍繞分支區域的行爲將會非常棘手。

順便說一下，你的整型版本可能會更快。通過平方對指數進行一些研究。

來源

2016-01-06 16:53:39 Bathsheba

爲什麼Math.pow（int，int）比我的天真執行慢？

回答

相關問題