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。结论
在本文中，我们讨论了确定整数是否为完美平方的多种方法。如我们所见，我们总是可以通过一些技巧来增强算法。
这些技巧将在开始算法的主要操作之前排除大量情况。原因是可以很容易地将许多整数确定为不完美的平方。
0 评论