牛顿法估算整数平方根时，为何误差小于1即可得到正确结果？

问题描述 #

针对牛顿法实现整数平方根的代码，存在两点疑问：

• 为何循环终止条件设为while (Math.abs(x0-x1) >= 1)，当两次迭代值的差小于1时，将x1强制转换为int（向下取整）就能得到正确结果？
• 是否存在异常场景：循环终止时x1为7点几，但真实平方根为6点几，导致本应返回6却错误返回7？
  多次测试下逻辑始终运行正常，但不清楚背后的正确性原理。

对应的Java实现代码如下：

class Solution {
  public int mySqrt(int x) {
    if (x < 2) return x;

    double x0 = x;
    double x1 = (x0 + x / x0) / 2.0;
    while (Math.abs(x0 - x1) >= 1) {
      x0 = x1;
      x1 = (x0 + x / x0) / 2.0;
    }

    return (int)x1;
  }
}

原理说明 #

这个逻辑的正确性完全由牛顿迭代求平方根的固有性质保证，不存在你担心的跨整数误差场景，核心依据有两点：

1. 迭代序列的收敛方向固定 #

用迭代公式x_{n+1} = (x_n + x/x_n)/2求√x时，只要初始值x0>0，整个迭代序列会严格从真实值的上方向下单调收敛到√x。也就是说从第一次迭代开始，所有生成的x1、x2...xn永远大于等于真实的√x，不会出现迭代值跳到真实平方根下方的情况。

2. 终止条件的边界约束 #

当循环终止时，满足|x0 - x1| < 1，此时可以结合迭代公式推导边界：
把x1的表达式代入差值不等式，化简后可得|x0 - x/x0| < 2。结合序列单调递减、始终在真实值上方的性质，x0 > √x，可进一步推导得出：只要两次迭代的差值还大于等于1，说明当前迭代值和真实值的差距还足够大，循环不会停止，会继续执行下一轮迭代。

你担心的「x1为7点几、真实平方根为6点几」的场景，只会出现在两次迭代差值≥1的阶段：比如x=48（真实平方根≈6.928）迭代过程中会出现x≈7.06的中间值，但此时和上一轮迭代值的差约为1.37，满足循环继续条件，会再执行一轮迭代，将值更新到≈6.93，此时两次迭代差值约为0.13<1，才会终止循环。

由于牛顿法求平方根是二次收敛，后一轮迭代的误差是前一轮误差的平方量级，当两次迭代差值小于1时，当前x1必然落在区间[√x, floor(√x)+1)内——也就是比真实平方根大，但不会超过真实平方根向上取整的整数边界，此时将x1向下取整（强转int），刚好得到正确的整数平方根结果，不会出现跨整数的返回错误。

内容的提问来源于stack exchange，提问作者Qrow Saki