不依赖 Math.sqrt 的高精度平方根实现二分法与牛顿迭代法实战解析leetcode 每日一题 my-sqrt【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本指南以 leetcode 仓库「每日一题」模块中的 my-sqrt 题目文档 为骨架完整还原一道「禁用数学库、将 sqrt(2) 精确到小数点后 10 位」的经典面试题并深入剖析其两种标准解法——二分法与牛顿迭代法。读完本文你将掌握浮点精度问题的处理手法、二分法在连续实数解空间上的收敛写法以及牛顿迭代法的切线逼近原理能够将同一套思路迁移到 LeetCode 69. Sqrt(x) 等平方根类题目上。题目背景与信息卡片这道题来自 leetcode 仓库的「每日一题」活动。正如 daily/README.md 所介绍的每日一题是仓库维护者在交流群中组织的一种活动大家一起解一道题题目和解法会被记录下来日后筛选沉淀进题解模块。my-sqrt 即收录于该活动历史汇总中标注时间为 2019-06-27tag 为binary search与math。文档信息卡片要点如下时间2019-06-27文档内信息卡片标注为 2019-06-21以每日一题汇总记录为准题目链接无原文档注明 LeetCode 上有一个相似题目即 69. Sqrt(x)其要求是返回整数平方根tagbinary searchmath题目描述要求不用数学库求 sqrt(2)精确到小数点后 10 位这个题目有两个关键约束禁用数学库不能直接调用Math.sqrt或等价语言库函数必须自行实现求根算法精度要求结果精确到小数点后 10 位即误差不超过10^-10这是一个面向实数解空间的浮点精度问题而不是常见的在有序数组中查找整数下标的整数二分。题目本身是 LeetCode 69. Sqrt(x) 的变体69 题求的是sqrt(x)的整数部分向下取整解空间是整数而本题要求小数点后 10 位的精度解空间是连续实数。二者解法同源但本题对精度的处理要求更高。问题分析连续解空间下的精度思维求sqrt(2)本质上是求方程x^2 - 2 0的正实根。函数f(x) x^2 - 2在[0, 2]上单调递增因此方程在区间内存在唯一根x sqrt(2) ≈ 1.4142135624这保证了二分法的可行性。关于解空间为连续实数这一特性仓库的二分专题讲义 thinkings/binary-search-1.md 中有专门的论述大多数二分题目解空间是整数而少部分题目解空间包括小数。如果解空间包括小数就可能会涉及到精度问题此时有两处关键变化——更新答案的步长整数二分中常见的l mid 1不再适用因为正确解可能恰好落在[mid, mid1]内的某个小数上步长改为 1 会错过解判断结束条件需要考虑误差由于精度问题循环终止条件从找到精确值变成结果与真值的误差在某一个范围内。本文两道解法正是对这两点的直接实践二分法用区间长度收敛到10^-10以内作为终止依据牛顿迭代法用相邻两次迭代值之差小于10^-10作为终止依据。讲义中还建议给上下界设置一个宽泛的范围本题将搜索区间取为[0, 2]或[0, num]正是这一原则的体现。解法一二分法二分法的思路很直接在[0, num]区间内取中间值mid比较mid * mid与num的大小关系。由于x^2在正数域单调递增mid * mid num说明真实根在mid右侧否则在左侧。每次比较都能舍去一半的区间时间复杂度为O(log n)。参考代码来自 my-sqrt 题目文档function sqrt(num) { if (num 0) return num; let start 0; let end num; let mid num 1; const DIGIT_COUNT 10; const PRECISION Math.pow(0.1, DIGIT_COUNT); while (Math.abs((num - mid * mid).toFixed(DIGIT_COUNT)) PRECISION) { mid start (end - start) / 2.0; if (mid * mid num) { start mid; } else { end mid; } } return mid; }逐行拆解其关键设计精度参数DIGIT_COUNT 10对应小数点后 10 位PRECISION Math.pow(0.1, 10) 1e-10是允许的误差上界。将两个参数抽成常量便于按需调整精度。终止条件Math.abs(num - mid * mid) PRECISION即当前候选值平方与目标值之差的绝对值小于1e-10时停止。这里的(...).toFixed(DIGIT_COUNT)先把差值保留 10 位小数再转回数值作用是抹平 JS 浮点运算本身的尾数噪声避免mid * mid的微小浮点误差导致死循环或精度抖动。区间收缩mid * mid num时根在右半区start mid否则根在左半区含当前点end mid。由于解空间是连续实数这里不能用整数二分中的start mid 1而必须保留mid本身。防溢出写法mid start (end - start) / 2.0等价于(start end) / 2但避免了start end在数值极大时溢出的风险这是二分实现的经典最佳实践。初始化的一个细节let mid num 1;使用位运算初始化中间值仅作进入循环前的占位循环体内会立即重新计算。需要注意 JS 的是对 32 位整数进行位运算对大数超过 2^31或非整数num结果不可靠因此只适合这里初始占位的用途循环内的区间计算全部改用浮点运算。从收敛性看区间[0, 2]的初始宽度为 2每轮缩小一半要使宽度小于1e-10需要约log2(2 / 1e-10) ≈ 35轮迭代每轮仅需一次乘法和比较实际运行可在微秒级完成。这一模板与仓库另一道每日一题 744. find smallest letter greater than target 中的二分写法可互为参照那道题在有序字符数组上做整数下标二分区间收缩采用min mid 1/max mid - 1终止条件为min max而本题因解空间连续收缩保留mid、终止条件改为精度判断。对比二者可以清晰看出整数解空间与实数解空间在二分写法上的核心差异。解法二牛顿迭代法牛顿迭代法是牛顿发明的一种求方程近似根的方法思路比较巧妙。求sqrt(a)可以转化为求方程x^2 - a 0的根也就是抛物线f(x) x^2 - a与 x 轴交点y 0的横坐标。我们不断用f(x)在某点的切线来逼近方程的根在曲线上任取一点(x, f(x))作该点的切线切线与 x 轴的交点就是一个比x更接近真实根的近似值。由于f(x) 2x点(x, f(x))处的切线斜率为2x令切线方程y - f(x) 2x * (X - x)中的y 0解得新的近似值X x - f(x) / (2x) x - (x^2 - a) / (2x) (x a / x) / 2即每次迭代公式为x_{n1} (x_n a / x_n) / 2。以下示意图直观展示了切线—与 x 轴交点—再作切线逐步逼近根的过程图片来自 Wikipedia参考代码来自 my-sqrt 题目文档function sqrtNewton(n) { if (n 0) return n; let res; let last; const DIGIT_COUNT 10; const PRECISION Math.pow(0.1, DIGIT_COUNT); res n; while (Math.abs(last - res) PRECISION) { last res; res (res n / res) / 2; } return res; }关键设计解读迭代初值res n直接从目标值本身出发。对n 0的情况该初值位于真实根右侧因为n sqrt(n)当n 1而牛顿法从根的右侧出发向根收敛是稳定的。迭代公式res (res n / res) / 2即(x a / x) / 2正是上面推导出的切线法公式没有调用任何数学库。终止条件Math.abs(last - res) PRECISION即相邻两次迭代结果的差值小于1e-10时停止。牛顿法二次收敛迭代值会迅速稳定用相邻差值作为收敛判据是标准做法。注意这里没有用toFixed抹平误差——因为牛顿法通过除法运算本身就会引入浮点噪声差值判据天然包含了这个容差。收敛速度牛顿迭代法具有二次收敛性即每轮迭代后误差大致变为上一轮的平方。从初值x0 2出发误差约0.586按平方关系衰减迭代序列约为 2 → 1.5 → 1.41667 → 1.41422 → 1.41421...大约 4~5 轮即可把误差压到1e-10以下。相比二分法约 35 轮牛顿法的迭代次数少一个数量级代价是每轮多一次除法n / res运算。当精度要求进一步提高比如精确到小数点后 15 位时牛顿法的优势会更加明显。此外这一迭代框架并不局限于平方根x_{n1} x_n - f(x_n) / f(x_n)对任意可导方程都成立只要知道f和f即可推广到求立方根、一般多项式方程等场景。两种解法对比与选型维度二分法牛顿迭代法核心思路利用单调性不断折半收缩区间利用切线不断逼近曲线与 x 轴交点前提条件函数在区间内单调本题x^2单调递增函数可导且导数已知本题f(x) 2x每轮开销一次乘法、一次比较一次除法、一次加法、一次除法n / res迭代轮数精度 1e-10约 35 轮约 4~5 轮收敛阶数线性区间每次减半二次误差平方级衰减边界处理需显式处理num 0需显式处理n 0实现难度低逻辑直白不易出错中需理解切线几何意义选型建议面试或工程实践中若追求代码简单、易于向面试官解释正确性二分法是稳妥之选若对性能敏感或精度要求极高牛顿迭代法更优。二者在本题中结果一致都收敛到1.4142135624附近误差小于1e-10但体现了两种截然不同的算法思想——前者是搜索后者是逼近。延伸从每日一题到仓库二分专题本题的精度处理手法与 leetcode 仓库的二分专题一脉相承。在 thinkings/binary-search-1.md 中作者将解空间包含小数的二分作为二分专题的重点难点之一并明确指出求平方根正是这类题型的典型代表原文以求 x 的平方根答案误差在 10^-6 次方都认为正确为例同时给出了两个工程建议解空间宁大勿小定义搜索区间时可以大但不可以小区间偏大只是多几次运算区间过小则可能错失正确解。本题将区间取为[0, num]正是遵循该原则二分不限于数组二分法要求的是序列有序本题的序列是x^2在正数域的单调递增性质属于题目条件隐含的有序性这也是很多二分题目的隐藏考点。对于想继续加深二分功底的读者仓库还收录了大量可配套练习的二分题目例如 875. koko-eating-bananas、33. search-in-rotated-sorted-array、4. median-of-two-sorted-arrays 等均可结合二分专题讲义对照学习。小结本题虽小却同时覆盖了二分法、浮点精度处理、牛顿迭代法三个重要考点。回顾全篇要点二分法通过对连续解空间的单调收缩求解终止条件从找到精确值改为误差小于 PRECISION并通过toFixed抹平浮点噪声牛顿迭代法利用切线逼近把求根问题转化为迭代公式x_{n1} (x_n a / x_n) / 2以二次收敛的速度在寥寥数轮内达到1e-10精度两种解法均不依赖任何数学库函数完全符合不用数学库求 sqrt(2) 精确到小数点后 10 位的题目约束。原文档末尾的「其他优秀解答」栏目当时标注为暂无读者不妨在理解上述两种解法后自行尝试给出第三种实现例如基于位运算的整数逼近后再做浮点修正作为对该题更深入的思考练习。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 不依赖 Math.sqrt 的高精度平方根实现：二分法与牛顿迭代法实战解析（leetcode 每日一题 my-sqrt）
不依赖 Math.sqrt 的高精度平方根实现二分法与牛顿迭代法实战解析leetcode 每日一题 my-sqrt【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本指南以 leetcode 仓库「每日一题」模块中的 my-sqrt 题目文档 为骨架完整还原一道「禁用数学库、将 sqrt(2) 精确到小数点后 10 位」的经典面试题并深入剖析其两种标准解法——二分法与牛顿迭代法。读完本文你将掌握浮点精度问题的处理手法、二分法在连续实数解空间上的收敛写法以及牛顿迭代法的切线逼近原理能够将同一套思路迁移到 LeetCode 69. Sqrt(x) 等平方根类题目上。题目背景与信息卡片这道题来自 leetcode 仓库的「每日一题」活动。正如 daily/README.md 所介绍的每日一题是仓库维护者在交流群中组织的一种活动大家一起解一道题题目和解法会被记录下来日后筛选沉淀进题解模块。my-sqrt 即收录于该活动历史汇总中标注时间为 2019-06-27tag 为binary search与math。文档信息卡片要点如下时间2019-06-27文档内信息卡片标注为 2019-06-21以每日一题汇总记录为准题目链接无原文档注明 LeetCode 上有一个相似题目即 69. Sqrt(x)其要求是返回整数平方根tagbinary searchmath题目描述要求不用数学库求 sqrt(2)精确到小数点后 10 位这个题目有两个关键约束禁用数学库不能直接调用Math.sqrt或等价语言库函数必须自行实现求根算法精度要求结果精确到小数点后 10 位即误差不超过10^-10这是一个面向实数解空间的浮点精度问题而不是常见的在有序数组中查找整数下标的整数二分。题目本身是 LeetCode 69. Sqrt(x) 的变体69 题求的是sqrt(x)的整数部分向下取整解空间是整数而本题要求小数点后 10 位的精度解空间是连续实数。二者解法同源但本题对精度的处理要求更高。问题分析连续解空间下的精度思维求sqrt(2)本质上是求方程x^2 - 2 0的正实根。函数f(x) x^2 - 2在[0, 2]上单调递增因此方程在区间内存在唯一根x sqrt(2) ≈ 1.4142135624这保证了二分法的可行性。关于解空间为连续实数这一特性仓库的二分专题讲义 thinkings/binary-search-1.md 中有专门的论述大多数二分题目解空间是整数而少部分题目解空间包括小数。如果解空间包括小数就可能会涉及到精度问题此时有两处关键变化——更新答案的步长整数二分中常见的l mid 1不再适用因为正确解可能恰好落在[mid, mid1]内的某个小数上步长改为 1 会错过解判断结束条件需要考虑误差由于精度问题循环终止条件从找到精确值变成结果与真值的误差在某一个范围内。本文两道解法正是对这两点的直接实践二分法用区间长度收敛到10^-10以内作为终止依据牛顿迭代法用相邻两次迭代值之差小于10^-10作为终止依据。讲义中还建议给上下界设置一个宽泛的范围本题将搜索区间取为[0, 2]或[0, num]正是这一原则的体现。解法一二分法二分法的思路很直接在[0, num]区间内取中间值mid比较mid * mid与num的大小关系。由于x^2在正数域单调递增mid * mid num说明真实根在mid右侧否则在左侧。每次比较都能舍去一半的区间时间复杂度为O(log n)。参考代码来自 my-sqrt 题目文档function sqrt(num) { if (num 0) return num; let start 0; let end num; let mid num 1; const DIGIT_COUNT 10; const PRECISION Math.pow(0.1, DIGIT_COUNT); while (Math.abs((num - mid * mid).toFixed(DIGIT_COUNT)) PRECISION) { mid start (end - start) / 2.0; if (mid * mid num) { start mid; } else { end mid; } } return mid; }逐行拆解其关键设计精度参数DIGIT_COUNT 10对应小数点后 10 位PRECISION Math.pow(0.1, 10) 1e-10是允许的误差上界。将两个参数抽成常量便于按需调整精度。终止条件Math.abs(num - mid * mid) PRECISION即当前候选值平方与目标值之差的绝对值小于1e-10时停止。这里的(...).toFixed(DIGIT_COUNT)先把差值保留 10 位小数再转回数值作用是抹平 JS 浮点运算本身的尾数噪声避免mid * mid的微小浮点误差导致死循环或精度抖动。区间收缩mid * mid num时根在右半区start mid否则根在左半区含当前点end mid。由于解空间是连续实数这里不能用整数二分中的start mid 1而必须保留mid本身。防溢出写法mid start (end - start) / 2.0等价于(start end) / 2但避免了start end在数值极大时溢出的风险这是二分实现的经典最佳实践。初始化的一个细节let mid num 1;使用位运算初始化中间值仅作进入循环前的占位循环体内会立即重新计算。需要注意 JS 的是对 32 位整数进行位运算对大数超过 2^31或非整数num结果不可靠因此只适合这里初始占位的用途循环内的区间计算全部改用浮点运算。从收敛性看区间[0, 2]的初始宽度为 2每轮缩小一半要使宽度小于1e-10需要约log2(2 / 1e-10) ≈ 35轮迭代每轮仅需一次乘法和比较实际运行可在微秒级完成。这一模板与仓库另一道每日一题 744. find smallest letter greater than target 中的二分写法可互为参照那道题在有序字符数组上做整数下标二分区间收缩采用min mid 1/max mid - 1终止条件为min max而本题因解空间连续收缩保留mid、终止条件改为精度判断。对比二者可以清晰看出整数解空间与实数解空间在二分写法上的核心差异。解法二牛顿迭代法牛顿迭代法是牛顿发明的一种求方程近似根的方法思路比较巧妙。求sqrt(a)可以转化为求方程x^2 - a 0的根也就是抛物线f(x) x^2 - a与 x 轴交点y 0的横坐标。我们不断用f(x)在某点的切线来逼近方程的根在曲线上任取一点(x, f(x))作该点的切线切线与 x 轴的交点就是一个比x更接近真实根的近似值。由于f(x) 2x点(x, f(x))处的切线斜率为2x令切线方程y - f(x) 2x * (X - x)中的y 0解得新的近似值X x - f(x) / (2x) x - (x^2 - a) / (2x) (x a / x) / 2即每次迭代公式为x_{n1} (x_n a / x_n) / 2。以下示意图直观展示了切线—与 x 轴交点—再作切线逐步逼近根的过程图片来自 Wikipedia参考代码来自 my-sqrt 题目文档function sqrtNewton(n) { if (n 0) return n; let res; let last; const DIGIT_COUNT 10; const PRECISION Math.pow(0.1, DIGIT_COUNT); res n; while (Math.abs(last - res) PRECISION) { last res; res (res n / res) / 2; } return res; }关键设计解读迭代初值res n直接从目标值本身出发。对n 0的情况该初值位于真实根右侧因为n sqrt(n)当n 1而牛顿法从根的右侧出发向根收敛是稳定的。迭代公式res (res n / res) / 2即(x a / x) / 2正是上面推导出的切线法公式没有调用任何数学库。终止条件Math.abs(last - res) PRECISION即相邻两次迭代结果的差值小于1e-10时停止。牛顿法二次收敛迭代值会迅速稳定用相邻差值作为收敛判据是标准做法。注意这里没有用toFixed抹平误差——因为牛顿法通过除法运算本身就会引入浮点噪声差值判据天然包含了这个容差。收敛速度牛顿迭代法具有二次收敛性即每轮迭代后误差大致变为上一轮的平方。从初值x0 2出发误差约0.586按平方关系衰减迭代序列约为 2 → 1.5 → 1.41667 → 1.41422 → 1.41421...大约 4~5 轮即可把误差压到1e-10以下。相比二分法约 35 轮牛顿法的迭代次数少一个数量级代价是每轮多一次除法n / res运算。当精度要求进一步提高比如精确到小数点后 15 位时牛顿法的优势会更加明显。此外这一迭代框架并不局限于平方根x_{n1} x_n - f(x_n) / f(x_n)对任意可导方程都成立只要知道f和f即可推广到求立方根、一般多项式方程等场景。两种解法对比与选型维度二分法牛顿迭代法核心思路利用单调性不断折半收缩区间利用切线不断逼近曲线与 x 轴交点前提条件函数在区间内单调本题x^2单调递增函数可导且导数已知本题f(x) 2x每轮开销一次乘法、一次比较一次除法、一次加法、一次除法n / res迭代轮数精度 1e-10约 35 轮约 4~5 轮收敛阶数线性区间每次减半二次误差平方级衰减边界处理需显式处理num 0需显式处理n 0实现难度低逻辑直白不易出错中需理解切线几何意义选型建议面试或工程实践中若追求代码简单、易于向面试官解释正确性二分法是稳妥之选若对性能敏感或精度要求极高牛顿迭代法更优。二者在本题中结果一致都收敛到1.4142135624附近误差小于1e-10但体现了两种截然不同的算法思想——前者是搜索后者是逼近。延伸从每日一题到仓库二分专题本题的精度处理手法与 leetcode 仓库的二分专题一脉相承。在 thinkings/binary-search-1.md 中作者将解空间包含小数的二分作为二分专题的重点难点之一并明确指出求平方根正是这类题型的典型代表原文以求 x 的平方根答案误差在 10^-6 次方都认为正确为例同时给出了两个工程建议解空间宁大勿小定义搜索区间时可以大但不可以小区间偏大只是多几次运算区间过小则可能错失正确解。本题将区间取为[0, num]正是遵循该原则二分不限于数组二分法要求的是序列有序本题的序列是x^2在正数域的单调递增性质属于题目条件隐含的有序性这也是很多二分题目的隐藏考点。对于想继续加深二分功底的读者仓库还收录了大量可配套练习的二分题目例如 875. koko-eating-bananas、33. search-in-rotated-sorted-array、4. median-of-two-sorted-arrays 等均可结合二分专题讲义对照学习。小结本题虽小却同时覆盖了二分法、浮点精度处理、牛顿迭代法三个重要考点。回顾全篇要点二分法通过对连续解空间的单调收缩求解终止条件从找到精确值改为误差小于 PRECISION并通过toFixed抹平浮点噪声牛顿迭代法利用切线逼近把求根问题转化为迭代公式x_{n1} (x_n a / x_n) / 2以二次收敛的速度在寥寥数轮内达到1e-10精度两种解法均不依赖任何数学库函数完全符合不用数学库求 sqrt(2) 精确到小数点后 10 位的题目约束。原文档末尾的「其他优秀解答」栏目当时标注为暂无读者不妨在理解上述两种解法后自行尝试给出第三种实现例如基于位运算的整数逼近后再做浮点修正作为对该题更深入的思考练习。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考