確定整數的平方根是否為整數的最快方法是什麼？

一種最快地確定一個整數的平方根是否為整數的方法

問題說明

我正在尋找最快的方法來確定一個長整數是否為一個完全平方（即它的平方根是另一個整數）：

1. 我使用內建的Math.sqrt() 函數完成了它，但我很好奇是否有一種方法可以使用整數域來完成，從而提高速度。


2. 維護一個查找表是不切實際的（因為有大約 2^31.5 個整數的平方小於 2⁶³）。

以下是我現在完成它的非常簡單直接的方法：

public final static boolean isPerfectSquare(long n)<br>{<br> if (n <pre class="brush:php;toolbar:false">return false;

long tst = (long)(Math.sqrt(n) 0.5);
return tst*tst == n;
}

_{注意：我在許多Project Euler 問題中使用了這個函數。因此，以後將不會對這一段程式碼進行任何維護。而這種微型最佳化實際上可以帶來差異，因為挑戰的一部分是用不到一分鐘的時間完成每個演算法，而此函數需要在某些問題中被呼叫數百萬次。}

---

我已經嘗試了解決這個問題的不同方案：

• 經過詳盡的測試，我發現向 Math.sqrt() 的結果添加 0.5 is 不必要的，至少在我的機器上是這樣。


• 快速反平方根比 Math.sqrt() 快，但對於 n >= 410881 給出了不正確的結果。然而，正如 BobbyShaftoe 所建議的，我們可以為 n
  
• Newton's 方法比 Math.sqrt() 慢很多。這可能是因為 Math.sqrt() 使用類似於 Newton 方法的東西，但是在硬體中實現，因此比 Java 中的速度快得多。此外，Newton 方法仍需要使用雙精確度浮點數。


• 一種經過改進的Newton 方法，它利用了一些技巧，使其只需要進行整數運算，在避免溢出時也需要一些技巧（我希望該函數可以處理所有正的64 位元有符號整數），而且它比Math.sqrt() 慢。


• 二分查找甚至更慢。這是有道理的，因為二分查找平均需要進行 16 次傳遞才能找到 64 位數字的平方根。


• 根據 John 的測試，在 C 中使用或語句比使用開關速度更快，但在 Java 和 C# 中，或和開關之間似乎沒有區別。


• 我還嘗試製作一個查找表（作為 64 個布林值的私人靜態數組）。然後，不是使用 switch 或 or 語句，我會直接說 if(lookup[(int)(n&0x3F)]) { test } else return false;. 令我驚訝的是，這(略微)慢了一些。這是因為數組邊界在 Java 中是受檢的。

以上是確定整數的平方根是否為整數的最快方法是什麼？的詳細內容。更多資訊請關注PHP中文網其他相關文章！