当前位置： 文江博客话题详情

如何求 Java BigInteger 的平方根？

发布于 2024-10-07 10:24:32 字数 118 浏览 4 评论 0原文

是否有一个库可以计算 BigInteger 的平方根？我希望它离线计算 - 仅一次，并且不在任何循环内。因此，即使计算成本昂贵的解决方案也是可以的。

我不想找到一些算法并实现。一个现成的解决方案将是完美的。

原文

Is there a library that will find 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.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（20）

北方的韩爷 2024-10-14 10:24:32

只是为了好玩：

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

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;
    }
}
回复 原文
不…忘初心 2024-10-14 10:24:32

我知道没有图书馆可以解决您的问题。您必须从某个地方导入外部库解决方案。我在下面提供的内容比获取外部库要简单。

您可以使用两个静态方法在类中创建您自己的外部库解决方案，如下所示，并将其添加到您的外部库集合中。这些方法不需要是实例方法，因此它们是静态的，并且方便的是，您不必实例化类即可使用它们。整数平方根的范数是下限值（即小于或等于平方根的最大整数），因此您可能只需要下面类中的一个静态方法，即floor方法来获取下限值，并且可以选择忽略上限（即大于或等于平方根的最小整数）方法版本。现在，它们位于默认包中，但您可以添加包语句将它们放入您认为方便的任何包中。

这些方法非常简单，并且迭代非常非常快地收敛到最接近的整数答案。如果你试图给他们一个否定的论点，他们会抛出一个 IllegalArgumentException 异常。您可以将异常更改为另一种异常，但必须确保负参数引发某种异常或至少不尝试计算。负数的整数平方根不存在，因为我们不在虚数领域。

这些来自众所周知的简单迭代整数平方根算法，这些算法已经在手工计算中使用了几个世纪。它的工作原理是对高估和低估进行平均，以收敛到更好的估计。可以重复这一过程，直到估计值与期望的值接近为止。

它们基于 y1 = ((x/y0) + y0) / 2 收敛到最大整数 yn，其中 yn * yn <= x。

这将为您提供 x 的 BigInteger 平方根 y 的下限值，其中
y*y＜＝x且(y+1)*(y+1)＞ x。

调整可以为您提供 x 的 BigInteger 平方根 y 的上限值，其中
y*y＞=x且(y-1)*(y-1)＜ x

两种方法都经过测试并且有效。他们在这里：

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

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
回复 原文
_蜘蛛 2024-10-14 10:24:32

奇怪的是，之前没有人提到过，但在 java 9 中，BigInteger 中有 sqrt，因此您可以像这样使用它：

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

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

EDIT-1

添加此函数还有另一种风格，除了取整平方根之外，还返回余数。

sqrtAndRemainder() BigInteger[]

返回包含整数平方根 s 的两个 BigInteger 数组
其中 this 及其余数分别为 this - s*s。

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.
回复 原文
白况 2024-10-14 10:24:32

我无法验证它们的准确性，但在谷歌搜索时有几个自制的解决方案。其中最好的似乎是这个： http ://www.merriampark.com/bigsqrt.htm

还可以尝试 Apache commons Math 项目（一旦 Apache 从 JCP 博客文章后的轰炸中恢复过来）。

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).

回复 原文
有深☉意 2024-10-14 10:24:32

正如Jigar所述，牛顿迭代 非常容易理解和实现。我将让其他人决定它是否是求数字平方根的最有效算法。

通过递归，只需大约两行即可完成。

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

其中n是我们要求平方根的数字，x0是上一次调用的数字，当从另一个发起第一次调用时，它总是1方法。所以最好你也用这样的东西来补充它；

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

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);
}
回复 原文
疯了 2024-10-14 10:24:32

对于初步猜测，我会使用 Math.sqrt(bi.doubleValue()) ，您可以使用已经建议的链接来使答案更加准确。

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.

回复 原文
爱要勇敢去追 2024-10-14 10:24:32

我需要 BigIntegers 的平方根来实现二次筛选。我在这里使用了一些解决方案，但迄今为止绝对最快和最好的解决方案来自 Google Guava 的 BigInteger 库。

可以找到文档 这里。

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.

回复 原文
篱下浅笙歌 2024-10-14 10:24:32

另一种方法，相当轻便。就速度而言，曼托诺的答案使用牛顿法，对于某些情况可能更可取。

这是我的方法...

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

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);
}
回复 原文
半山落雨半山空 2024-10-14 10:24:32

这是我发现的最好（也是最短）的工作解决方案

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

我已经测试过它并且它工作正常（并且看起来很快）

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)

