How can I find the Square Root of a Java BigInteger?

2023-01-29 16:05 问答作者：

Is there a library that will f开发者_如何学JAVAind the square root of a BigInteger? I want it computed offline - only once, and not inside any loop. So even computationally expensive solution is okay.

I don't want to find some algorithm and implement. A readily available solution will be perfect.

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

I know of no library solution for your question. You'll have to import an external library solution from somewhere. What I give you below is less complicated than getting an external library.

You can create your own external library solution in a class with two static methods as shown below and add that to your collection of external libraries. The methods don't need to be instance methods and so they are static and, conveniently, you don't have to instance the class to use them. The norm for integer square roots is a floor value (i.e. the largest integer less than or equal to the square root), so you may need only the one static method, the floor method, in the class below for the floor value and can choose to ignore the ceiling (i.e. the smallest integer greater than or equal to the square root) method version. Right now, they are in the default package, but you can add a package statement to put them in whatever package you find convenient.

The methods are dirt simple and the iterations converge to the closest integer answer very, very fast. They throw an IllegalArgumentException if you try to give them a negative argument. You can change the exception to another one, but you must ensure that a negatve argument throws some kind of exception or at least doesn't attempt the computation. Integer square roots of negative numbers don't exist since we are not in the realm of imaginary numbers.

These come from very well known simple iterative integer square root algorithms that have been used in hand computations for centuries. It works by averaging an overestimate and underestimate to converge to a better estimate. This may be repeated until the estimate is as close as is desired.

They are based on y1 = ((x/y0) + y0) / 2 converging to the largest integer, yn, where yn * yn <= x.

This will give you a floor value for a BigInteger square root, y, of x where y * y <= x and (y + 1) * (y + 1) > x.

An adaptation can give you a ceiling value for BigInteger square root, y, of x where y * y >= x and (y - 1) * (y - 1) < x

Both methods have been tested and work. They are here:

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

Strange that nobody has mentioned it earlier but in java 9 you have sqrt in BigInteger, so you can just use it like that:

BigInteger nine = BigInteger.valueOf(9);
BigInteger three = nine.sqrt();

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

EDIT-1

Adding that there is another flavour of this function that, in addition to the floored square root, also returns the remainder.

sqrtAndRemainder() BigInteger[]

Returns an array of two BigIntegers containing the integer square root s
of this and its remainder this - s*s, respectively.

I can't verify the accuracy of them but there are several home grown solutions when googling. The best of them seemed to be this one: http://www.merriampark.com/bigsqrt.htm

Also try the Apache commons Math project (once Apache recovers from its bombardment after the JCP blog post).

As Jigar states, Newton's iteration is both quite simple to understand and to implement. I'll leave it up to others decide whether it is the most efficient algorithm or not for finding the square root of a number.

With recursion it can be done in just about two lines.

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

Where n is the number we want to find the square root of, and x0 is the number from the previous call, which will always be 1 when initiate the first call from another method. So preferably, you will complement it with something like this as well;

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

For an initial guess I would use Math.sqrt(bi.doubleValue()) and you can use the links already suggested to make the answer more accurate.

I needed to have the square root for BigIntegers for implementing the quadratic sieve. I used some of the solutions here but the absolutely fastest and best solution so far is from Google Guava's BigInteger library.

Documentation can be found here.

An alternative approach, which is quite light. Speed-wise, Mantono's answer, that uses the Newton method, might be preferable for certain cases.

Here's my approach...

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

This is the best (and shortest) working solution I've found

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

Here is the 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);
  }

I've tested it and it's working correctly (and seems fast)

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

I was just working on this problem and successfully wrote a recursive square root finder in Java. You can change the BDtol to whatever you want, but this runs fairly quickly and gave me the follow example as a result:

Original number 146783911423364576743092537299333563769268393112173908757133540102089006265925538868650825438150202201473025

SQRT --> 383123885216472214589586756787577295328224028242477055.000000000

Then for confirmation 146783911423364576743092537299333563769268393112173908757133540102089006265925538868650825438150202201473025.000000000000000000

Simplified Jim answer and improved 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;
    }
}

Update (23July2018) : This technique does not apper to work for larger values. Have posted a different technique based on binary-search below.