BigInteger の平方根を見つけるライブラリはありますか? オフラインで計算したい-ループ内ではなく、1回だけ。したがって、計算コストの高いソリューションでも問題ありません。
アルゴリズムを見つけて実装したくありません。すぐに利用できるソリューションが最適です。
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
あなたの質問に対するライブラリソリューションはありません。どこかから外部ライブラリ ソリューションをインポートする必要があります。以下に示すことは、外部ライブラリを取得するよりも簡単です。
以下に示すように、2 つの静的メソッドを持つクラスで独自の外部ライブラリ ソリューションを作成し、それを外部ライブラリのコレクションに追加できます。メソッドはインスタンス メソッドである必要はなく、静的であり、便利なことに、それらを使用するためにクラスをインスタンス化する必要はありません。整数の平方根のノルムはフロア値 (つまり、平方根以下の最大の整数) であるため、フロア値に対して以下のクラスで 1 つの静的メソッド (フロア メソッド) のみが必要な場合があり、選択することができます。シーリング (つまり、平方根以上の最小の整数) メソッド バージョンを無視します。現在、それらはデフォルトのパッケージにありますが、package ステートメントを追加して、便利なパッケージに入れることができます。
メソッドは非常にシンプルで、反復は最も近い整数の答えに非常に高速に収束します。負の引数を指定しようとすると、IllegalArgumentException がスローされます。例外を別のものに変更できますが、負の引数が何らかの例外をスローするか、少なくとも計算を試行しないようにする必要があります。虚数の領域にないため、負の数の整数平方根は存在しません。
これらは、何世紀にもわたって手計算で使用されてきた、非常によく知られている単純な反復整数平方根アルゴリズムに由来します。過大評価と過小評価を平均して、より良い推定値に収束させることで機能します。これは、推定値が希望どおりになるまで繰り返されます。
これらは、y1 = ((x/y0) + y0) / 2 に基づいて、最大の整数 yn に収束します。ここで、yn * yn <= x です。
これにより、y * y <= x および (y + 1) * (y + 1) > x である x の BigInteger 平方根 y のフロア値が得られます。
適応により、y * y >= x および (y - 1) * (y - 1) < x である x の BigInteger 平方根 y の上限値を得ることができます。
どちらの方法もテスト済みで、機能しています。それらはここにあります：
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 に答える
5
それらの正確性を確認することはできませんが、グーグルで検索すると、自家製のソリューションがいくつかあります。それらの中で最高のものはこれのようでした: http://www.merriampark.com/bigsqrt.htm
また、Apache commons Math プロジェクトを試してみてください (JCP ブログ投稿後に Apache が攻撃から回復したら)。
于 2010-12-10T10:34:28.983 に答える
4
私が使用する最初の推測ではMath.sqrt(bi.doubleValue())、すでに提案されているリンクを使用して、回答をより正確にすることができます。
于 2010-12-10T10:35:49.803 に答える
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
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
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
確認の ため
于 2015-09-30T17:15:54.590 に答える
0
また、バイナリ検索を使用して x の平方根を見つけることもできます。また、たとえば 10^10 に乗算し、m^2 であるため、バイナリ検索で m のような整数を見つけることもできます。
System.out.println(m.divide(10^5)+"."+m.mod(10^5));于 2016-03-26T16:41:31.723 に答える
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
私は平方根の整数部分までしか行っていませんが、この大まかなアルゴリズムを変更して、必要なだけ精度を上げることができます。
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 に答える
-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
1行で私が思う仕事をすることができます。
Math.pow(bigInt.doubleValue(), (1/n));
于 2012-12-02T01:23:48.670 に答える