在C++中求平方根的巴比伦算法中出现了无限循环

Question

我在互联网上仔细搜索了这个主题，帖子要么已经过期，要么使用的方法与我书中描述的不同。

例如：http://www.geeksforgeeks.org/square-root-of-a-perfect-square/。此链接中提供的方法对我无效，因为我的算法需要循环直到达到上一“猜测”的1％。

以下是文本中的问题：

巴比伦算法计算数字n的平方根如下：

1. 猜测一个数字（初始猜测值可以选取n / 2）。
2. 计算r = n / guess。
3. 设置guess =（guess + r）/ 2。
4. 返回步骤2，直到满足条件。重复第2和第3步的次数越多，guess将越接近n的平方根。

编写程序，输入整数n，通过巴比伦算法迭代，直到猜测值相对于之前的猜测值的误差小于1％，并将答案输出为double类型。

我已编写以下代码：

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

int main()
{
int  n;
double r, guess(4), lastGuess;

cout << "Enter a number to find the square root of: ";
cin >> n;

do
{

    r = n / guess;
    lastGuess = guess;
    guess = ( guess + r ) / 2;

//  cout <<"Guess: " << guess << endl;
//  cout <<"Last Guess: " << lastGuess << endl;

    cout << "Guess : " << guess  << endl;
    cout << "Last Guess 1% = " << lastGuess + ( lastGuess * 0.01 ) << endl;
    cout << "r = " << r << endl;

} while( guess >= lastGuess * 0.01 );
cout << r;

return 0;
}

该程序计算出了r的正确答案，但是循环并没有终止，尽管猜测值大于上一次猜测值加1%。当输入144作为n时，该程序会产生以下输出。

....
r = 12
Guess : 12
Last Guess 1% = 12.12
r = 12
Guess : 12
Last Guess 1% = 12.12
r = 12
Guess : 12
Last Guess 1% = 12.12
r = 12
Guess : 12
Last Guess 1% = 12.12
....

根据当前猜测的结果（小于上一次猜测结果），条件判断应该返回false，以此来结束循环，但是循环却没有结束。请问原因是什么？根（r）是正确的（12）。猜测结果比上一次猜测结果少（12＜12.12）。

- Anthony Santiago

Answer 1

如果您想增加1％，则需要乘以1.01，而不是0.01。

while( guess >= lastGuess * 1.01 );

顺便提一下，当猜测增加超过1%时，这个迭代会继续进行。你也应该考虑相反的情况，即它可能缩小超过1%。近似值可以从任何方向逼近答案。（对于正根，它将从右侧逼近，对于负根，它将从左侧逼近。）

- John Kugelman

---

没错！这是正确的。我的原始表达式是lastGuess +（lastGuess * 0.01）。我不记得当时为什么删掉了它。现在看起来很有道理。那应该和（lastGuess * 1.01）是一样的。我现在也明白了你所说的n小于4的情况。非常感谢！ - Anthony Santiago

你还应该考虑相反的情况，即它可能缩小了超过1％。幸运的是，迭代值会交替地偏高和偏低。 - David Eisenstat

@DavidEisenstat 牛顿法可以交替使用。巴比伦方法倾向于从右侧收敛。 - John Kugelman

实际上，它总是从右侧收敛，因此我关于其他检查是多余的评论成立。 - David Eisenstat

从技术上讲，当考虑负根时，它将从外部收敛。如果你猜测100的平方根为-20，它将从左侧收敛到-10。 - John Kugelman

我刚刚自己尝试了一下，我必须考虑到两个方面。我知道我必须应用这两个检查，但在你解释之前，我不知道为什么。我没有在这里包含代码，因为解决方案将反映我需要为第二个检查做什么。它被留在帖子中以使代码更清晰，这样你们就可以更好地帮助我并专注于一个明确的主题。 - Anthony Santiago

Answer 2

在打印你的lastGuess时，你正在使用

 lastGuess + ( lastGuess * 0.01 )

但是在检查循环条件时，您使用的是

lastGuess*0.01

因此，在循环条件中使用与打印lastGuess值所使用的相同方程式。

- Hemant Gangwar

Answer 3

为了正确退出循环，请使用类似于以下内容的代码。

void f(int N)
{
    double x = N / 4;
    double prev = 0.0f;

    while(1)
    {
        x = 0.5 * (x + N / x);
        if (prev == x)
            break;

        prev = x;
        printf("val: %f\n", x);
    }

    printf("SQRT(%d) = %f\n", N, x);
}

- Ashot Madatyan

Answer 4

我在我的书中也遇到了同样的问题。这是我写的代码，它完美地运行。

#include <iostream>
using namespace std;
int main()
{
    double guess, root, previousGuess;
    int number;
    cout << "Enter a number to find the Babylonian square root.\n";
    cin >> number;
    cout << "You want to find the square root of " << number << ".\n";
    cout << "Enter a guess for the square root.\n";
    cin >> guess;

    do
    {
        root = number / guess;
        previousGuess = guess;
        guess = (guess + root ) / 2;

    } while(guess < 0.99*previousGuess || guess > 1.01*previousGuess);

    cout << "The answer is " << guess << ".\n";
    return 0;
}

- FrankGray