了解用于在Java中计算BigInteger平方根的基础逻辑/数学(Understanding underlying logic/maths for calculating BigInteger sq

了解用于在Java中计算BigInteger平方根的基础逻辑/数学(Understanding underlying logic/maths for calculating BigInteger square root in Java)

我想用Java计算BigInteger的平方根。在调查时，我发现了这个很棒的链接如何找到Java BigInteger的平方根？，早些时候在StackOverflow上问道。

有两个很棒的代码片段可以解决这个问题。但缺少潜在的逻辑或数学。

这是第一个：

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

取自这里。

这是第二个：

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

由@EdwardFalk回答。

任何人都可以解释或指出基础数学或逻辑，以确保主题的完整性。

I wanted to calculate the square root of BigInteger in Java. While investigating, I found this great link How can I find the Square Root of a Java BigInteger?, asked earlier on StackOverflow.

There are two great code snippets given to solve this. But the underlying logic or maths is missing.

This is the first one :

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

taken from here.

This is the second one :

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

answered by @EdwardFalk.

Can anyone please explain or point to the underlying maths or logic, for the completeness of the topic.