Home / Questions / 63079
Accepted
V0LT3RR4
Asked: 2020-04-16 12:30:06 +0800 CST 2020-04-16 12:30:06 +0800 CST

Square root of a BigInteger or BigDecimal in Java

  • 772

Hello, I have tried to take the root of a BigIntegerwith the method pow, BigIntegerbecause I cannot find the method that performs the square root operation on the instances of this class. 

BigInteger sqr = n.pow(0.5);

However the method powonly BigIntegerreceives integers. If there is a way or if the method to take the square root of a BigIntegerdoes exist, I would appreciate it if you could clarify it for me, thanks.

java

1 Answers

  1. Best Answer
    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;
    }
}

    It is something very similar to a brute force attack. first we choose a starting point, in this case we use the properties of the binary system in such a way that the value of the bit of half of the total length is in the cases that have integer square root, for example:

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

    then we just iterate, if x/a=a then a*a=x.

    for example: 81

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

    in binary it is 1010001, it has 7 digits, half would be 4, 1000 in decimal is 8.

    we start the to iterate:

    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
    • 5