3

Buenas, he intentado sacar la raíz de un BigInteger con el método pow de BigInteger, porque no encuentro el método que realice la operación de raíz cuadrada a las instancias de esta clase.

BigInteger sqr = n.pow(0.5);

Sin embargo el método pow de BigInteger solo recibe enteros. Si hay una forma o si el método para sacar la raíz cuadrada de un BigInteger si existe, les agradecería me lo aclararan, gracias.

1

1 respuesta 1

5
public static BigInteger raiz(BigInteger x) {
    BigInteger a= BigInteger.ZERO.setBit(x.bitLength()/2);
    BigInteger b= a;
    while(true) {
        BigInteger c = a.add(x.divide(a)).shiftRight(1);
        if (c.equals(a) || c.equals(b))
            return c;
        b= a;
        a= c;
    }
}

es algo muy parecido a un ataque por fuerza bruta. primero elegimos un punto de comienzo, en este caso usamos las propiedades del sistema binario de tal manera que el valor del bit de la mitad de la longitud total es en los casos que se tiene raíz cuadrada entera, por ejemplo:

2->4
4->16
8->64
16->256

luego solo iteramos, si x/a=a entonces a*a=x.

por ejemplo: 81

BigInteger a= BigInteger.ZERO.setBit(x.bitLength()/2);

en binario es 1010001, tiene 7 dígitos, la mitad seria 4, 1000 en decimal es 8.

iniciamos la a iterar:

x=81
a=8
b=8

c=(a+(x/a))/2
c=(8+(81/8))/2
c=(8+(10))/2
c=(18)/2
c=9

b=8
a=9

c=(a+(x/a))/2
c=(9+(81/9))/2
c=(9+(9))/2
c=(9)/2
c=9

c.equals(a)

return 9
4
  • 1
    Jorge , sería genial que brindarás una breve explicación del método. qué realiza y a que resultado llega. Gracias
    – Dev. Joel
    el 15 abr. 2017 a las 21:08
  • Estoy de acuerdo con Dev. Joel, tambien me gustaria saber como funciona, tengo nociones basicas acerca de bits. Gracias por la respuesta.
    – V0LT3RR4
    el 15 abr. 2017 a las 21:09
  • 2
    La solución esta basado en Newtons method. sería bueno de elaborar un poco. Básicamente se usa convergencia de acercarse rápidamente al resultado, una "adivinación cualificada". el 15 abr. 2017 a las 21:15
  • 1
    @VictorPaternina he extendido la respuesta, pero para que requieres la raíz de un Biginteger? el 16 abr. 2017 a las 18:05

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.