Как найти квадратный корень Java BigInteger?

Question

Есть ли библиотека, которая найдет квадратный корень из BigInteger?Я хочу, чтобы он вычислялся в автономном режиме - только один раз, а не внутри какого-либо цикла.Так что даже вычислительно дорогое решение хорошо.

Я не хочу найти какой-то алгоритм и реализовать.Легкодоступное решение будет идеальным.

Answer 1

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

Я просто работал над этой проблемой и успешно написал рекурсивный искатель квадратного корня на Java.Вы можете изменить BDtol на любое другое, но это работает довольно быстро, и в результате я получил следующий пример:

Исходный номер 14678391142336457674309253729933356376926839311217390875713354010208900623050502552552552552553083083082500_1000_1000_1000_1000_2500525525825525525525525525_0151009 * SQRT -> 383123885216472214589586756787577295328224028242477055.000000000

1013 * Тогда для подтверждения 146783911423364576743092537299333563769268393112173908757133540102089006265925538868650825438150202201473025,000000000000000000

Answer 2

Это лучшее (и самое короткое) рабочее решение, которое я нашел

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

Вот код:

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

Я проверил его, и он работает правильно (и, кажется, быстро)

Answer 3

Ответ, который я разместил выше, не работает для больших чисел (но это интересно!). Как таковая публикация бинарно-поискового подхода для определения правильности квадратного корня.

package com.example.so.squareroot;

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

/**
 * <p>/2434917/kak-naiti-kvadratnyi-koren-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;

    }


}

С уважением Ravindra

Answer 4

Вот решение, которое не использует BigInteger.multiply или 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 5

Вы также можете использовать бинарный поиск, чтобы найти квадратный корень из x, также вы можете умножить его, например, на 10 ^ 10 и найти целое число, подобное m, с помощью двоичного поиска, так как m ^ 2

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

Answer 6

Язык C # имеет синтаксис, аналогичный Java. Я написал это рекурсивное решение.

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

Назовите этот код так (в Java, я думаю, это будет "System.out.print").

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

И ответ таков: +27993718524262253829858552106

Отказ от ответственности: я понимаю, что этот метод не работает для чисел меньше 10; это метод квадратного корня BigInteger.

Это легко исправить. Измените первый метод на следующий, чтобы дать рекурсивной части немного пространства для дыхания.

    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 7

Я дошел до целочисленной части квадратного корня, но вы можете изменить этот грубый алгоритм, чтобы получить как можно большую точность:

  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 8

Мне кажется, что одну строку можно выполнить.

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