如何找到 Java BigInteger 的平方根？

只是为了好玩：

public static BigInteger sqrt(BigInteger x) {
    BigInteger div = BigInteger.ZERO.setBit(x.bitLength()/2);
    BigInteger div2 = div;
    // Loop until we hit the same value twice in a row, or wind
    // up alternating.
    for(;;) {
        BigInteger y = div.add(x.divide(div)).shiftRight(1);
        if (y.equals(div) || y.equals(div2))
            return y;
        div2 = div;
        div = y;
    }
}

我知道没有库解决方案可以解决您的问题。您必须从某个位置导入外部库解决方案。我在下面给你的东西比获得外部库更简单。

可以使用如下所示的两个静态方法在类中创建自己的外部库解决方案，并将其添加到外部库集合中。这些方法不需要是实例方法，因此它们是静态的，方便的是，您不必实例化类即可使用它们。整数平方根的范数是一个下限值（即小于或等于平方根的最大整数），因此可能只需要一种静态方法，即下限方法，在下面的类中对于下限值，可以选择忽略上限（即小于或等于平方根的最小整数）方法版本。现在，它们位于默认包中，但您可以添加一个 package 语句以将它们放在您认为方便的任何包中。

这些方法非常简单，迭代非常非常快速地收敛到最接近的整数答案。如果你试图给他们一个否定的论点，他们会抛出一个非法的论据。您可以将异常更改为另一个异常，但必须确保否定参数引发某种异常，或者至少不会尝试计算。负数的整数平方根不存在，因为我们不在虚数的领域。

这些来自非常著名的简单迭代整数平方根算法，这些算法已经在手工计算中使用了几个世纪。它的工作原理是平均高估和低估，以收敛到更好的估计。可以重复此操作，直到估计值达到所需的水平。

它们基于 y1 = （（x/y0） + y0） / 2 收敛到最大整数 yn，其中 yn * yn <= x。

这将为您提供 x 的 BigInteger 平方根 y 的底值，其中 y * y <= x 和 （y + 1） * （y + 1） > x。

自适应可以为您提供 x 的 BigInteger 平方根 y 的上限值，其中 y * y >= x 和 （y - 1） * （y - 1） < x

这两种方法都经过测试并有效。他们在这里：

import java.math.BigInteger;

public class BigIntSqRoot {

public static BigInteger bigIntSqRootFloor(BigInteger x)
        throws IllegalArgumentException {
    if (x.compareTo(BigInteger.ZERO) < 0) {
        throw new IllegalArgumentException("Negative argument.");
    }
    // square roots of 0 and 1 are trivial and
    // y == 0 will cause a divide-by-zero exception
    if (x .equals(BigInteger.ZERO) || x.equals(BigInteger.ONE)) {
        return x;
    } // end if
    BigInteger two = BigInteger.valueOf(2L);
    BigInteger y;
    // starting with y = x / 2 avoids magnitude issues with x squared
    for (y = x.divide(two);
            y.compareTo(x.divide(y)) > 0;
            y = ((x.divide(y)).add(y)).divide(two));
    return y;
} // end bigIntSqRootFloor

public static BigInteger bigIntSqRootCeil(BigInteger x)
        throws IllegalArgumentException {
    if (x.compareTo(BigInteger.ZERO) < 0) {
        throw new IllegalArgumentException("Negative argument.");
    }
    // square roots of 0 and 1 are trivial and
    // y == 0 will cause a divide-by-zero exception
    if (x == BigInteger.ZERO || x == BigInteger.ONE) {
        return x;
    } // end if
    BigInteger two = BigInteger.valueOf(2L);
    BigInteger y;
    // starting with y = x / 2 avoids magnitude issues with x squared
    for (y = x.divide(two);
            y.compareTo(x.divide(y)) > 0;
            y = ((x.divide(y)).add(y)).divide(two));
    if (x.compareTo(y.multiply(y)) == 0) {
        return y;
    } else {
        return y.add(BigInteger.ONE);
    }
} // end bigIntSqRootCeil
} // end class bigIntSqRoot