ARTICLE DETAIL

资讯详情

深耕网站建设与运营推广的一线实战洞察。

《程序员数学:割圆术》—— 基于 N-gons 递推的近似 π 计算实战解析

《程序员数学:割圆术》—— 基于 N-gons 递推的近似 π 计算实战解析 文档教程后端【免费下载链接】CodeGuide:books: 本代码库是作者小傅哥多年从事一线互联网 Java 开发的学习历程技术汇总旨在为大家提供一个清晰详细的学习教程侧重点更倾向编写Java核心内容。如果本仓库能为您提供帮助请给予支持(关注、点赞、分享)项目地址https://gitcode.com/gh_mirrors/code/CodeGuide点击查看免费下载本篇技术指南聚焦小傅哥《程序员数学 v2.0》系列中的经典篇章「割圆术LiuHui」以三国时期数学家刘徽的割圆思想为主线完整讲解其历史脉络、勾股定理递推原理以及仓库文档中给出的蒙特卡洛投点liuHui01与 N 边形边长递归liuHui02两套 Java 实现。读完本篇你将掌握「用圆内接正多边形逼近圆」的核心数学建模方法能够独立用代码递推出 96 边形、192 边形甚至更高精度的 π 近似值并理解两种实现背后收敛速度与计算复杂度的本质差异。一、割圆术在《程序员数学》中的位置在 docs/md/algorithm/logic/math/math.md 中小傅哥的《程序员数学》共收录了数学方向 14 章内容包括二进制、阶乘、斐波那契、RSA、割圆术、傅里叶变换等。这些内容并非孤立的数学题而是与工程实践强关联——例如数据库路由中散列算法的雪崩测试、非对称加密中对素数的选择等都属于把数学落到代码里的典型场景。割圆术正是这类数学 代码结合的极佳样本它只用初中几何级别的勾股定理就能通过反复迭代把 π 的精度从 3 一路推到 3.141696 边形其递推结构与算法设计中的倍增收敛思想一脉相承。二、历史背景刘徽之前与之后的 π 精度之争1. 割圆术的发明者与时代背景刘徽的 π 算法由曹魏国的数学家刘徽公元 3 世纪发明。在他之前中国古代对圆周率圆周长与直径之比的取值多为经验性的人物 / 来源取值精度早期经验值π ≈ 3.01 位有效数字张衡78-139π ≈ 92/29 ≈ 3.1724 或 π ≈ √10 ≈ 3.162精确到小数点后 1 位王蕃219-257π ≈ 142/45 ≈ 3.156精确到小数点后 1 位张衡的取值来自天球与地球直径的比例推算王蕃的取值同样是经验拟合。刘徽对这类经验 π并不满意评论它们太大超出了标准。刘徽是第一位为精确计算 π 提供严格算法的中国数学家——他用自己的割圆术计算到九十六边形得到了精确到五位有效数字的结果π ≈ 3.1416。从这段历史可以看到割圆术的诞生动机是用确定性的几何递推取代经验估计这正是算法的本质一个可以反复执行、逐步逼近精确值的计算过程。三、算法原理从六边形开始的几何递推1. 核心思路用圆内接正多边形逼近圆刘徽从一个内接于圆的正六边形开始。设AB为六边形的一条边的长度记作Mr为圆的半径。随后用线OPC平分弧AB得到新的弦AC。AC恰好成为圆内接**正十二边形12 边形**的一条边令其长度为m。此时PC的长度记为j弦心距方向上的增量OP的长度记为G。由于AOP与APC是两个直角三角形刘徽反复引用勾股定理勾股定理完成边长换算2. 递推关系由 m 求 M至此我们就掌握了一种由m确定M的技术——给定当前多边形的边长就能计算出边数翻倍后的多边形边长对当前边长M取半halfSide M / 2用勾股定理求弦心距perpendicular √(r² - halfSide²)求半径超出弦心距的部分excessRadius r - perpendicular再用勾股定理求新边长m √(excessRadius² halfSide²)。从六边形出发用该公式可以依次求出十二边形、二十四边形、四十八边形……的边长理论上可以无限递归下去。而多边形的边数序列为6、12、24、48、96……即每次迭代边数翻倍2ⁿ倍。知道边长与边数后多边形的周长L 边长 × 边数即可求出而圆面积约等于多边形周长的一半乘以半径三角形剖分求和最终即可逼近 π。四、算法实现两套 Java 代码逐行解析原文档作者特别提醒直到去测试验证割圆术我才体会到为啥要用那么多强大的计算机来计算 π 了因为像我这样的电脑根本计算不出多少位 π 值就把风扇跑得嗖嗖的了这背后正是两种实现截然不同的计算复杂度。1. 复杂度高蒙特卡洛随机投点法liuHui01public static double liuHui01(int splitPoint) { // 圆的半径 double r 1.0; // 正方形的边长 double s 2.0 * r; Random rand new Random(); // 计算圆内随机生成的点的个数 int m 0; for (int i 0; i splitPoint; i) { double x rand.nextDouble() * s - r; double y rand.nextDouble() * s - r; if (x * x y * y r * r) { m; } } // 面积比 圆的面积 / 正方形的面积 double p (double) m / splitPoint; // 圆周率 面积比 * 4 return p * 4; }实现要点该方法接收一个整数splitPoint表示投点采样次数半径为r 1.0外接正方形边长s 2.0 * r正方形面积 4圆面积 π循环splitPoint次每次在[-r, r] × [-r, r]范围内随机生成点(x, y)若满足x² y² ≤ r²则判定点落在圆内计数器m加 1最终p m / splitPoint是圆内点数占比由于占比 ≈ 圆面积 / 正方形面积 π / 4所以π ≈ p * 4。为何复杂度高从代码结构可以推断该方法的时间复杂度为 O(n)n即投点次数。蒙特卡洛方法的收敛速率遵循统计规律——误差约为1/√n这意味着想多得到一位有效数字投点量需要增大 100 倍。原文档称其为重心法从实现逻辑看其本质是**蒙特卡洛随机投点Monte Carlo**法随机性决定了它的收敛慢、结果不稳定每次运行数值都会波动这正是它复杂度高的根本原因。2. 复杂度低割圆术递归法liuHui02static double getNGonSideLength(double sideLength, int splitCounter) { if (splitCounter 0) { return sideLength; } double halfSide sideLength / 2; // 使用勾股定理勾股定理 double perpendicular Math.sqrt(Math.pow(circleRadius, 2) - Math.pow(halfSide, 2)); double excessRadius circleRadius - perpendicular; double splitSideLength Math.sqrt(Math.pow(excessRadius, 2) Math.pow(halfSide, 2)); return getNGonSideLength(splitSideLength, splitCounter - 1); } static int getNGonSideCount(int splitCount) { // 内接六边形 (6-gon) 开始 int hexagonSidesCount 6; // 在每次拆分迭代中我们制作 N 边形6 边形、12 边形、24 边形、48 边形等等。 return hexagonSidesCount * (splitCount 0 ? (int) Math.pow(2, splitCount) : 1); } public static double liuHui02(int splitCount) { double nGonSideLength getNGonSideLength(circleRadius, splitCount - 1); int nGonSideCount getNGonSideCount(splitCount - 1); double nGonPerimeter nGonSideLength * nGonSideCount; double approximateCircleArea (nGonPerimeter / 2) * circleRadius; return approximateCircleArea / Math.pow(circleRadius, 2); }三个方法的分工getNGonSideLength(sideLength, splitCounter)递归地使用勾股定理计算翻倍后的新边长。第一个参数是当前边长第二个参数是剩余拆分次数当splitCounter 0时递归终止返回边长。否则将边长减半用Math.sqrt依次求出弦心距perpendicular、半径超出量excessRadius再用勾股定理合成新边长splitSideLength然后携带新边长继续递归splitCounter - 1。getNGonSideCount(splitCount)计算迭代后的多边形边数。内置常量hexagonSidesCount 6表示内接六边形当splitCount 0时返回6 × 2^splitCount否则返回 6。这与每次拆分边数翻倍的几何事实完全对应。liuHui02(splitCount)主入口方法。以splitCount - 1为参数分别求得边长与边数计算周长nGonPerimeter 边长 × 边数再利用圆面积 ≈ 周长的一半 × 半径估算圆面积最后除以r²得到 π 的近似值半径circleRadius取 1 时即为圆面积本身。为何复杂度低从代码结构可以推断getNGonSideLength是深度为splitCount的线性递归整体时间复杂度为 O(k)k 为拆分次数。它每一次递归都让边数翻倍6 → 12 → 24 → 48…因此只需极少次迭代就能获得可观的精度——这就是割圆术与蒙特卡洛法的本质区别前者误差随迭代次数按指数收缩后者误差随采样量按平方根收缩。3. 收敛过程数值验证以半径r 1、六边形边长side 1起算按上述递推公式逐步迭代可以得到如下收敛过程可由 liuHui02 同款公式计算验证迭代次数边数边长π 近似值1120.51763809023.105828542240.26105238443.132628613480.13080625853.139350204960.06543816563.1410319551920.03272346333.1414524763840.01636227923.1415576177680.00818120813.14158389815360.00409061263.14159046可以看到第 4 次迭代96 边形即得到3.1410与刘徽当年九十六边形π ≈ 3.1416的成就完全吻合第 8 次迭代1536 边形已逼近3.14159。这正是割圆术低复杂度的直观证据——几何递推以指数级效率逼近 π。五、精度边界与工程启示1. 浮点精度的天花板需要说明的是上述数值基于double双精度浮点计算。从代码实现看getNGonSideLength中的excessRadius circleRadius - perpendicular是一个两个相近大数相减的操作随着迭代加深halfSide越来越小perpendicular越来越接近circleRadius相减会触发灾难性消去catastrophic cancellation有效数字逐步丢失。因此用double实现割圆术迭代到一定次数后精度不会再提升——这也是原文档作者电脑算不出多少位 π 值的真实原因瓶颈不在几何递推而在浮点表示本身。若需要更高精度需要改用BigDecimal或任意精度库重写平方根运算而不再适合直接用Math.sqrt。2. 两种实现的工程取舍维度liuHui01蒙特卡洛liuHui02割圆术时间复杂度O(n)n 为投点数O(k)k 为递归深度收敛速度误差 ~ 1/√n极慢误差按 2ⁿ 指数收缩极快结果确定性随机性每次运行结果不同确定性同一输入结果唯一对 CPU 的消耗大量随机数生成极易跑满 CPU轻量递归几乎无压力适用场景概率统计、图形采样类问题确定性数值逼近类问题从工程视角看liuHui02是用数学模型换计算量的典范——多边形的几何结构天然携带确定性信息远比盲目投点高效。这也呼应了小傅哥在 docs/md/algorithm/logic/math/math.md 中的观点有数学才有编程之美代码是对数学逻辑的具体实现有了数学支撑才让编程逻辑具有灵魂。六、总结割圆术虽诞生于公元 3 世纪但其核心思想在今天依然不过时递推建模把求 π转化为求边长递推用勾股定理串联每一次倍增收敛分析理解指数收敛 vs 平方根收敛的差异是选择算法方案的底层依据精度边界浮点表示的局限决定了任何数值算法的可用范围这也解释了为什么现代计算 π 需要专用算法与超算资源。阅读本文后你可以直接基于liuHui02的代码结构动手验证从 6 边形开始逐步增加到 96 边形、1536 边形亲手复现刘徽 1800 年前的计算精度并进一步观察double精度下的收敛上限——这正是把数学史变成程序能力的最佳起点。赞分享文档教程后端【免费下载链接】CodeGuide:books: 本代码库是作者小傅哥多年从事一线互联网 Java 开发的学习历程技术汇总旨在为大家提供一个清晰详细的学习教程侧重点更倾向编写Java核心内容。如果本仓库能为您提供帮助请给予支持(关注、点赞、分享)项目地址https://gitcode.com/gh_mirrors/code/CodeGuide点击查看免费下载相关推荐Apache Druid DataSketches HLL Sketch 模块基于 HLL 的近似基数去重计数实战指南Apache Druid DataSketches HLL Sketch 模块基于 HLL 的近似基数去重计数实战指南 Apache Druid 的 drui数据库OLAP大数据后端Nyströmformer 源码解析与实战指南基于 Nyström 采样的 O(n) 自注意力近似与 Transformers 实现Nyströmformer 源码解析与实战指南基于 Nyström 采样的 O n 自注意力近似与 Transformers 实现 导读 Nyströmfor人工智能深度学习机器学习预训练微调NLP计算机视觉语音多模态StarRocks ds_theta_count_distinct 详解基于 Apache DataSketches Theta Sketch 的高基数近似去重计数StarRocks ds_theta_count_distinct 详解基于 Apache DataSketches Theta Sketch 的高基数近似去数据库OLAP数据仓库大数据湖仓一体数据分析创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考
返回列表