如何找到 Java BigInteger 的平方根？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4407839/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How can I find the Square Root of a Java BigInteger?
提问by
Is there a library that will find the square root of a BigInteger? I want it computed offline - only once, and not inside any loop. So even computationally expensive solution is okay.
是否有一个库可以找到 BigInteger 的平方根？我希望它离线计算 - 只计算一次，而不是在任何循环内。因此，即使是计算上昂贵的解决方案也是可以的。
I don't want to find some algorithm and implement. A readily available solution will be perfect.
我不想找到一些算法并实现。一个现成的解决方案将是完美的。
回答by Martijn Verburg
I can't verify the accuracy of them but there are several home grown solutions when googling. The best of them seemed to be this one: http://www.merriampark.com/bigsqrt.htm
我无法验证它们的准确性，但在谷歌搜索时有几个本土解决方案。其中最好的似乎是这个：http: //www.merriampark.com/bigsqrt.htm
Also try the Apache commons Math project (once Apache recovers from its bombardment after the JCP blog post).
还可以尝试 Apache commons Math 项目（一旦 Apache 从 JCP 博客文章的轰炸中恢复过来）。
回答by Peter Lawrey
For an initial guess I would use Math.sqrt(bi.doubleValue())and you can use the links already suggested to make the answer more accurate.
对于我会使用的初步猜测Math.sqrt(bi.doubleValue())，您可以使用已经建议的链接来使答案更准确。
回答by Jim
I know of no library solution for your question. You'll have to import an external library solution from somewhere. What I give you below is less complicated than getting an external library.
我知道您的问题没有图书馆解决方案。您必须从某处导入外部库解决方案。我在下面给您的内容比获取外部库要简单。
You can create your own external library solution in a class with two static methods as shown below and add that to your collection of external libraries. The methods don't need to be instance methods and so they are static and, conveniently, you don't have to instance the class to use them. The norm for integer square roots is a floor value (i.e. the largest integer less than or equal to the square root), so you may need only the one static method, the floor method, in the class below for the floor value and can choose to ignore the ceiling (i.e. the smallest integer greater than or equal to the square root) method version. Right now, they are in the default package, but you can add a package statement to put them in whatever package you find convenient.
您可以在具有两个静态方法的类中创建自己的外部库解决方案，如下所示，并将其添加到您的外部库集合中。这些方法不需要是实例方法，因此它们是静态的，而且方便的是，您不必实例化类来使用它们。整数平方根的范数是一个下限值（即小于或等于平方根的最大整数），所以你可能只需要下面这个类中的一个静态方法，下限方法，下限值可以选择忽略上限（即大于或等于平方根的最小整数）方法版本。现在，它们位于默认包中，但您可以添加一个包语句，将它们放入您认为方便的任何包中。
The methods are dirt simple and the iterations converge to the closest integer answer very, very fast. They throw an IllegalArgumentException if you try to give them a negative argument. You can change the exception to another one, but you must ensure that a negatve argument throws some kind of exception or at least doesn't attempt the computation. Integer square roots of negative numbers don't exist since we are not in the realm of imaginary numbers.
这些方法非常简单，迭代非常非常快地收敛到最接近的整数答案。如果你试图给他们一个否定的参数，他们会抛出一个 IllegalArgumentException。您可以将异常更改为另一个异常，但必须确保否定参数会引发某种异常或至少不尝试计算。负数的整数平方根不存在，因为我们不在虚数领域。
These come from very well known simple iterative integer square root algorithms that have been used in hand computations for centuries. It works by averaging an overestimate and underestimate to converge to a better estimate. This may be repeated until the estimate is as close as is desired.
这些来自众所周知的简单迭代整数平方根算法，这些算法已在手工计算中使用了几个世纪。它的工作原理是平均高估和低估以收敛到更好的估计。这可以重复直到估计与期望的一样接近。
They are based on y1 = ((x/y0) + y0) / 2 converging to the largest integer, yn, where yn * yn <= x.
它们基于 y1 = ((x/y0) + y0) / 2 收敛到最大整数 yn，其中 yn * yn <= x。
This will give you a floor value for a BigInteger square root, y, of x where y * y <= x and (y + 1) * (y + 1) > x.
这将为您提供 x 的 BigInteger 平方根 y 的下限值，其中 y * y <= x 和 (y + 1) * (y + 1) > x。
An adaptation can give you a ceiling value for BigInteger square root, y, of x where y * y >= x and (y - 1) * (y - 1) < x
改编可以为您提供 BigInteger 平方根 y 的上限值，其中 y * y >= x 并且 (y - 1) * (y - 1) < x
Both methods have been tested and work. They are here:
这两种方法都经过测试并有效。他们在这里：
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
回答by Ustaman Sangat
I am only going as far as the integer part of the square root but you can modify this rough algo to go to as much more precision as you want:
我只考虑平方根的整数部分，但你可以修改这个粗略的算法，以达到你想要的尽可能多的精度：
public static void main(String args[]) {
BigInteger N = new BigInteger(
"17976931348623159077293051907890247336179769789423065727343008115"
+ "77326758055056206869853794492129829595855013875371640157101398586"
+ "47833778606925583497541085196591615128057575940752635007475935288"
+ "71082364994994077189561705436114947486504671101510156394068052754"
+ "0071584560878577663743040086340742855278549092581");
System.out.println(N.toString(10).length());
String sqrt = "";
BigInteger divisor = BigInteger.ZERO;
BigInteger toDivide = BigInteger.ZERO;
String Nstr = N.toString(10);
if (Nstr.length() % 2 == 1)
Nstr = "0" + Nstr;
for (int digitCount = 0; digitCount < Nstr.length(); digitCount += 2) {
toDivide = toDivide.multiply(BigInteger.TEN).multiply(
BigInteger.TEN);
toDivide = toDivide.add(new BigInteger(Nstr.substring(digitCount,
digitCount + 2)));
String div = divisor.toString(10);
divisor = divisor.add(new BigInteger(
div.substring(div.length() - 1)));
int into = tryMax(divisor, toDivide);
divisor = divisor.multiply(BigInteger.TEN).add(
BigInteger.valueOf(into));
toDivide = toDivide.subtract(divisor.multiply(BigInteger
.valueOf(into)));
sqrt = sqrt + into;
}
System.out.println(String.format("Sqrt(%s) = %s", N, sqrt));
}
private static int tryMax(final BigInteger divisor,
final BigInteger toDivide) {
for (int i = 9; i > 0; i--) {
BigInteger div = divisor.multiply(BigInteger.TEN).add(
BigInteger.valueOf(i));
if (div.multiply(BigInteger.valueOf(i)).compareTo(toDivide) <= 0)
return i;
}
return 0;
}
回答by Masudias
A single line can do the job I think.
一条线就可以完成我认为的工作。
Math.pow(bigInt.doubleValue(), (1/n));
回答by Eran Medan
This is the best (and shortest) working solution I've found
这是我发现的最好（也是最短）的工作解决方案
http://faruk.akgul.org/blog/javas-missing-algorithm-biginteger-sqrt/
http://faruk.akgul.org/blog/javas-missing-algorithm-biginteger-sqrt/
Here is the code:
这是代码：
public static BigInteger sqrt(BigInteger n) {
BigInteger a = BigInteger.ONE;
BigInteger b = new BigInteger(n.shiftRight(5).add(new BigInteger("8")).toString());
while(b.compareTo(a) >= 0) {
BigInteger mid = new BigInteger(a.add(b).shiftRight(1).toString());
if(mid.multiply(mid).compareTo(n) > 0) b = mid.subtract(BigInteger.ONE);
else a = mid.add(BigInteger.ONE);
}
return a.subtract(BigInteger.ONE);
}
I've tested it and it's working correctly (and seems fast)
我已经测试过它并且它工作正常（而且看起来很快）
回答by Edward Falk
Just for fun:
只是为了好玩：
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;
}
}
回答by kmillen
The C# language has similar syntax to Java. I wrote this recursive solution.
C# 语言的语法与 Java 相似。我写了这个递归解决方案。
static BigInteger fsqrt(BigInteger n)
{
string sn = n.ToString();
return guess(n, BigInteger.Parse(sn.Substring(0, sn.Length >> 1)), 0);
}
static BigInteger guess(BigInteger n, BigInteger g, BigInteger last)
{
if (last >= g - 1 && last <= g + 1) return g;
else return guess(n, (g + (n / g)) >> 1, g);
}
Call this code like this (in Java I guess it would be "System.out.print").
像这样调用这段代码（在 Java 中我猜它应该是“System.out.print”）。
Console.WriteLine(fsqrt(BigInteger.Parse("783648276815623658365871365876257862874628734627835648726")));
And the answer is: 27993718524262253829858552106
答案是：27993718524262253829858552106
Disclaimer: I understand this method doesn't work for numbers less than 10; this is a BigInteger square root method.
免责声明：我知道此方法不适用于小于 10 的数字；这是一个 BigInteger 平方根方法。
This is easily remedied. Change the first method to the following to give the recursive portion some room to breathe.
这很容易补救。将第一种方法更改为以下方法，以便为递归部分留出一些喘息的空间。
static BigInteger fsqrt(BigInteger n)
{
if (n > 999)
{
string sn = n.ToString();
return guess(n, BigInteger.Parse(sn.Substring(0, sn.Length >> 1)), 0);
}
else return guess(n, n >> 1, 0);
}
回答by Johan S
I needed to have the square root for BigIntegers for implementing the quadratic sieve. I used some of the solutions here but the absolutely fastest and best solution so far is from Google Guava's BigInteger library.
我需要有 BigIntegers 的平方根来实现二次筛。我在这里使用了一些解决方案，但迄今为止绝对最快和最好的解决方案来自 Google Guava 的 BigInteger 库。
Documentation can be found here.
文档可以在这里找到。
回答by Ilya Gazman
Simplified Jim answerand improved performance.
简化了Jim 的回答并提高了性能。
public class BigIntSqRoot {
private static BigInteger two = BigInteger.valueOf(2L);
public static BigInteger bigIntSqRootFloor(BigInteger x)
throws IllegalArgumentException {
if (checkTrivial(x)) {
return x;
}
if (x.bitLength() < 64) { // Can be cast to long
double sqrt = Math.sqrt(x.longValue());
return BigInteger.valueOf(Math.round(sqrt));
}
// starting with y = x / 2 avoids magnitude issues with x squared
BigInteger y = x.divide(two);
BigInteger value = x.divide(y);
while (y.compareTo(value) > 0) {
y = value.add(y).divide(two);
value = x.divide(y);
}
return y;
}
public static BigInteger bigIntSqRootCeil(BigInteger x)
throws IllegalArgumentException {
BigInteger y = bigIntSqRootFloor(x);
if (x.compareTo(y.multiply(y)) == 0) {
return y;
}
return y.add(BigInteger.ONE);
}
private static boolean checkTrivial(BigInteger x) {
if (x == null) {
throw new NullPointerException("x can't be null");
}
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 true;
} // end if
return false;
}
}
