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

不念不忘少年蓝@ 2022-05-16 09:57 389阅读 0赞

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

1\+3\+5\+...\+2n−1=n2. 1 \+ 3 \+ 5 \+ . . . \+ 2 n − 1 =n2.

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

1.  初始值x0=1 x 0= 1, 误差ϵ  ϵ 足够小；
    
     *  按照xn\+1=12(xn\+nxn)  x n + 1 = 1 2 ( x n + n x n ) 迭代，直至|x2n−n|≤ϵ  | x n 2 − n | ≤ ϵ ;
     *  对xn  x n 取整，结果为m  m ， 如果m m的平方为n  n ，则n n为平方数，否则不是平方数。
     *    接下来，我们证明这个算法的有效性。首先，我们证明对于n≥1  n ≥ 1 ，都有xn>n−−√  x n > n 。我们使用数学归纳法。
        
        1.  当n=1  n = 1 时，x1=12(1\+n)>n−−√  x 1 = 1 2 ( 1 + n ) > n .
        2.  假设xn>n−−√  x n > n ,则xn\+1−n−−√=x2n\+n−2n√xn2xn=(xn−n√)22xn>0  x n + 1 − n = x n 2 + n − 2 n x n 2 x n = ( x n − n ) 2 2 x n > 0 ,所以xn\+1>n−−√  x n + 1 > n .
        
        接着我们再证明xn(n≥1)  x n ( n ≥ 1 ) 序列递减。因为当n>0  n > 0 时，有  
        
        
        xn\+1−xn=n−x2n2xn<0.  x n + 1 − x n = n − x n 2 2 x n < 0. 
        
          
        这是因为当  n≥1  n ≥ 1 时，有  xn>n−−√  x n > n .
        
          因此，我们利用第二步的迭代，不停地运算后，所得到的项xn  x n 与n−−√  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=2128  F 7 = 2 128 ,则输出结果为：
        
            340282366920938463463374607431768211456是完全平方数。
        
          本次分享到此结束，欢迎大家交流~