有趣的定理 · 算术平方根的近似公式与迭代之美
从毕达哥拉斯树到牛顿迭代法，再到二进制平方根算法，有趣的定理带你走进数字背后的幽默与深刻。
✦ 开篇 · 那些让人犯困却又好玩的定理
今天咱们聊聊数学界那些一听就犯困，但换个角度听又能笑到肚子疼的定理。别跟我提费马大定理，那玩意儿忒严肃了，像块高冷的石头。还有那些证明里堆满符号和公理推导的东西，也先放放。
我要介绍的，是算术平方根的近似公式，也就是所谓的毕达哥拉斯树在那儿乱晃，实际上核心只是一个好办的线性递推。你看，任何自然数 ( n )，只要不是彻底平方数，它下面的算术平方根在二进制里就是个一辈子循环的 1 后面跟无限多个 0。这听起来挺抽象对吧？好办点说，就是开根号那玩意儿在机器里存不了个整数值，你得给它加点小数位，要么搞个高精度的浮点数。这就好比你在水泥地里想挖个洞，光凭手感觉准吗？准，但得用尺子量，并且得是数字化的尺子。
还记得那个经典的勾股数例子吗？3, 4, 5 三角形。设 ( a=3, b=4, c=5 )。平方和：( 3^2=9 )，( 4^2=16 )，加起来正好 25。再试一组更大的，比如斐波那契数列里的 ( a=8, b=13, c=17 )。( 8^2=64 )，( 13^2=169 )，( 17^2=289 )。( 64+169=289 )。这仿佛没啥特殊的，就是勾股定理本身。那有没有啥规律能直接算出这些数？有的。
✦ 牛顿迭代法 · 从猜想到收敛
有一个最著名的公式，叫毕达哥拉斯树的变体，要么更准地说，是欧几里得要么皮亚哥那些人在数论课上走的弯路，最终发现了一个好办的迭代公式。假设我们想算 ( sqrt{n} )。你能够随意取个整数 ( x )，然后算 ( (x + n/x) / 2 )。这一套操作重复几次，你就越来越接近实数解了。这个公式叫啥？它叫牛顿迭代法。听起来就挺像牛顿研究物理定律时的样子，但用在这里彻底是另一回事。
? 实例：计算 √13
先随意取个 ( x=3 )。第一步，算 ( (3 + 13/3) / 2 = (3 + 4.333) / 2 = 3.666... )。第二步，目前 ( x ) 约等于 3.666。再算 ( (3.666 + 13/3.666) / 2 )。第三步，持续迭代。你会发现，你的估摸值每次都会往真值“吸”那会儿。这就像你在泥地里抓苍蝇，刚启动抓不住，抓待会儿松手，苍蝇就飞到你手心了。
? 敏感细节 · 初始值偏差
要是你选 ( x=3.000...01 )，也就是比 3 略微大一点点，那第一次迭代的结局就会比真值大。反之，要是你选 ( x=2.999...99 )，那结局就会比真值小。这说明这个迭代过程贼敏感，对初始值的细小偏差贼敏感。在计算机里，这简直是灾难。出于浮点数有限精度，你没法保证第一步就启动“对”。你输入 0.000001，结局可能输出 3.000000001，再输入 0.000000001，输出变成 3.00000000001，最终又变成 3.0000000000001。你当作它收敛了，实际上只是在原地踏步，卡在那儿。
? 整数特例与质数陷阱
对于某些特殊的数，比如 ( n=121 )，( sqrt{121}=11 )，是个整数。这时候迭代法会贼稳定，直接收敛到整数。但要是 ( n ) 是个质数，要么某个看起来挺整的数实际上不是彻底平方数，比如 ( n=145 )（( 12^2=144 )，( 12.08... )），这时候迭代过程就会在数字之间跳来跳去，就连有时候会出于舍入误差出现负数，害得逻辑彻底反了。这就好比你在玩一个找茬的游戏，屏幕上的数字红蓝闪烁，你不知道哪一个是真，哪一个是假。
✦ 二进制树 · 平方根的线性扫描宿命
这就让人联想到那个由 0 和 1 组成的二进制树。你在二叉搜索树里找中间值，每次判断左子树还是右子树。最终它会走到某个叶子节点。这个叶子节点的位置，就是整个树的高度。对于满二叉树，要么接近满二叉树的树，它的高度是 ( log_2 N )。那要是树略微偏一点呢？比如你少挂了几个叶子节点，高度会不会变成 ( log_2 N + 1 )？嗯，没错。这就解释了为啥树的结构对性能影响庞大。
? 树高度与 log₂N
- 满二叉树高度 = ⌊log₂N⌋
- 偏斜树高度 = N-1
- 平衡树 ≈ 1.44 log₂N
- 实际工程中红黑树、AVL 树
? 平方根二进制算法
在二进制里，( sqrt{n} ) 的过程实际上是在做某种位移和加法的组合。从最高位启动减 1，每次减去之前那个 1 的后继，直到 0。这个过程工夫复杂度是 ( O(log N) )？可是，有一个定理告诉我们，不存有这样的算法。也就是说，计算 ( sqrt{n} ) 起码得线性扫描。扫一遍二进制，一遍 OK。扫一遍十进制，也 OK。扫一遍一般/平平的浮点数（比如 64 位），也 OK。
? 具体二进制扫描 · n=10 的案例
假设 ( n=10 )，二进制 1010。从最高位启动，找到第一个 1，记作 ( c_0=1 )。然后找到第二个 1，记作 ( c_1=0 )…… 最终收敛到 ( sqrt{10} ≈ 3.1623 )。二进制表示 11.0010... 这个过程虽然琐碎，但揭示了线性扫描的本质。更多细节可参考下方选项卡。
✦ 更多示例 · 卡片里的数字游戏
? 勾股数生成
欧几里得公式：( a=m^2-n^2, b=2mn, c=m^2+n^2 )。取 m=4, n=1 得到 (15,8,17)。再如 m=5, n=2 得 (21,20,29)。
- -5 三角形
- -13
- -17
? 牛顿迭代收敛速度
初始值 x=2 算 √5：第一步 2.25，第二步 2.2361，第三步 2.23607。二次收敛！每次有效数字翻倍。
⚠️ 浮点数陷阱
位双精度浮点，当 n=2^53+1 时，√n 无法精确表示，迭代可能陷入死循环。实际测试：n=9007199254740993 时出现震荡。
✦ 深度选项卡 · 毕达哥拉斯树变体 & 复杂度
毕达哥拉斯树与欧几里得迭代
毕达哥拉斯树的变体本质是 ( x_{k+1} = (x_k + n/x_k)/2 )。这个公式可以追溯到巴比伦时期，但牛顿将其发扬光大。有趣的是，如果初始值选择为 ( lfloor sqrt{n} rfloor )，迭代次数不超过 5 次就能达到双精度精度。例如 n=13, 初始 3，迭代序列：3 → 3.6667 → 3.6066 → 3.60555 → 3.605551275。
伪代码 & 浮点数陷阱
function sqrtNewton(n, initial, tol=1e-15):
x = initial
while True:
next_x = (x + n/x) 0.5
if abs(next_x - x) < tol:
break
x = next_x
return x
对于 n=121, 初始 10, 迭代: 10 → 11.05 → 11.0001 → 11.000000 → 11。整数完美收敛。但对于 n=2, 初始 1.4, 迭代: 1.4 → 1.4142857 → 1.41421356 → 1.41421356。
网友们还关心：如果 n 是质数且接近完全平方，比如 n=14641 (121²), 迭代会直接命中整数，但浮点数舍入可能导致最后几位跳动。
为什么平方根计算至少是线性扫描？
任何计算 ( sqrt{n} ) 的算法都必须读取 n 的二进制表示的所有有效位。因为平方根是一个非多项式函数，输出对输入的每一位都敏感。更正式地，定理：如果存在亚线性时间算法计算 ( sqrt{n} ) 到 1 ulp 精度，则存在亚线性时间算法判断两个数是否相等，矛盾。因此复杂度下界是 ( Omega(log n) )，即线性于位数。
? 更多定理碎片 · 从欧几里得到皮亚哥
欧几里得在《几何原本》中给出了平方根的几何作图法，而皮亚哥学派则发现了无理数的存在。有趣的是，毕达哥拉斯树的迭代公式竟然和牛顿法如出一辙。我们再来看一个例子：计算 √2 的巴比伦方法：初始 1, 迭代: (1+2/1)/2=1.5, (1.5+2/1.5)/2=1.41667, 第三次 1.4142157, 第四次 1.41421356。这就是牛顿迭代法的雏形。
另外，网友们还关心：为什么 3,4,5 是勾股数？因为 3²+4²=5²。但 8,13,17 呢？8²+13²=64+169=233，而 17²=289，不相等？等等，原文中 8,13,17 的例子有误？实际上 8²+13²=233，17²=289，并不相等。但 8,15,17 是勾股数 (64+225=289)。所以正确的斐波那契勾股数应该是 (3,4,5), (5,12,13), (8,15,17) 等。这里特别勘误，保证知识严谨。
回到算术平方根近似公式，我们还可以使用连分数表示：√13 = [3; 1,1,1,1,6,...]，收敛更快。但牛顿迭代法由于二次收敛，在计算机中更常用。最后，有趣的定理告诉我们：数学不是冰冷的符号，而是充满幽默与深度的探险。