¿Cómo puedo encontrar la raíz cuadrada de un BigInteger de Java?

square-root

Question

¿Hay una biblioteca que encuentre la raíz cuadrada de un BigInteger? Quiero que se calcule sin conexión: solo una vez, y no dentro de ningún bucle. Así que incluso una solución computacionalmente costosa está bien.

No quiero encontrar algún algoritmo e implementarlo. Una solución fácilmente disponible será perfecta.

Answer 1

Actualización (23 de julio de 2018): esta técnica no funciona para valores más grandes. Han publicado una técnica diferente basada en la búsqueda binaria a continuación.

Estaba estudiando la factorización y terminé escribiendo esto.

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


}

El enfoque se puede visualizar así:

¡Espero que esto ayude!

Answer 2

Aquí hay una solución que no usa BigInteger.multiply o 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};
    }

Answer 3

Como afirma Jigar , la iteración de Newton es bastante simple de entender y de implementar. Dejaré que otros decidan si es el algoritmo más eficiente o no para encontrar la raíz cuadrada de un número.

Con la recursión se puede hacer en casi dos líneas.

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

Donde n es el número del que queremos encontrar la raíz cuadrada de, y x0 es el número de la llamada anterior, que siempre será 1 cuando inicie la primera llamada desde otro método. Así que, preferiblemente, lo complementará con algo como esto también;

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 4

Creo que una sola línea puede hacer el trabajo.

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

Answer 5

El lenguaje C # tiene una sintaxis similar a la de Java. Escribí esta solución recursiva.

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

Llame a este código como este (en Java supongo que sería "System.out.print").

Console.WriteLine(fsqrt(BigInteger.Parse("783648276815623658365871365876257862874628734627835648726")));

Y la respuesta es: 27993718524262253829858552106

Descargo de responsabilidad: entiendo que este método no funciona para números menores de 10; Este es un método de raíz cuadrada de BigInteger.

Esto es fácilmente remediado. Cambie el primer método al siguiente para darle a la parte recursiva un poco de espacio para respirar.

    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 6

Es extraño que nadie lo haya mencionado antes, pero en java 9 tienes sqrt en BigInteger, así que puedes usarlo así:

BigInteger b = BigInteger.valueOf(64);
BigInteger eight = b.sqrt();

https://docs.oracle.com/javase/9/docs/api/java/math/BigInteger.html#sqrt--

Answer 7

Esta es la mejor solución de trabajo (y la más corta) que he encontrado

http://faruk.akgul.org/blog/javas-missing-algorithm-biginteger-sqrt/

Aquí está el código:

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

Lo he probado y está funcionando correctamente (y parece rápido)

Answer 8

La respuesta que publiqué arriba no funciona para grandes números (¡pero curiosamente!). Como tal, la publicación de un enfoque de búsqueda binaria para determinar la raíz cuadrada para la corrección.

package com.example.so.squareroot;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

/**
 * <p>https://.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;

    }


}

Saludos Ravindra

Answer 9

Necesitaba tener la raíz cuadrada de BigIntegers para implementar el tamiz cuadrático. Utilicé algunas de las soluciones aquí, pero la solución absolutamente más rápida y mejor hasta ahora es la de la biblioteca BigInteger de Google Guava.

La documentación se puede encontrar here .

Answer 10

No conozco ninguna solución de biblioteca para su pregunta. Tendrás que importar una solución de biblioteca externa desde algún lugar. Lo que le doy a continuación es menos complicado que obtener una biblioteca externa.

Puede crear su propia solución de biblioteca externa en una clase con dos métodos estáticos como se muestra a continuación y agregarlo a su colección de bibliotecas externas. No es necesario que los métodos sean métodos de instancia, por lo que son estáticos y, de manera conveniente, no es necesario que instale la clase para usarlos. La norma para las raíces cuadradas de enteros es un valor de piso (es decir, el entero más grande menor o igual que la raíz cuadrada), por lo que es posible que solo necesite un método estático, el método de piso, en la siguiente clase para el valor de piso y puede elegir para ignorar la versión del método del techo (es decir, el entero más pequeño mayor o igual que la raíz cuadrada). En este momento, están en el paquete predeterminado, pero puede agregar una declaración de paquete para colocarlos en el paquete que le resulte más conveniente.

Los métodos son muy simples y las iteraciones convergen a la respuesta del entero más cercano muy, muy rápido. Lanzan una IllegalArgumentException si intentas darles un argumento negativo. Puede cambiar la excepción a otra, pero debe asegurarse de que un argumento negativo arroje algún tipo de excepción o al menos no intente realizar el cálculo. Las raíces cuadradas de números negativos no existen ya que no estamos en el reino de los números imaginarios.

Estos provienen de algoritmos de raíz cuadrada de enteros iterativos simples muy conocidos que se han utilizado en los cálculos manuales durante siglos. Funciona al promediar una sobreestimación y una subestimación para converger a una mejor estimación. Esto se puede repetir hasta que la estimación esté tan cerca como se desee.

Se basan en y1 = ((x / y0) + y0) / 2 que convergen al entero más grande, yn, donde yn * yn <= x.

Esto le dará un valor mínimo para una raíz cuadrada de BigInteger, y, de x donde y * y <= x y (y + 1) * (y + 1)> x.

Una adaptación puede darle un valor de techo para la raíz cuadrada de BigInteger, y, de x donde y * y> = x y (y - 1) * (y - 1) <x

Ambos métodos han sido probados y funcionan. Ellos están aquí:

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 11

No puedo verificar la precisión de ellos, pero existen varias soluciones locales cuando se busca en Google. El mejor de ellos parecía ser este: http://www.merriampark.com/bigsqrt.htm

También intente el proyecto Apache commons Math (una vez que Apache se recupere de su bombardeo después de la publicación del blog JCP).

Answer 12

Para una suposición inicial, usaría Math.sqrt(bi.doubleValue()) y puede usar los enlaces que ya se han sugerido para que la respuesta sea más precisa.

Answer 13

Solo por diversión:

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 14

Solo voy hasta la parte entera de la raíz cuadrada, pero puede modificar este algoritmo aproximado para que tenga la mayor precisión que desee:

  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 15

Un enfoque alternativo, que es bastante ligero. En cuanto a la velocidad, la respuesta de Mantono, que utiliza el método de Newton, podría ser preferible para ciertos casos.

Aquí está mi enfoque ...

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 16

también puede usar la búsqueda binaria para encontrar la raíz cuadrada de x, también puede multiplicarla para, por ejemplo, 10 ^ 10 y encontrar un número entero como m por búsqueda binaria desde m ^ 2

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

Answer 17

Jim simplifica la respuesta y mejora el rendimiento.

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 18

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

Estaba trabajando en este problema y escribí con éxito un buscador recursivo de raíz cuadrada en Java. Puedes cambiar el BDtol a lo que quieras, pero esto se ejecuta con bastante rapidez y me dio el siguiente ejemplo como resultado:

Número original 146783911423364576743092537299333563769268393112173908757133540102089006265925538868650825438150202201473025

SQRT -> 383123885216472214589586756787577295328224028242477055.000000000

Luego para la confirmación 146783911423364576743092537299333563769268393112173908757133540102089006265925538868650825438150202201473025.000000000000000000