回复 原文
丿*梦醉红颜 2024-10-14 10:24:32
    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更改为您想要的任何内容，但是运行速度相当快，并给出了以下示例：

原始号码1467839114233645767430925372993335637692683931121739087571335401020890062659255388686 50825438150202201473025

SQRT --> 383123885216472214589586756787577295328224028242477055.000000000

然后进行确认
146783911423364576743092537299333563769268393112173908757133540102089006265925538868650825438150202201473025.0000000000 00000000

    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

回复 原文
魂ガ小子 2024-10-14 10:24:32

简化了Jim 答案并提高了性能。

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

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;
    }
}
回复 原文
帅冕 2024-10-14 10:24:32

更新（2018 年 7 月 23 日）：此技术不适用于较大的值。下面发布了基于二进制搜索的不同技术。

我正在研究因式分解并最终写了这篇文章。

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


}

该方法可以如下所示：

整数模数的幂 - N

希望这有帮助！

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

I was looking into factorization and ended up writing this.

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


}

The approach can be visualized like this :

Powers of Integers Moduluo - N

Hope this helps!

回复 原文
滥情稳全场 2024-10-14 10:24:32

如果需要性能，
那么对于长度在 64 位到 10240 位之间的数字，使用 Norton Plus 的速度比 Java 内置的 BigInteger Sqrt 快 15 倍到 45 倍。

// A fast square root by Ryan Scott White. (MIT License)
public static BigInteger NewtonPlusSqrt(BigInteger x) {
    if (x.compareTo(BigInteger.valueOf(144838757784765629L)) < 0) {
        long xAsLong = x.longValue();
        long vInt = (long)Math.sqrt(xAsLong);
        if (vInt * vInt > xAsLong)
            vInt--;
        return BigInteger.valueOf(vInt);  }

    double xAsDub = x.doubleValue();
    BigInteger val;
    if (xAsDub < 2.1267e37) // 2.12e37 largest here since sqrt(long.max*long.max) > long.max
    {
        long vInt = (long)Math.sqrt(xAsDub);
        val = BigInteger.valueOf((vInt + x.divide(BigInteger.valueOf(vInt)).longValue()) >> 1);
    }
    else if (xAsDub < 4.3322e127) {
        // Convert a double to a BigInteger
        long bits = Double.doubleToLongBits(Math.sqrt(xAsDub));
        int exp = ((int) (bits >> 52) & 0x7ff) - 1075;
        val = BigInteger.valueOf((bits & ((1L << 52)) - 1) | (1L << 52)).shiftLeft(exp);

        val = x.divide(val).add(val).shiftRight(1);
        if (xAsDub > 2e63) {
            val = x.divide(val).add(val).shiftRight(1);  }
    }
    else // handle large numbers over 4.3322e127
    {
        int xLen = x.bitLength();
        int wantedPrecision = ((xLen + 1) / 2);
        int xLenMod = xLen + (xLen & 1) + 1;

        //////// Do the first Sqrt on Hardware ////////
        long tempX = x.shiftRight(xLenMod - 63).longValue();
        double tempSqrt1 = Math.sqrt(tempX);
        long valLong = Double.doubleToLongBits(tempSqrt1) & 0x1fffffffffffffL;

        if (valLong == 0)
            valLong = 1L << 53;

        //////// Classic Newton Iterations ////////
        val = BigInteger.valueOf(valLong).shiftLeft(53 - 1)
                .add((x.shiftRight(xLenMod - (3 * 53))).divide(BigInteger.valueOf(valLong)));

        int size = 106;
        for (; size < 256; size <<= 1) {
            val = val.shiftLeft(size - 1).add(x.shiftRight(xLenMod - (3 * size)).divide(val)); }

        if (xAsDub > 4e254) // 4e254 = 1<<845.77 
        {
            int numOfNewtonSteps = 31 - Integer.numberOfLeadingZeros(wantedPrecision / size) + 1;

            ////// Apply Starting Size ////////
            int wantedSize = (wantedPrecision >> numOfNewtonSteps) + 2;
            int needToShiftBy = size - wantedSize;
            val = val.shiftRight(needToShiftBy);

            size = wantedSize;
            do {
                //////// Newton Plus Iteration ////////
                int shiftX = xLenMod - (3 * size);
                BigInteger valSqrd = val.multiply(val).shiftLeft(size - 1);
                BigInteger valSU = x.shiftRight(shiftX).subtract(valSqrd);
                val = val.shiftLeft(size).add(valSU.divide(val));
                size *= 2;
            } while (size < wantedPrecision);
        }
        val = val.shiftRight(size - wantedPrecision);
    }

    // Detect a round ups. This function can be further optimized - see article.
    // For a ~7% speed bump the following line can be removed but round-ups will occur.
    if (val.multiply(val).compareTo(x) > 0)
        val = val.subtract(BigInteger.ONE);

    // // Enabling the below will guarantee an error is stopped for larger numbers.
    // // Note: As of this writing, there are no known errors.
    // BigInteger tmp = val.multiply(val);
    // if (tmp.compareTo(x) > 0)  {
    //     System.out.println("val^2(" + val.multiply(val).toString() + ") >=  x(" + x.toString() + ")"); 
    //     System.console().readLine();
    //     //throw new Exception("Sqrt function had internal error - value too high");   
    // }
    // if (tmp.add(val.shiftLeft(1)).add(BigInteger.ONE).compareTo(x) <= 0) {
    //     System.out.println("(val+1)^2(" + val.add(BigInteger.ONE).multiply(val.add(BigInteger.ONE)).toString() + ") >=  x(" + x.toString() + ")"); 
    //     System.console().readLine();
    //     //throw new Exception("Sqrt function had internal error - value too low");    
    // }

    return val;
}

