是否有一个库可以找到 BigInteger 的平方根？我希望它离线计算 - 只计算一次，而不是在任何循环内。因此，即使是计算昂贵的解决方案也可以。
我不想找到一些算法并实现。一个现成的解决方案将是完美的。
user529141
问问题
53894 次
19 回答
39
纯娱乐：
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;
}
}
于 2013-05-29T01:25:17.553 回答
20
我知道您的问题没有图书馆解决方案。您必须从某处导入外部库解决方案。我在下面给您的内容比获取外部库要简单。
您可以使用如下所示的两个静态方法在一个类中创建自己的外部库解决方案，并将其添加到您的外部库集合中。这些方法不需要是实例方法，因此它们是静态的，而且方便的是，您不必实例化类来使用它们。整数平方根的范数是一个底值（即小于或等于平方根的最大整数），因此您可能只需要下面类中的一个静态方法，底值方法，并且可以选择忽略上限（即大于或等于平方根的最小整数）方法版本。现在，它们在默认包中，但您可以添加一个包语句将它们放在您认为方便的任何包中。
这些方法非常简单，迭代非常非常快地收敛到最接近的整数答案。如果你试图给他们一个否定的论点，他们会抛出一个 IllegalArgumentException。您可以将异常更改为另一个异常，但您必须确保否定参数引发某种异常或至少不尝试计算。负数的整数平方根不存在，因为我们不在虚数领域。
这些来自众所周知的简单迭代整数平方根算法，这些算法已在手动计算中使用了几个世纪。它通过平均高估和低估来收敛到更好的估计。这可以重复，直到估计与期望的一样接近。
它们基于 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
于 2012-08-15T00:42:28.633 回答
12
奇怪的是之前没有人提到它，但是在 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--
编辑-1
补充说这个函数还有另一种风格，除了平方根，还返回余数。
sqrtAndRemainder() BigInteger[] Returns an array of two BigIntegers containing the integer square root s of this and its remainder this - s*s, respectively.
于 2018-09-13T08:26:30.140 回答
5
我无法验证它们的准确性，但在谷歌搜索时有几种本土解决方案。其中最好的似乎是这个：http ://www.merriampark.com/bigsqrt.htm
还可以尝试 Apache commons Math 项目（一旦 Apache 在 JCP 博客文章之后从轰炸中恢复过来）。
于 2010-12-10T10:34:28.983 回答
4
对于我会使用的初步猜测Math.sqrt(bi.doubleValue())，您可以使用已经建议的链接来使答案更准确。
于 2010-12-10T10:35:49.803 回答
4
正如Jigar所说，Newton 的迭代非常易于理解和实现。我将由其他人决定它是否是查找数字平方根的最有效算法。
使用递归，只需大约两行即可完成。
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);
}
于 2016-01-13T23:58:07.040 回答
3
我需要 BigIntegers 的平方根来实现二次筛。我在这里使用了一些解决方案，但迄今为止绝对最快和最好的解决方案来自 Google Guava 的 BigInteger 库。
文档可以在这里找到。
于 2014-11-12T20:28:31.523 回答
2
另一种方法，它很轻。速度方面，曼托诺的答案使用牛顿法，在某些情况下可能更可取。
这是我的方法...
public static BigInteger sqrt(BigInteger n) {
BigInteger a = BigInteger.ONE;
BigInteger b = n.shiftRight(1).add(new BigInteger("2")); // (n >> 1) + 2 (ensure 0 doesn't show up)
while (b.compareTo(a) >= 0) {
BigInteger mid = a.add(b).shiftRight(1); // (a+b) >> 1
if (mid.multiply(mid).compareTo(n) > 0)
b = mid.subtract(BigInteger.ONE);
else
a = mid.add(BigInteger.ONE);
}
return a.subtract(BigInteger.ONE);
}
于 2016-03-23T20:15:39.163 回答
1
简化了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;
}
}
于 2015-01-24T01:04:40.883 回答
1
这是我找到的最好（也是最短）的工作解决方案
http://faruk.akgul.org/blog/javas-missing-algorithm-biginteger-sqrt/
这是代码：
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);
}
我已经测试过了，它工作正常（而且看起来很快）
于 2013-03-23T20:16:39.007 回答
1
更新（2018 年 7 月 23 日）：此技术不适用于较大的值。在下面发布了一种基于二进制搜索的不同技术。
我正在研究因式分解并最终写了这个。
package com.example.so.math;
import java.math.BigInteger;
/**
*
* <p>https://stackoverflow.com/questions/4407839/how-can-i-find-the-square-root-of-a-java-biginteger</p>
* @author Ravindra
* @since 06August2017
*
*/
public class BigIntegerSquareRoot {
public static void main(String[] args) {
int[] values = {5,11,25,31,36,42,49,64,100,121};
for (int i : values) {
BigInteger result = handleSquareRoot(BigInteger.valueOf(i));
System.out.println(i+":"+result);
}
}
private static BigInteger handleSquareRoot(BigInteger modulus) {
int MAX_LOOP_COUNT = 100; // arbitrary for now.. but needs to be proportional to sqrt(modulus)
BigInteger result = null;
if( modulus.equals(BigInteger.ONE) ) {
result = BigInteger.ONE;
return result;
}
for(int i=2;i<MAX_LOOP_COUNT && i<modulus.intValue();i++) { // base-values can be list of primes...
//System.out.println("i"+i);
BigInteger bigIntegerBaseTemp = BigInteger.valueOf(i);
BigInteger bigIntegerRemainderTemp = bigIntegerBaseTemp.modPow(modulus, modulus);
BigInteger bigIntegerRemainderSubtractedByBase = bigIntegerRemainderTemp.subtract(bigIntegerBaseTemp);
BigInteger bigIntegerRemainderSubtractedByBaseFinal = bigIntegerRemainderSubtractedByBase;
BigInteger resultTemp = null;
if(bigIntegerRemainderSubtractedByBase.signum() == -1 || bigIntegerRemainderSubtractedByBase.signum() == 1) {
bigIntegerRemainderSubtractedByBaseFinal = bigIntegerRemainderSubtractedByBase.add(modulus);
resultTemp = bigIntegerRemainderSubtractedByBaseFinal.gcd(modulus);
} else if(bigIntegerRemainderSubtractedByBase.signum() == 0) {
resultTemp = bigIntegerBaseTemp.gcd(modulus);
}
if( resultTemp.multiply(resultTemp).equals(modulus) ) {
System.out.println("Found square root for modulus :"+modulus);
result = resultTemp;
break;
}
}
return result;
}
}
该方法可以像这样可视化：
希望这可以帮助！
于 2017-08-06T19:10:02.517 回答
1
BigDecimal BDtwo = new BigDecimal("2");
BigDecimal BDtol = new BigDecimal(".000000001");
private BigDecimal bigIntSQRT(BigDecimal lNew, BigDecimal lOld, BigDecimal n) {
lNew = lOld.add(n.divide(lOld, 9, BigDecimal.ROUND_FLOOR)).divide(BDtwo, 9, BigDecimal.ROUND_FLOOR);
if (lOld.subtract(lNew).abs().compareTo(BDtol) == 1) {
lNew = bigIntSQRT(lNew, lNew, n);
}
return lNew;
}
我只是在解决这个问题，并成功地用 Java 编写了一个递归平方根查找器。您可以将BDtol更改为您想要的任何内容，但这运行得相当快，结果给了我以下示例：
原号146783911423364576743092537299333563769268393112173908757133540102089006265925538868650825438150202201473025
SQRT --> 383123885216472214589586756787577295328224028242477055.000000000
然后确认 146783911423364576743092537299333563769268393112173908757133540102089006265925538868650825438150202201473025.000000000000000
于 2015-09-30T17:15:54.590 回答
0
我只研究平方根的整数部分，但你可以修改这个粗略的算法来达到你想要的更高的精度：
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;
}
于 2012-10-23T04:18:38.193 回答
0
这是一个不使用 BigInteger.multiply 或 BigInteger.divide 的解决方案：
private static final BigInteger ZERO = BigInteger.ZERO;
private static final BigInteger ONE = BigInteger.ONE;
private static final BigInteger TWO = BigInteger.valueOf(2);
private static final BigInteger THREE = BigInteger.valueOf(3);
/**
* This method computes sqrt(n) in O(n.bitLength()) time,
* and computes it exactly. By "exactly", I mean it returns
* not only the (floor of the) square root s, but also the
* remainder r, such that r >= 0, n = s^2 + r, and
* n < (s + 1)^2.
*
* @param n The argument n, as described above.
*
* @return An array of two values, where the first element
* of the array is s and the second is r, as
* described above.
*
* @throws IllegalArgumentException if n is not nonnegative.
*/
public static BigInteger[] sqrt(BigInteger n) {
if (n == null || n.signum() < 0) {
throw new IllegalArgumentException();
}
int bl = n.bitLength();
if ((bl & 1) != 0) {
++ bl;
}
BigInteger s = ZERO;
BigInteger r = ZERO;
while (bl >= 2) {
s = s.shiftLeft(1);
BigInteger crumb = n.testBit(-- bl)
? (n.testBit(-- bl) ? THREE : TWO)
: (n.testBit(-- bl) ? ONE : ZERO);
r = r.shiftLeft(2).add(crumb);
BigInteger d = s.shiftLeft(1);
if (d.compareTo(r) < 0) {
s = s.add(ONE);
r = r.subtract(d).subtract(ONE);
}
}
assert r.signum() >= 0;
assert n.equals(s.multiply(s).add(r));
assert n.compareTo(s.add(ONE).multiply(s.add(ONE))) < 0;
return new BigInteger[] {s, r};
}
于 2018-03-24T06:46:17.007 回答
0
您还可以使用二进制搜索来查找 x 的平方根，也可以将其乘以例如 10^10 并通过二进制搜索找到像 m 这样的整数，因为 m^2
System.out.println(m.divide(10^5)+"."+m.mod(10^5));于 2016-03-26T16:41:31.723 回答
0
我在上面发布的答案不适用于大量数字（但有趣的是！）。因此，发布了一种二进制搜索方法来确定平方根的正确性。
package com.example.so.squareroot;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
/**
* <p>https://stackoverflow.com/questions/4407839/how-can-i-find-the-square-root-of-a-java-biginteger</p>
* <p> Determine square-root of a number or its closest whole number (binary-search-approach) </p>
* @author Ravindra
* @since 07-July-2018
*
*/
public class BigIntegerSquareRootV2 {
public static void main(String[] args) {
List<BigInteger> listOfSquares = new ArrayList<BigInteger>();
listOfSquares.add(BigInteger.valueOf(5).multiply(BigInteger.valueOf(5)).pow(2));
listOfSquares.add(BigInteger.valueOf(11).multiply(BigInteger.valueOf(11)).pow(2));
listOfSquares.add(BigInteger.valueOf(15485863).multiply(BigInteger.valueOf(10000019)).pow(2));
listOfSquares.add(BigInteger.valueOf(533000401).multiply(BigInteger.valueOf(982451653)).pow(2));
listOfSquares.add(BigInteger.valueOf(11).multiply(BigInteger.valueOf(23)));
listOfSquares.add(BigInteger.valueOf(11).multiply(BigInteger.valueOf(23)).pow(2));
for (BigInteger bigIntegerNumber : listOfSquares) {
BigInteger squareRoot = calculateSquareRoot(bigIntegerNumber);
System.out.println("Result :"+bigIntegerNumber+":"+squareRoot);
}
System.out.println("*********************************************************************");
for (BigInteger bigIntegerNumber : listOfSquares) {
BigInteger squareRoot = determineClosestWholeNumberSquareRoot(bigIntegerNumber);
System.out.println("Result :"+bigIntegerNumber+":"+squareRoot);
}
}
/*
Result :625:25
Result :14641:121
Result :23981286414105556927200571609:154858924231397
Result :274206311533451346298141971207799609:523647125012112853
Result :253:null
Result :64009:253
*/
public static BigInteger calculateSquareRoot(BigInteger number) {
/*
* Can be optimized by passing a bean to store the comparison result and avoid having to re-calculate.
*/
BigInteger squareRootResult = determineClosestWholeNumberSquareRoot(number);
if( squareRootResult.pow(2).equals(number)) {
return squareRootResult;
}
return null;
}
/*
Result :625:25
Result :14641:121
Result :23981286414105556927200571609:154858924231397
Result :274206311533451346298141971207799609:523647125012112853
Result :253:15
Result :64009:253
*/
private static BigInteger determineClosestWholeNumberSquareRoot(BigInteger number) {
BigInteger result = null;
if(number.equals(BigInteger.ONE)) {
return BigInteger.ONE;
} else if( number.equals(BigInteger.valueOf(2)) ) {
return BigInteger.ONE;
} else if( number.equals(BigInteger.valueOf(3)) ) {
return BigInteger.ONE;
} else if( number.equals(BigInteger.valueOf(4)) ) {
return BigInteger.valueOf(2);
}
BigInteger tempBaseLow = BigInteger.valueOf(2);
BigInteger tempBaseHigh = number.shiftRight(1); // divide by 2
int loopCount = 11;
while(true) {
if( tempBaseHigh.subtract(tempBaseLow).compareTo(BigInteger.valueOf(loopCount)) == -1 ) { // for lower numbers use for-loop
//System.out.println("Breaking out of while-loop.."); // uncomment-for-debugging
break;
}
BigInteger tempBaseMid = tempBaseHigh.subtract(tempBaseLow).shiftRight(1).add(tempBaseLow); // effectively mid = [(high-low)/2]+low
BigInteger tempBaseMidSquared = tempBaseMid.pow(2);
int comparisonResultTemp = tempBaseMidSquared.compareTo(number);
if(comparisonResultTemp == -1) { // move mid towards higher number
tempBaseLow = tempBaseMid;
} else if( comparisonResultTemp == 0 ) { // number is a square ! return the same !
return tempBaseMid;
} else { // move mid towards lower number
tempBaseHigh = tempBaseMid;
}
}
BigInteger tempBasePrevious = tempBaseLow;
BigInteger tempBaseCurrent = tempBaseLow;
for(int i=0;i<(loopCount+1);i++) {
BigInteger tempBaseSquared = tempBaseCurrent.pow(2);
//System.out.println("Squared :"+tempBaseSquared); // uncomment-for-debugging
int comparisonResultTempTwo = tempBaseSquared.compareTo(number);
if( comparisonResultTempTwo == -1 ) { // move current to previous and increment current...
tempBasePrevious = tempBaseCurrent;
tempBaseCurrent = tempBaseCurrent.add(BigInteger.ONE);
} else if( comparisonResultTempTwo == 0 ) { // is an exact match!
tempBasePrevious = tempBaseCurrent;
break;
} else { // we've identified the point of deviation.. break..
//System.out.println("breaking out of for-loop for square root..."); // uncomment-for-debugging
break;
}
}
result = tempBasePrevious;
//System.out.println("Returning :"+result); // uncomment-for-debugging
return result;
}
}
问候拉文德拉
于 2018-07-07T12:50:57.397 回答
0
这是一种易于理解的方法，可能没有最佳性能，但它在不到一秒的时间内为单个 BigInteger 提供了解决方案。
public static BigInteger sqrt(BigInteger n) {
BigInteger bottom = BigInteger.ONE;
BigInteger top = n;
BigInteger mid;
while(true) {
mid = top.add(bottom).divide(new BigInteger(""+2));
top = mid;
bottom = n.divide(top);
// System.out.println("top: "+top);
// System.out.println("mid: "+mid);
// System.out.println("bottom: "+bottom);
if(top.equals(bottom)) {
return top;
}
}
}
于 2020-04-30T20:05:32.437 回答
-1
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);
}
像这样调用这段代码（在Java中我猜它是“System.out.print”）。
Console.WriteLine(fsqrt(BigInteger.Parse("783648276815623658365871365876257862874628734627835648726")));
答案是：27993718524262253829858552106
免责声明：我了解此方法不适用于小于 10 的数字；这是一个 BigInteger 平方根方法。
这很容易补救。将第一种方法更改为以下方法，为递归部分提供一些喘息的空间。
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);
}
于 2014-07-31T21:30:14.977 回答
-2
一条线就可以完成我认为的工作。
Math.pow(bigInt.doubleValue(), (1/n));
于 2012-12-02T01:23:48.670 回答