Java中確定整數的平方根是否是整數
1.概述
理想平方是一個數字，可以表示為兩個相等整數的乘積。
在本文中，我們將發現多種方法來確定整數在Java中是否是理想的平方。另外，我們將討論每種技術的優缺點，以確定其效率，這是最快的。
2.檢查整數是否為完美平方
眾所周知，Java為定義整數提供了兩種數據類型。第一個是int ，它表示32位數字，而另一個是long ，它表示64位數字。在本文中，我們將使用long數據類型來處理最壞的情況（可能的最大整數）。
由於Java以64位表示長整數，因此長整數的範圍是-9,223,372,036,854,775,808到,223,372,036,854,775,807 。而且，由於我們要處理完美的平方，因此我們只關心處理正整數集，因為將任何整數自身相乘總是會產生一個正數。
另外，由於最大數目是2^63 ，這意味著大約2^31.5整數的平方小於2^63 。此外，我們可以假設擁有一個包含這些數字的查找表是無效的。
2.1。在Java中使用sqrt方法
檢查整數是否為理想平方的最簡單，最直接的方法是使用sqrt函數。眾所周知， sqrt函數返回一個double sqrt值。因此，我們需要做的就是將結果轉換為int並乘以它本身。然後，我們檢查結果是否等於開始的整數：
public static boolean isPerfectSquareByUsingSqrt(long n) {
if (n <= 0) {
return false;
}
double squareRoot = Math.sqrt(n);
long tst = (long)(squareRoot + 0.5);
return tst*tst == n;
}請注意，由於處理double精度值時可能遇到的精度誤差，我們可能需要將結果加0.5。有時，將整數分配給double變量時，可以用小數點表示。
例如，如果我們將數字3分配給double精度變量，則其值可能是3.00000001或2.99999999。因此，為避免這種表示方式，在將其強制轉換為long值之前，我們先添加0.5以確保獲得實際值。
另外，如果我們用一個數字測試sqrt函數，我們會注意到執行時間很快。另一方面，如果需要多次調用sqrt函數，並嘗試減少sqrt函數執行的操作數，則這種微優化實際上可能會有所作為。
2.2。使用二進制搜索
我們可以使用二進制搜索來查找數字的平方根，而無需使用sqrt函數。
由於該數字的範圍是1到2 63 ，所以根在1到2 31.5之間。因此，二分查找算法需要約16次迭代才能獲得平方根：
public boolean isPerfectSquareByUsingBinarySearch(long low, long high, long number) {
long check = (low + high) / 2L;
if (high < low) {
return false;
}
if (number == check * check) {
return true;
}
else if (number < check * check) {
high = check - 1L;
return isPerfectSquareByUsingBinarySearch(low, high, number);
}
else {
low = check + 1L;
return isPerfectSquareByUsingBinarySearch(low, high, number);
}
}2.3。二進制搜索的增強
為了增強二進制搜索，我們可以注意到，如果我們確定基本數的位數，則可以確定根的範圍。
例如，如果數字僅由一位數字組成，則平方根的範圍在1到4之間。原因是，一位數字的最大整數為9，其根為3。此外，如果數字為由兩位數字組成，範圍在4到10之間，依此類推。
因此，我們可以構建一個查找表，以基於開頭的數字的位數來指定平方根的範圍。這將減少二進制搜索的範圍。因此，將需要較少的迭代來獲得平方根：
public class BinarySearchRange {
private long low;
private long high;
// standard constructor and getters
}private void initiateOptimizedBinarySearchLookupTable() {
lookupTable.add(new BinarySearchRange());
lookupTable.add(new BinarySearchRange(1L, 4L));
lookupTable.add(new BinarySearchRange(3L, 10L));
for (int i = 3; i < 20; i++) {
lookupTable.add(
new BinarySearchRange(
lookupTable.get(i - 2).low * 10,
lookupTable.get(i - 2).high * 10));
}
}public boolean isPerfectSquareByUsingOptimizedBinarySearch(long number) {
int numberOfDigits = Long.toString(number).length();
return isPerfectSquareByUsingBinarySearch(
lookupTable.get(numberOfDigits).low,
lookupTable.get(numberOfDigits).high,
2.4。整數算法的牛頓法
通常，我們可以使用牛頓法來獲得任何數字的平方根，甚至是非整數。牛頓法的基本思想是假設數字X是數字N平方根。之後，我們可以開始循環並繼續計算根，該根肯定會朝N的正確平方根移動。
但是，通過對牛頓方法進行一些修改，我們可以使用它來檢查整數是否是理想的平方：
public static boolean isPerfectSquareByUsingNewtonMethod(long n) {
long x1 = n;
long x2 = 1L;
while (x1 > x2) {
x1 = (x1 + x2) / 2L;
x2 = n / x1;
}
return x1 == x2 && n % x1 == 0L;
}3.優化整數平方根算法
正如我們所討論的，有多種算法可以檢查整數的平方根。儘管如此，我們始終可以通過一些技巧來優化任何算法。
技巧應考慮避免執行將確定平方根的主要操作。例如，我們可以直接排除負數。
我們可以使用的事實之一是“完美的平方只能以16為底的0、1、4或9結尾” 。因此，我們可以在開始計算之前將整數轉換為以16為底的整數。之後，我們排除將數字視為不完美平方根的情況：
public static boolean isPerfectSquareWithOptimization(long n) {
if (n < 0) {
return false;
}
switch((int)(n & 0xF)) {
case 0: case 1: case 4: case 9:
long tst = (long)Math.sqrt(n);
return tst*tst == n;
default:
return false;
}
}4。結論
在本文中，我們討論了確定整數是否為完美平方的多種方法。如我們所見，我們總是可以通過一些技巧來增強算法。
這些技巧將在開始算法的主要操作之前排除大量情況。原因是可以很容易地將許多整數確定為不完美的平方。