Java之判断大整数是否为平方数

2018-08-19 本文已影响163人山阴少年

在本篇博客中，我们将讨论如何使用有效的算法来判断一个大整数是否为平方数。
给定正整数 $n$ ,如果存在一个整数 $m$ ，满足 $m^{2}=n$ ，那么则称 $n$ 为平方数。因此，判断一个大整数 $n$ 是否为平方数，很自然的想法就是，从1开始，依次递增，判断这个数的平方是否等于给定的数 $n$ ，如果是，则 $n$ 为平方数，如果这个数的平方大于 $n$ ，则 $n$ 不是平方数。这个想法很简单，但可惜的是，效率却很低，因为我们要遍历 $\sqrt{n}$ 个数，当 $n$ 很大时，这样的效率是我们不能忍受的。
那么有没有其他方法呢？这时候，一个公式进入我们的视野，那就是：

$1+3+5+...+2n-1=n^{2}.$

看上去这个公式给了我们一点希望，因为我们不需要从1开始一个一个去找，而是只需要寻找至 $2\sqrt{n}-1$ 即可。但我们仔细地分析一下，不难发现，该公式的实质和一个一个找没什么区别，因为我们还是要遍历 $\sqrt{n}$ 个数。
所以，存在有效的算法吗？答案是肯定的！为什么不尝试着去计算 $n$ 的平方根呢？按照这个思路，我们具体的算法，结合牛顿法，步骤如下：

初始值 $x_0=1$ , 误差 $\epsilon$ 足够小；
按照 $x_{n+1}=\frac{1}{2}(x_{n}+\frac{n}{x_{n}})$ 迭代，直至 $|x_{n}^{2}-n|\leq\epsilon$ ;
对 $x_{n}$ 取整，结果为 $m$ ，如果 $m$ 的平方为 $n$ ，则 $n$ 为平方数，否则不是平方数。

接下来，我们证明这个算法的有效性。首先，我们证明对于 $n\geq1$ ，都有 $x_{n} > \sqrt{n}$ 。我们使用数学归纳法。

当 $n=1$ 时， $x_{1}=\frac{1}{2}(1+n)>\sqrt{n}$ .
假设 $x_{n}>\sqrt{n}$ ,则 $x_{n+1}-\sqrt{n}=\frac{x_{n}^{2}+n-2\sqrt{n}x_{n}}{2x_{n}}=\frac{(x_{n}-\sqrt{n})^{2}}{2x_{n}}>0$ ,所以 $x_{n+1}>\sqrt{n}$ .

接着我们再证明 $x_{n}(n\geq1)$ 序列递减。因为当 $n>0$ 时，有
$x_{n+1}-x_{n}=\frac{n-x_{n}^{2}}{2x_{n}}<0.$
这是因为当 $n\geq1$ 时，有 $x_{n}>\sqrt{n}$ .

因此，我们利用第二步的迭代，不停地运算后，所得到的项 $x_{n}$ 与 $\sqrt{n}$ 很接近，只是稍微大一点。因此，该算法的第三步的判断就是正确的了。
下面我们将会给出上述算法的Java程序代码，具体如下：

package Problems;

import java.math.BigInteger;
import java.math.BigDecimal;

public class IS_Square {
    public static void main(String[] args) {

        // 计算2**128+1
        BigInteger F7 = new BigInteger("2").pow(128).add(BigInteger.ONE);
        boolean w = is_square(F7);
        if(w)
            System.out.println(String.format("%s是完全平方数。", F7));
        else
            System.out.println(String.format("%s不是完全平方数。", F7));

    }

    // 判断是否为完全平方数
    public static boolean is_square(BigInteger F7){
        // 牛顿法求解平方根, 求解a的平方根
        // x为a的平方根，x的初始值为1， 按x = (x+a/x)/2迭代， 误差为error
        BigDecimal x = BigDecimal.ONE;
        BigDecimal a = new BigDecimal(F7.toString());
        BigDecimal eps = new BigDecimal("1");
        final BigDecimal error = new BigDecimal("1E-10");
        int scale = 100;

        // 进入循环
        while(eps.compareTo(error) == 1){ // eps > error
            x = x.add(a.divide(x, scale, BigDecimal.ROUND_HALF_UP)).divide(new BigDecimal("2.0"), scale, BigDecimal.ROUND_HALF_UP);
            eps = x.multiply(x).subtract(a).abs();
        }

        BigInteger sqrt = x.toBigInteger();  // 求平方根的整数部分
        if(sqrt.pow(2).compareTo(F7) == 0)
            return true;
        else
            return false;

    }

}

其输出结果如下：

340282366920938463463374607431768211457不是完全平方数。

如果将Java程序中的 $F7=2^{128}$ ,则输出结果为：

340282366920938463463374607431768211456是完全平方数。

本次分享到此结束，欢迎大家交流~

Java之判断大整数是否为平方数

猜你喜欢

热点阅读