我想用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.
最满意答案
两者基本上都是牛顿迭代 。
然而,第一个代码片段有一些奇怪的曲折,所以我会去第二个片段。
Both are basically a newton iteration.
However the first code snippet has some strange twists, so I would go for the second snippet.
更多推荐
发布评论