如何找到Java BigInteger的平方根？

Question

是否有一个库可以找到BigInteger的平方根？我希望它离线计算 - 只有一次,而不是在任何循环内.所以即使是计算成本高昂的解决方案也没关系

我不想找到一些算法和实现.一个现成的解决方案将是完美的.

Answer 1

纯娱乐:

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;
    }
}

Answer 2

我知道你的问题没有库解决方案.您必须从某处导入外部库解决方案.我在下面给你的内容不如获得外部库那么复杂.

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

这些方法很简单,迭代会非常非常快地收敛到最接近的整数答案.如果你试图给他们一个负面的参数,他们会抛出IllegalArgumentException.您可以将异常更改为另一个异常,但必须确保negatve参数抛出某种异常或至少不尝试计算.由于我们不在虚数的范围内,所以不存在负数的整数平方根.

这些算法来自于众所周知的简单迭代整数平方根算法,这些算法已经在手工计算中使用了几个世纪.它通过平均过高估计和低估来收敛到更好的估计.这可以重复,直到估计值尽可能接近.

它们基于y1 =((x/y0)+ y0)/ 2收敛到最大整数yn,其中yn*yn <= x.

这将为您提供BigInteger平方根y的底值,其中y*y <= x且(y + 1)*(y + 1)> x.

自适应可以为BigInteger平方根y提供x的上限值,其中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

Answer 3

奇怪的是，没有人提到它，但是在Java 9中，BigInteger中有sqrt，因此您可以像这样使用它：

BigInteger nine = BigInteger.valueOf(9);
BigInteger three = nine.sqrt();

https://docs.oracle.com/javase/9​​/docs/api/java/math/BigInteger.html#sqrt--

Answer 4

我无法验证它们的准确性,但谷歌搜索时有几种本土解决方案.其中最好的似乎就是这个:http://www.merriampark.com/bigsqrt.htm

还可以尝试Apache commons Math项目(一旦Apache在JCP博客文章之后从其轰炸中恢复).

Answer 5

正如Jigar所说，牛顿迭代非常容易理解和实现。我将让其他人决定它是否是求数字平方根的最有效算法。

通过递归，只需大约两行即可完成。

private static BigInteger newtonIteration(BigInteger n, BigInteger x0)
{
    final BigInteger x1 = n.divide(x0).add(x0).shiftRight(1);
    return x0.equals(x1)||x0.equals(x1.subtract(BigInteger.ONE)) ? x0 : newtonIteration(n, x1);
}

其中n是我们想要求平方根的数字，x0是上一次调用的数字，当从另一个方法发起第一次调用时，它始终为 1。所以最好你也用这样的东西来补充它；

public static BigInteger sqrt(final BigInteger number)
{
    if(number.signum() == -1)
        throw new ArithmeticException("We can only calculate the square root of positive numbers.");
    return newtonIteration(number, BigInteger.ONE);
}