Comment puis-je trouver la racine carrée d'un BigInteger Java?
y a-t-il une bibliothèque qui trouvera la racine carrée d'un BigInteger? Je veux qu'il calculées hors ligne - une seule fois, et pas à l'intérieur d'une boucle. Donc même une solution coûteuse sur le plan informatique est acceptable.
Je ne veux pas trouver d'algorithme et implémenter. Une solution facilement disponible sera parfaite.
18 réponses
Juste pour le 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;
}
}
Je ne connais pas de solution de bibliothèque pour votre question. Vous devrez importer une solution de bibliothèque externe de quelque part. Ce que je vous donne ci-dessous est moins compliqué que d'obtenir une bibliothèque externe.
vous pouvez créer votre propre solution de bibliothèque externe dans une classe avec deux méthodes statiques comme montré ci-dessous et ajouter cela à votre collection de bibliothèques externes. Les méthodes n'ont pas besoin d'être des méthodes d'instance et donc elles sont statiques et, commodément, vous n'avez pas à demandez à la classe de les utiliser. La norme pour les racines carrées entières est une valeur de plancher (c.-à-d. le plus grand nombre entier inférieur ou égal à la racine carrée), de sorte que vous pouvez avoir besoin seulement la méthode statique, la méthode de plancher, dans la classe ci-dessous pour la valeur de plancher et peut choisir d'ignorer le plafond (c.-à-d. le plus petit nombre entier supérieur ou égal à la racine carrée) version de la méthode. En ce moment, ils sont dans le paquet par défaut, mais vous pouvez ajouter une déclaration de paquet pour les mettre dans n'importe quel paquet que vous trouverez pratique.
les méthodes sont très simples et les itérations convergent vers la réponse entière la plus proche très, très rapide. Ils jettent un ArgumentException illégale si vous essayez de leur donner un argument négatif. Vous pouvez changer l'exception à une autre, mais vous devez vous assurer qu'un argument negatve lance une sorte d'exception ou au moins ne tente pas le calcul. Entier des racines carrées de nombres négatifs n'existent pas puisque nous ne sommes pas dans le domaine des nombres imaginaires.
ces algorithmes proviennent de simples algorithmes itératifs de racine carrée, très connus, qui ont été utilisés dans les calculs manuels pendant des siècles. Il fonctionne en faisant la moyenne d'une surestimation et de sous-estimer à converger vers une meilleure estimation. Cela peut être répété jusqu'à ce que l'estimation soit aussi proche que désiré.
ils sont basés sur y1 = ((x/y0) + y0) / 2 convergeant vers le plus grand entier, yn, où yn * yn <= X.
cela vous donnera un valeur au sol pour une racine carrée BigInteger, y, de x où y * y <= x et (y + 1) * (y + 1) > x.
une adaptation peut vous donner une valeur de plafond pour la racine carrée BigInteger, y, de x où y * y >= x et (y - 1) * (y - 1) < x
les deux méthodes ont été testées et fonctionnent. Ils sont ici:
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
Je ne peux pas en vérifier l'exactitude, mais il existe plusieurs solutions maison sur Google. Le meilleur d'entre eux semblait être celui-ci: http://www.merriampark.com/bigsqrt.htm
essaye aussi le projet de maths Apache commons (une fois Apache récupéré de son bombardement après le billet du blog JCP).
comme Jigar indique, l'itération de Newton est à la fois très simple à comprendre et à mettre en œuvre. Je vais laisser les autres décider s'il est le plus efficace algorithme ou pas pour trouver la racine carrée d'un nombre.
avec récursion, il peut être fait en seulement deux lignes.
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);
}
où n est le nombre dont nous voulons trouver la racine carrée, et x0 est le numéro de l'appel précédent, qui sera toujours 1 lorsque lancer le premier appel d'une autre méthode. Donc, de préférence, vous le compléterez avec quelque chose comme ça aussi;
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);
}
j'avais besoin d'avoir la racine carrée pour les BigIntegers pour mettre en œuvre le tamis quadratique. J'ai utilisé certaines des solutions ici, mais la solution absolument la plus rapide et la meilleure jusqu'à présent est de la bibliothèque BigInteger de Google Guava.
Documentation peut être trouvé ici .
une approche alternative, qui est assez légère. Du point de vue de la vitesse, la réponse de Mantono, qui utilise la méthode de Newton, pourrait être préférable dans certains cas.
Voici mon approche...
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);
}
pour une première supposition j'utiliserais Math.sqrt(bi.doubleValue()) et vous pouvez utiliser les liens déjà suggérés pour rendre la réponse plus précise.
C'est la meilleure (et la plus courte) de travail solution que j'ai trouvé
http://faruk.akgul.org/blog/javas-missing-algorithm-biginteger-sqrt /
voici le 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);
}
je l'ai testé et il fonctionne correctement (et semble rapide)
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;
}
j'étais juste en train de travailler sur ce problème et j'ai réussi à écrire un logiciel de recherche de racine carrée récursive en Java. Vous pouvez changer le BDtol à tout ce que vous voulez, mais cela fonctionne assez rapidement et m'a donné l'exemple suivant en conséquence:
Original number 1467839114233645767430925372993335637692683931121739087571335401020890062659255388686508254381502201473025
SQRT -- >383123885216472214589586756787577295328224028242477055.000000000
puis pour confirmation 1467839114233645767430925372993335637692683931121739087571335401020890062659255388686508254381502201473025.0000000000000000000000 151940920"
mise à jour (23juillet2018) : cette technique ne s'applique pas aux valeurs plus élevées. Ont posté une technique différente basée sur la recherche binaire ci-dessous.
j'étais en train d'étudier la factorisation et j'ai fini par écrire ceci.
package com.example.so.math;
import java.math.BigInteger;
/**
*
* <p>/q/how-can-i-find-the-square-root-of-a-java-biginteger-73106/":"+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;
}
}
l'approche peut être visualisée comme ceci:
Espérons que cette aide!
étrange que personne ne l'a mentionné plus tôt, mais dans java 9 Vous avez sqrt dans BigInteger, donc vous pouvez juste l'utiliser comme ça:
BigInteger b = BigInteger.valueOf(64);
BigInteger eight = b.sqrt();
https://docs.oracle.com/javase/9/docs/api/java/math/BigInteger.html#sqrt--
je vais seulement jusqu'à la partie entière de la racine carrée mais vous pouvez modifier cet algo rugueux pour aller à autant plus de précision que vous voulez:
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;
}
le langage C# a une syntaxe similaire à Java. J'ai écrit cette solution récursive.
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);
}
appelez ce code comme ceci (en Java je suppose qu'il serait" système.hors.imprimer.)"
Console.WriteLine(fsqrt(BigInteger.Parse("783648276815623658365871365876257862874628734627835648726")));
Et la réponse est: 27993718524262253829858552106
avertissement: je comprends que cette méthode ne fonctionne pas pour les nombres inférieurs à 10; il s'agit d'une méthode de racine carrée BigInteger.
cela est facilement remédié. Changer la première méthode à la suivante pour donner à la partie récursive de l'espace pour respirer.
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);
}
Simplifiée Jim réponse et amélioration de la performance.
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;
}
}
vous pouvez également utiliser la recherche binaire pour trouver la racine carrée de x vous pouvez également le multiplier par exemple 10^10 et trouver un entier comme m par recherche binaire depuis m^2
System.out.println(m.divide(10^5)+"."+m.mod(10^5));Voici une solution qui n'utilise pas BigInteger.multiplier ou BigInteger.diviser:
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};
}
la réponse que j'ai posté ci-dessus ne fonctionne pas pour les grands nombres (mais il est intéressant de le faire!). Comme telle affichage d'une approche de recherche binaire pour déterminer racine carrée pour l'exactitude.
package com.example.so.squareroot;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
/**
* <p>/q/how-can-i-find-the-square-root-of-a-java-biginteger-73106/"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;
}
}
en ce qui Concerne Ravindra
Une seule ligne peut faire le travail je pense.
Math.pow(bigInt.doubleValue(), (1/n));