这是与内置 BigInteger.Sqrt() 的性能比较
输入图片此处描述

更多详细信息

If performance is needed,
then using the Norton Plus is 15X-45X faster than Java's built-in BigInteger Sqrt for numbers between 64 bits and 10240 bits in length.

// A fast square root by Ryan Scott White. (MIT License)
public static BigInteger NewtonPlusSqrt(BigInteger x) {
    if (x.compareTo(BigInteger.valueOf(144838757784765629L)) < 0) {
        long xAsLong = x.longValue();
        long vInt = (long)Math.sqrt(xAsLong);
        if (vInt * vInt > xAsLong)
            vInt--;
        return BigInteger.valueOf(vInt);  }

    double xAsDub = x.doubleValue();
    BigInteger val;
    if (xAsDub < 2.1267e37) // 2.12e37 largest here since sqrt(long.max*long.max) > long.max
    {
        long vInt = (long)Math.sqrt(xAsDub);
        val = BigInteger.valueOf((vInt + x.divide(BigInteger.valueOf(vInt)).longValue()) >> 1);
    }
    else if (xAsDub < 4.3322e127) {
        // Convert a double to a BigInteger
        long bits = Double.doubleToLongBits(Math.sqrt(xAsDub));
        int exp = ((int) (bits >> 52) & 0x7ff) - 1075;
        val = BigInteger.valueOf((bits & ((1L << 52)) - 1) | (1L << 52)).shiftLeft(exp);

        val = x.divide(val).add(val).shiftRight(1);
        if (xAsDub > 2e63) {
            val = x.divide(val).add(val).shiftRight(1);  }
    }
    else // handle large numbers over 4.3322e127
    {
        int xLen = x.bitLength();
        int wantedPrecision = ((xLen + 1) / 2);
        int xLenMod = xLen + (xLen & 1) + 1;

        //////// Do the first Sqrt on Hardware ////////
        long tempX = x.shiftRight(xLenMod - 63).longValue();
        double tempSqrt1 = Math.sqrt(tempX);
        long valLong = Double.doubleToLongBits(tempSqrt1) & 0x1fffffffffffffL;

        if (valLong == 0)
            valLong = 1L << 53;

        //////// Classic Newton Iterations ////////
        val = BigInteger.valueOf(valLong).shiftLeft(53 - 1)
                .add((x.shiftRight(xLenMod - (3 * 53))).divide(BigInteger.valueOf(valLong)));

        int size = 106;
        for (; size < 256; size <<= 1) {
            val = val.shiftLeft(size - 1).add(x.shiftRight(xLenMod - (3 * size)).divide(val)); }

        if (xAsDub > 4e254) // 4e254 = 1<<845.77 
        {
            int numOfNewtonSteps = 31 - Integer.numberOfLeadingZeros(wantedPrecision / size) + 1;

            ////// Apply Starting Size ////////
            int wantedSize = (wantedPrecision >> numOfNewtonSteps) + 2;
            int needToShiftBy = size - wantedSize;
            val = val.shiftRight(needToShiftBy);

            size = wantedSize;
            do {
                //////// Newton Plus Iteration ////////
                int shiftX = xLenMod - (3 * size);
                BigInteger valSqrd = val.multiply(val).shiftLeft(size - 1);
                BigInteger valSU = x.shiftRight(shiftX).subtract(valSqrd);
                val = val.shiftLeft(size).add(valSU.divide(val));
                size *= 2;
            } while (size < wantedPrecision);
        }
        val = val.shiftRight(size - wantedPrecision);
    }

    // Detect a round ups. This function can be further optimized - see article.
    // For a ~7% speed bump the following line can be removed but round-ups will occur.
    if (val.multiply(val).compareTo(x) > 0)
        val = val.subtract(BigInteger.ONE);

    // // Enabling the below will guarantee an error is stopped for larger numbers.
    // // Note: As of this writing, there are no known errors.
    // BigInteger tmp = val.multiply(val);
    // if (tmp.compareTo(x) > 0)  {
    //     System.out.println("val^2(" + val.multiply(val).toString() + ") >=  x(" + x.toString() + ")"); 
    //     System.console().readLine();
    //     //throw new Exception("Sqrt function had internal error - value too high");   
    // }
    // if (tmp.add(val.shiftLeft(1)).add(BigInteger.ONE).compareTo(x) <= 0) {
    //     System.out.println("(val+1)^2(" + val.add(BigInteger.ONE).multiply(val.add(BigInteger.ONE)).toString() + ") >=  x(" + x.toString() + ")"); 
    //     System.console().readLine();
    //     //throw new Exception("Sqrt function had internal error - value too low");    
    // }

    return val;
}

