如何findJava BigInteger的平方根？

有没有一个库可以findBigInteger的平方根？ 我希望它脱机计算 – 只有一次，而不是在任何循环内。 所以即使计算上昂贵的解决scheme也没关系。

我不想find一些algorithm和实现。 现成的解决scheme将是完美的。

Answer 1

我知道你的问题没有图书馆的解决scheme。 您必须从某处导入外部库解决scheme。 下面我给你的东西比得到外部图书馆要简单得多。

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

方法很简单，迭代收敛到最接近的整数，非常快。 如果你试图给他们一个负面的论点，他们会抛出一个IllegalArgumentException。 您可以将exception更改为另一个exception，但必须确保negatve参数引发某种exception，或者至less不会尝试计算。 负数的整数平方根不存在，因为我们不在虚数的范围内。

这些来自非常有名的简单迭代整数平方根algorithm，几百年来一直用于手工计算。 它通过平均高估和低估来工作，以收敛到更好的估计。 这可能会重复，直到估计尽可能接近预期。

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

这将给出一个BigInteger平方根y的x的底值，其中y * y <= x且（y + 1）*（y + 1）> x。

一个适应可以给你一个BigInteger平方根的上限值，其中y * y> = x和（y-1）*（y-1）<x

两种方法都经过testing和工作。 他们在这里：

 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 2

只是为了好玩：

 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 3

我无法validation他们的准确性，但有一些在谷歌search的解决scheme。 他们最好的似乎是这一个： http : //www.merriampark.com/bigsqrt.htm

也可以尝试Apache的Commons Math项目（一旦Apache从JCP博客文章的轰炸中恢复过来）。

Answer 4

我需要BigIntegers的平方根来实现二次筛。 我在这里使用了一些解决scheme，但到目前为止，绝对最快和最好的解决scheme来自Google Guava的BigInteger库。

文档可以在这里find。

Answer 5

正如Jigar所说的， 牛顿的迭代很容易理解和实现。 我会把它留给其他人来决定是否是最有效的algorithm或找不到数字的平方根。

recursion可以在两行左右完成。

 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是我们希望find的平方根的数字， 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); } 

Answer 6

对于初步猜测，我会使用Math.sqrt（bi.doubleValue（）），您可以使用已经build议的链接来使答案更准确。

Answer 7

这是我find的最好的（也是最短的）工作解决scheme

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

我testing过了，它工作正常（而且似乎很快）

Answer 8

  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中编写了一个recursion的平方根查找程序。 您可以将BDtol更改为任何您想要的，但是运行速度相当快，因此给出了以下示例：

原始号146783911423364576743092537299333563769268393112173908757133540102089006265925538868650825438150202201473025

SQRT – > 383123885216472214589586756787577295328224028242477055.000000000

然后确认146783911423364576743092537299333563769268393112173908757133540102089006265925538868650825438150202201473025.000000000000000000

Answer 9

另一种方法很轻。 速度方面，Mantono的答案，使用牛顿法，可能会更适合某些情况。

这是我的方法

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

Answer 10

我只是走平方根的整数部分，但你可以修改这个粗略的algorithm，以尽可能多的精度，只要你想：

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

Answer 11

C＃语言的语法与Java相似。 我写了这个recursion的解决scheme。

  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平方根方法。

这很容易解决。 将第一种方法更改为以下给recursion部分呼吸的空间。

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

Answer 12

简化的吉姆回答和改进的性能。

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

Answer 13

你也可以用二分查找来findx的平方根，也可以把它乘以例如10 ^ 10，然后通过二分查找find一个像m这样的整数，因为m ^ 2

 System.out.println(m.divide(10^5)+"."+m.mod(10^5)); 

Answer 14

我正在研究分解，最后写了这个。

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

该方法可以像这样可视化：

希望这可以帮助！

Answer 15

一条线可以做我认为的工作。

 Math.pow(bigInt.doubleValue(), (1/n));