拨开荷叶行,寻梦已然成。仙女莲花里,翩翩白鹭情。
IMG-LOGO
主页 文章列表 Java中确定整数的平方根是否是整数

Java中确定整数的平方根是否是整数

白鹭 - 2021-11-24 543 0 0

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 评论

发表评论

您的电子邮件地址不会被公开。 必填的字段已做标记 *