Here is a performance comparison vs. the built-in BigInteger.Sqrt()
enter image description here

More details here.

回复 原文
不必在意 2024-10-14 10:24:32

我只讨论平方根的整数部分，但您可以修改这个粗略的算法以达到您想要的更高精度：

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

I am only going as far as the integer part of the square root but you can modify this rough algo to go to as much more precision as you want:

  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;
}
回复 原文
葵雨 2024-10-14 10:24:32

您还可以使用二分查找来查找 x 的平方根
您也可以将其乘以例如 10^10 并通过二分搜索找到像 m 这样的整数，因为 m^2

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

you can also use binary search to find the square root of x
also you can multiply it to for example 10^10 and find an integer like m by binary search since m^2

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

回复 原文
小鸟爱天空丶 2024-10-14 10:24:32

这是一个不使用 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};
    }

Here's a solution that does not use BigInteger.multiply or 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};
    }
回复 原文
寄居者 2024-10-14 10:24:32

我上面发布的答案不适用于大量（但有趣的是！）。因此发布了一种二分搜索方法来确定平方根的正确性。

package com.example.so.squareroot;

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

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

    }


}

问候
拉文德拉

The answer I posted above doesn't work for large numbers (but interestingly so!). As such posting a binary-search approach for determining square root for correctness.

package com.example.so.squareroot;

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

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

    }


}

Regards
Ravindra

回复 原文
甜味拾荒者 2024-10-14 10:24:32

这是一种易于理解的方法，可能没有最佳性能，但它可以在不到一秒的时间内给出单个 BigInteger 的解决方案。

public static BigInteger sqrt(BigInteger n) {
    BigInteger bottom = BigInteger.ONE;
    BigInteger top = n;
    BigInteger mid;
    while(true) {
        mid = top.add(bottom).divide(new BigInteger(""+2));
        top = mid;
        bottom = n.divide(top);
//            System.out.println("top:    "+top);
//            System.out.println("mid:    "+mid);
//            System.out.println("bottom: "+bottom);
        if(top.equals(bottom)) {
            return top;
        }
    }
}

This is an easy to understand way that may not have the best performance but it gives the solution for a single BigInteger in less than a second.

public static BigInteger sqrt(BigInteger n) {
    BigInteger bottom = BigInteger.ONE;
    BigInteger top = n;
    BigInteger mid;
    while(true) {
        mid = top.add(bottom).divide(new BigInteger(""+2));
        top = mid;
        bottom = n.divide(top);
//            System.out.println("top:    "+top);
//            System.out.println("mid:    "+mid);
//            System.out.println("bottom: "+bottom);
        if(top.equals(bottom)) {
            return top;
        }
    }
}
回复 原文
迷你仙 2024-10-14 10:24:32

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

The C# language has similar syntax to Java. I wrote this recursive solution.

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

Call this code like this (in Java I guess it would be "System.out.print").

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

And the answer is:
27993718524262253829858552106

Disclaimer: I understand this method doesn't work for numbers less than 10; this is a BigInteger square root method.

This is easily remedied. Change the first method to the following to give the recursive portion some room to breathe.

    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);            
    }
回复 原文
明媚殇 2024-10-14 10:24:32

我认为单行就可以完成这项工作。

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

A single line can do the job I think.

Math.pow(bigInt.doubleValue(), (1/n));
回复 原文
~没有更多了~

关于作者

偷得浮生

暂无简介

0 文章
0 评论
22 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

留蓝

文章 0 评论 0

18790681156

文章 0 评论 0

zach7772

文章 0 评论 0

Wini

文章 0 评论 0

ayeshaaroy

文章 0 评论 0

初雪

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文