java - BigInteger Sqrt 函数不收敛

Question

我目前正在编写一个函数来计算给定 BigInteger 的平方根。我的测试文件中的当前数字是 250074134890485729738。然而，程序总是在找到 15813732488 处的 sqrt 时停止，其平方是 250074135202026670144。我已经复制了这个 来自另一个 StackOverflow 问题的代码，并且它停止收敛于相同的数字。它使用牛顿法，而我使用的是巴比伦法/海伦法。

他们的代码:

    public static BigInteger sqrtN(BigInteger in) {
final BigInteger TWO = BigInteger.valueOf(2);
int c;

// Significantly speed-up algorithm by proper select of initial approximation
// As square root has 2 times less digits as original value
// we can start with 2^(length of N1 / 2)
BigInteger n0 = TWO.pow(in.bitLength() / 2);
// Value of approximate value on previous step
BigInteger np = in;

do {
    // next approximation step: n0 = (n0 + in/n0) / 2
    n0 = n0.add(in.divide(n0)).divide(TWO);

    // compare current approximation with previous step
    c = np.compareTo(n0);

    // save value as previous approximation
    np = n0;

    // finish when previous step is equal to current
}  while (c != 0);

return n0;}

我的代码:

    static BigInteger number;
static BigInteger sqrt;

public static void main(String[] args) throws Exception {

    number = new BigInteger(getFile());
    System.out.println("Factoring: \n\n" + number);
    sqrt = sqrt();
    System.out.println("The root is: " + sqrt.toString());
    System.out.println("Test, should equal nearest square at or above original number: " + sqrt.multiply(sqrt).toString() + "\nOriginal number: " + number.toString());
}
public static BigInteger sqrt() {
   BigInteger guess = number.divide(new BigInteger("500"));
   BigInteger TWO = new BigInteger("2");
   BigInteger HUNDRED = new BigInteger("100");
   boolean go = true;
   while (number.subtract((guess.multiply(guess))).abs().compareTo(HUNDRED) ==  1 &&      go){
       BigInteger numOne = guess.divide(TWO);
       BigInteger numTwo = number.divide(guess.multiply(TWO));
       guess = numOne.add(numTwo);
       if (numOne.equals(numTwo))
           go = false;
       System.out.println(guess.toString());
   }


    return guess.add(BigInteger.ONE);

我的输出:

保理:

250074134890485729738
250074134890485979
125037067445243488
62518533722622743
31259266861313370
15629633430660684
7814816715338341
3907408357685169
1953704178874583
976852089501290
488426044878644
244213022695321
122106511859659
61053256953828
30526630524913
15263319358455
7631667871224
3815850319588
1907957927606
954044498302
477153309146
238838702566
119942872245
61013907968
32556274730
20118781556
16274333124
15820250501
15813733820
15813732478
15813732478
The root is: 15813732479
Test, should equal nearest square at or above original number: 250074134917379485441
Original number: 250074134890485729738

一些注意事项:

1. 我在写这篇文章时有几个想法，我尝试了它们。如果有什么不匹配，那是我的错。我确实检查过，但我并不完美。
2. 虽然我很感激人们慷慨地向我指出另一段预先编写的代码/发布他们自己的代码，但这(虽然不是学校作业)对我来说是一种学习经历。请务必发布如何修复此代码，请不要仅发布执行相同操作的不同代码段。

回答:这实际上是按原样工作的，原始输入根本不是一个完美的正方形。因此，这非常适合我的目的。感谢所有因我的无能而浪费时间的人。我更改了代码以返回一个等效于(如果 Math.sqrt/ceil 在 BigInts 上工作)的值:

    sqrt = Math.Ceil(Math.Sqrt(A_RANDOM_BIGINTEGER_HERE));

我还删除了不必要的变量，并更新了输出以匹配。这两种方法都可以正常工作，尽管第一种方法需要一些代码来捕获非收敛循环，以防将来此问题的任何访问者希望使用它们。

Answer 1

15813732478 是250074134890485729738 的平方根，至少是它的整数部分。根据 calc，真正的平方根是 15813732478.149670840219509075711。

有两个问题:

1. 您正在循环 100 次而不是在收敛处停止。
2. 您对 sqrt(N)*sqrt(N) = N 的假设是错误的，因为您只计算积分部分，所以会出现与 N< 成正比的误差。