Raíz cuadrada de BigDecimal en Java
square-root (12)
¿Podemos calcular la raíz cuadrada de un BigDecimal en Java utilizando solo la API de Java y no un algoritmo personalizado de 100 líneas?
¡A partir de Java 9 puedes! Ver BigDecimal.sqrt() .
Al usar los Trucos de Karp, esto se puede implementar sin un bucle en solo dos líneas, dando una precisión de 32 dígitos:
public static BigDecimal sqrt(BigDecimal value) {
BigDecimal x = new BigDecimal(Math.sqrt(value.doubleValue()));
return x.add(new BigDecimal(value.subtract(x.multiply(x)).doubleValue() / (x.doubleValue() * 2.0)));
}
Aquí hay una solución muy precisa y rápida, está basada en mi solución BigIntSqRoot y la siguiente observación: La raíz cuadrada de A ^ 2B - Es A multiplicar la raíz de B. Usando este método, puedo calcular fácilmente los primeros 1000 dígitos de la raíz cuadrada de 2.
1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727350138462309122970249248360558507372126441214970999358314132226659275055927557999505011527820605714701095599716059702745345968620147285174186408891986095523292304843087143214508397626036279952514079896872533965463318088296406206152583523950547457502877599617298355752203375318570113543746034084988471603868999706990048150305440277903164542478230684929369186215805784631115966687130130156185689872372352885092648612494977154218334204285686060146824720771435854874155657069677653720226485447015858801620758474922657226002085584466521458398893944370926591800311388246468157082630100594858704003186480342194897278290641045072636881313739855256117322040245091227700226941127573627280495738108967504018369868368450725799364729060762996941380475654823728997180326802474420629269124859052181004459842150591120249441341728531478105803603371077309182869314710171111683916581726889419758716582152128229518488472
Así que aquí está el código fuente
public class BigIntSqRoot {
private static final int PRECISION = 10000;
private static BigInteger multiplier = BigInteger.valueOf(10).pow(PRECISION * 2);
private static BigDecimal root = BigDecimal.valueOf(10).pow(PRECISION);
private static BigInteger two = BigInteger.valueOf(2L);
public static BigDecimal bigDecimalSqRootFloor(BigInteger x)
throws IllegalArgumentException {
BigInteger result = bigIntSqRootFloor(x.multiply(multiplier));
//noinspection BigDecimalMethodWithoutRoundingCalled
return new BigDecimal(result).divide(root);
}
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.");
}
return x.equals(BigInteger.ZERO) || x.equals(BigInteger.ONE);
}
}
Como se dijo antes: si no le importa la precisión de su respuesta, pero solo desea generar dígitos aleatorios después de la décima quinta aún válida, entonces, ¿por qué usa BigDecimal en absoluto?
Aquí hay un código para el método que debería hacer el truco con BigDecimals en coma flotante:
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
public BigDecimal bigSqrt(BigDecimal d, MathContext mc) {
// 1. Make sure argument is non-negative and treat Argument 0
int sign = d.signum();
if(sign == -1)
throw new ArithmeticException("Invalid (negative) argument of sqrt: "+d);
else if(sign == 0)
return BigDecimal.ZERO;
// 2. Scaling:
// factorize d = scaledD * scaleFactorD
// = scaledD * (sqrtApproxD * sqrtApproxD)
// such that scalefactorD is easy to take the square root
// you use scale and bitlength for this, and if odd add or subtract a one
BigInteger bigI=d.unscaledValue();
int bigS=d.scale();
int bigL = bigI.bitLength();
BigInteger scaleFactorI;
BigInteger sqrtApproxI;
if ((bigL%2==0)){
scaleFactorI=BigInteger.ONE.shiftLeft(bigL);
sqrtApproxI=BigInteger.ONE.shiftLeft(bigL/2);
}else{
scaleFactorI=BigInteger.ONE.shiftLeft(bigL-1);
sqrtApproxI=BigInteger.ONE.shiftLeft((bigL-1)/2 );
}
BigDecimal scaleFactorD;
BigDecimal sqrtApproxD;
if ((bigS%2==0)){
scaleFactorD=new BigDecimal(scaleFactorI,bigS);
sqrtApproxD=new BigDecimal(sqrtApproxI,bigS/2);
}else{
scaleFactorD=new BigDecimal(scaleFactorI,bigS+1);
sqrtApproxD=new BigDecimal(sqrtApproxI,(bigS+1)/2);
}
BigDecimal scaledD=d.divide(scaleFactorD);
// 3. This is the core algorithm:
// Newton-Ralpson for scaledD : In case of f(x)=sqrt(x),
// Heron''s Method or Babylonian Method are other names for the same thing.
// Since this is scaled we can be sure that scaledD.doubleValue() works
// for the start value of the iteration without overflow or underflow
System.out.println("ScaledD="+scaledD);
double dbl = scaledD.doubleValue();
double sqrtDbl = Math.sqrt(dbl);
BigDecimal a = new BigDecimal(sqrtDbl, mc);
BigDecimal HALF=BigDecimal.ONE.divide(BigDecimal.ONE.add(BigDecimal.ONE));
BigDecimal h = new BigDecimal("0", mc);
// when to stop iterating? You start with ~15 digits of precision, and Newton-Ralphson is quadratic
// in approximation speed, so in roundabout doubles the number of valid digits with each step.
// This fmay be safer than testing a BigDecifmal against zero.
int prec = mc.getPrecision();
int start = 15;
do {
h = scaledD.divide(a, mc);
a = a.add(h).multiply(HALF);
start *= 2;
} while (start <= prec);
// 3. Return rescaled answer. sqrt(d)= sqrt(scaledD)*sqrtApproxD :
return (a.multiply(sqrtApproxD));
}
Como prueba, intente cuadrar repetidamente un número un par de veces que tomando la raíz cuadrada repetida, y vea qué tan cerca está de donde comenzó.
Lo he usado y funciona bastante bien. Aquí hay un ejemplo de cómo funciona el algoritmo en un nivel alto.
Editar: Tenía curiosidad por ver qué tan preciso era esto como se define a continuación. Aquí está el sqrt (2) de una fuente oficial :
(first 200 digits) 1.41421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206057147
y aquí está usando el enfoque que bosquejo a continuación con SQRT_DIG igual a 150:
(first 200 digits) 1.41421356237309504880168872420969807856967187537694807317667973799073247846210703885038753432764157273501384623091229702492483605585073721264412149709993583141322266592750559275579995050115278206086685
La primera desviación ocurre después de 195 dígitos de precisión . Utilice bajo su propio riesgo si necesita un nivel de precisión tan alto como este.
Al cambiar SQRT_DIG a 1000 se obtuvieron 1570 dígitos de precisión .
private static final BigDecimal SQRT_DIG = new BigDecimal(150);
private static final BigDecimal SQRT_PRE = new BigDecimal(10).pow(SQRT_DIG.intValue());
/**
* Private utility method used to compute the square root of a BigDecimal.
*
* @author Luciano Culacciatti
* @url http://www.codeproject.com/Tips/257031/Implementing-SqrtRoot-in-BigDecimal
*/
private static BigDecimal sqrtNewtonRaphson (BigDecimal c, BigDecimal xn, BigDecimal precision){
BigDecimal fx = xn.pow(2).add(c.negate());
BigDecimal fpx = xn.multiply(new BigDecimal(2));
BigDecimal xn1 = fx.divide(fpx,2*SQRT_DIG.intValue(),RoundingMode.HALF_DOWN);
xn1 = xn.add(xn1.negate());
BigDecimal currentSquare = xn1.pow(2);
BigDecimal currentPrecision = currentSquare.subtract(c);
currentPrecision = currentPrecision.abs();
if (currentPrecision.compareTo(precision) <= -1){
return xn1;
}
return sqrtNewtonRaphson(c, xn1, precision);
}
/**
* Uses Newton Raphson to compute the square root of a BigDecimal.
*
* @author Luciano Culacciatti
* @url http://www.codeproject.com/Tips/257031/Implementing-SqrtRoot-in-BigDecimal
*/
public static BigDecimal bigSqrt(BigDecimal c){
return sqrtNewtonRaphson(c,new BigDecimal(1),new BigDecimal(1).divide(SQRT_PRE));
}
asegúrate de ver la respuesta de Barwnikk. es más conciso y aparentemente ofrece una precisión buena o mejor.
No hay nada en la API de Java, por lo que si el doble no es lo suficientemente preciso (si no, ¿por qué usar BigDecimal en absoluto?) Entonces necesitas algo como el siguiente código).
import java.math.BigDecimal;
public class BigDSqrt {
public static BigDecimal sqrt(BigDecimal n, int s) {
BigDecimal TWO = BigDecimal.valueOf(2);
// Obtain the first approximation
BigDecimal x = n
.divide(BigDecimal.valueOf(3), s, BigDecimal.ROUND_DOWN);
BigDecimal lastX = BigDecimal.valueOf(0);
// Proceed through 50 iterations
for (int i = 0; i < 50; i++) {
x = n.add(x.multiply(x)).divide(x.multiply(TWO), s,
BigDecimal.ROUND_DOWN);
if (x.compareTo(lastX) == 0)
break;
lastX = x;
}
return x;
}
}
Si desea calcular las raíces cuadradas para números con más dígitos que caben en un doble (un BigDecimal con una escala grande):
Wikipedia tiene un artículo para computar raíces cuadradas: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method
Esta es mi implementación de esto:
public static BigDecimal sqrt(BigDecimal in, int scale){
BigDecimal sqrt = new BigDecimal(1);
sqrt.setScale(scale + 3, RoundingMode.FLOOR);
BigDecimal store = new BigDecimal(in.toString());
boolean first = true;
do{
if (!first){
store = new BigDecimal(sqrt.toString());
}
else first = false;
store.setScale(scale + 3, RoundingMode.FLOOR);
sqrt = in.divide(store, scale + 3, RoundingMode.FLOOR).add(store).divide(
BigDecimal.valueOf(2), scale + 3, RoundingMode.FLOOR);
}while (!store.equals(sqrt));
return sqrt.setScale(scale, RoundingMode.FLOOR);
}
setScale(scale + 3, RoundingMode.Floor) porque al calcular proporciona más precisión. RoundingMode.Floor trunca el número, RoundingMode.HALF_UP realiza el redondeo normal.
Si necesita encontrar solo raíces cuadradas enteras , estos son dos métodos que pueden usarse.
Método de Newton : muy rápido incluso para 1000 dígitos BigInteger:
public static BigInteger sqrtN(BigInteger in) {
final BigInteger TWO = BigInteger.valueOf(2);
int c;
// Significantly speed-up algorithm by proper select of initial approximation
// As square root has 2 times less digits as original value
// we can start with 2^(length of N1 / 2)
BigInteger n0 = TWO.pow(in.bitLength() / 2);
// Value of approximate value on previous step
BigInteger np = in;
do {
// next approximation step: n0 = (n0 + in/n0) / 2
n0 = n0.add(in.divide(n0)).divide(TWO);
// compare current approximation with previous step
c = np.compareTo(n0);
// save value as previous approximation
np = n0;
// finish when previous step is equal to current
} while (c != 0);
return n0;
}
El método de bisección - es hasta 50 veces más lento que el de Newton - se usa solo con fines educativos:
public static BigInteger sqrtD(final BigInteger in) {
final BigInteger TWO = BigInteger.valueOf(2);
BigInteger n0, n1, m, m2, l;
int c;
// Init segment
n0 = BigInteger.ZERO;
n1 = in;
do {
// length of segment
l = n1.subtract(n0);
// middle of segment
m = l.divide(TWO).add(n0);
// compare m^2 with in
c = m.pow(2).compareTo(in);
if (c == 0) {
// exact value is found
break;
} else if (c > 0) {
// m^2 is bigger than in - choose left half of segment
n1 = m;
} else {
// m^2 is smaller than in - choose right half of segment
n0 = m;
}
// finish if length of segment is 1, i.e. approximate value is found
} while (l.compareTo(BigInteger.ONE) > 0);
return m;
}
Supongamos que no quiere tratar solo con el caso trivial de grandes decimales pequeños y desea administrar la precisión, entonces la respuesta es no: esto no se puede hacer en unos pocos LOC sin bibliotecas externas, pero esta lista de preguntas relacionada alguna Buenos.
BigDecimal.valueOf(Math.sqrt(myBigDecimal.doubleValue()));
public static BigDecimal sqrt( final BigDecimal value )
{
BigDecimal guess = value.multiply( DECIMAL_HALF );
BigDecimal previousGuess;
do
{
previousGuess = guess;
guess = sqrtGuess( guess, value );
} while ( guess.subtract( previousGuess ).abs().compareTo( EPSILON ) == 1 );
return guess;
}
private static BigDecimal sqrtGuess( final BigDecimal guess,
final BigDecimal value )
{
return guess.subtract( guess.multiply( guess ).subtract( value ).divide( DECIMAL_TWO.multiply( guess ), SCALE, RoundingMode.HALF_UP ) );
}
private static BigDecimal epsilon()
{
final StringBuilder builder = new StringBuilder( "0." );
for ( int i = 0; i < SCALE - 1; ++i )
{
builder.append( "0" );
}
builder.append( "1" );
return new BigDecimal( builder.toString() );
}
private static final int SCALE = 1024;
private static final BigDecimal EPSILON = epsilon();
public static final BigDecimal DECIMAL_HALF = new BigDecimal( "0.5" );
public static final BigDecimal DECIMAL_TWO = new BigDecimal( "2" );
public static BigDecimal sqrt(BigDecimal A, final int SCALE) {
BigDecimal x0 = new BigDecimal("0");
BigDecimal x1 = new BigDecimal(Math.sqrt(A.doubleValue()));
while (!x0.equals(x1)) {
x0 = x1;
x1 = A.divide(x0, SCALE, ROUND_HALF_UP);
x1 = x1.add(x0);
x1 = x1.divide(TWO, SCALE, ROUND_HALF_UP);
}
return x1;
}
Este trabajo perfecto! ¡Muy rápido para más de 65536 dígitos!