教程文档示例工程【免费下载链接】website-archiveArchive of the Coding Train website (first version)项目地址https://gitcode.com/gh_mirrors/we/website-archive点击查看免费下载导读本文围绕 Coding TrainDaniel Shiffman的编程挑战第 161 期展开如何只靠随机数、最大公约数与互质概率估算出圆周率 π。核心思路是两个随机整数互质的概率恰好等于 (6/\pi^2)因此只要大量抽样并统计互质对的比例就能反推出 π。本文将结合 website-archive 仓库中 CC_161_pi_from_random 的完整 p5.js 源码与真实数据文件逐步拆解数学原理、欧几里得算法实现、数据切分细节和可视化逻辑让你读完后能独立复现、修改并验证这个经典的 π Day 实验。一、挑战概览从随机数到π 的估计在 161-pi-from-random.md 中这一期挑战被标注为video_number: 161发布于 2021 年 3 月 14 日π Day仓库目录为CC_161_pi_from_random。它包含两个 p5.js 变体变体语言仓库文件夹数据文件Estimating π from Random Numbersp5.jsfrom-randommilliondigits.txt100 万个随机数字Estimating π from Digits of πp5.jsfrom-pipi1000000.txtπ 的 100 万位小数两个变体的目标一致取一对整数判断它们是否互质co-prime用互质比例反推 π。区别仅仅在于随机数的来源——前者使用 RAND 公司著名的《A Million Random Digits with 100,000 Normal Deviates》随机数表后者则直接使用 π 自身的小数位这本身就是一个有趣的哲学问题用 π 的数字去估算 π等价于假设 π 的数字足够随机。原文档的章节时间线topics勾勒了视频的完整讲解路径什么是互质1:26→ 欧几里得算法4:21→ 求最大公约数示例8:40→ 编写gcd()函数9:55→ 载入随机数字12:23→ 用draw()驱动循环14:39→ 互质还是共因子16:13→ 如何估算 π17:44→ 估算实现18:50→ 用 π 的数字再试一次21:59→ 扩展思路22:54。下文将沿着这条主线展开。二、数学基础为什么互质概率能算出 π2.1 什么是互质co-prime两个整数互质意味着它们的最大公约数Greatest Common Divisor, GCD为 1即二者除 1 外没有公共因子。例如 8 和 9 互质而 6 和 9 不互质有公共因子 3。2.2 关键结论互质概率 (6/\pi^2)这是本期实验的数学基石从整数中均匀随机地取两个数它们互质的概率是 (6/\pi^2)约 0.6079。直觉理解如下对一个素数 (p)一个随机整数能被 (p) 整除的概率是 (1/p)所以两个随机整数同时被 (p) 整除的概率是 (1/p^2)即它们不被 (p) 同时整除的概率是 (1-1/p^2)。要互质就必须对所有素数都满足不同时被整除因此[ P(\text{coprime}) \prod_{p\ \text{prime}} \left(1-\frac{1}{p^2}\right) \frac{1}{\zeta(2)} \frac{6}{\pi^2} ]这里 (\zeta(2)\pi^2/6) 是欧拉在 1735 年解决的巴塞尔问题。原文档将这一背景列为参考资源Probability of Two Integers Being Coprime。2.3 从互质比例反推 π设抽样总对数为total其中互质对数为coprimeCount则[ \frac{coprimeCount}{total} \approx \frac{6}{\pi^2} \quad\Longrightarrow\quad \pi \approx \sqrt{\frac{6 \cdot total}{coprimeCount}} ]这正是仓库源码中那一行估计式的由来let pie sqrt((6 * total) / coprimeCount);需要强调的是这是一个统计估计单次抽样会有波动只有样本量足够大几十万对以上时结果才会逐渐收敛到 3.14159… 附近。三、欧几里得算法互质判定的实现要判定一对整数是否互质只需计算gcd(a, b)并检查是否为 1。欧几里得算法辗转相除法基于一条性质gcd(a, b) gcd(b, a % b)不断用余数替换较大的数直到余数为 0此时的除数就是最大公约数。from-random/sketch.js 中的递归实现如下function gcd(a, b) { if (b a) { [b, a] [a, b]; // 保证 a b } let r a % b; if (r 0) { return b; // 余数为 0b 即为最大公约数 } else { return gcd(b, r); // 否则递归gcd(a, b) gcd(b, a % b) } }要点解读第一步用 ES6 解构赋值[b, a] [a, b]交换两数确保a b避免a % b得到无意义的首轮结果递归终止条件当a % b 0时b整除a最大公约数就是b判定互质if (gcd(a, b) 1) { coprimeCount; }即gcd返回 1 时两数互质。由于本实验中的数值来自 5 位数字分组见下节a、b的取值范围是 1100000递归深度非常有限性能完全不是问题——draw()每帧要处理 500 对欧几里得算法的对数级收敛保证了这一点。四、数据准备100 万数字如何变成随机整数对4.1 两份真实数据文件仓库中提供了实验所需的完整数据milliondigits.txt约 100 万个随机数字源自 RAND 公司 1955 年出版的随机数表原文档将其列为背景资料。文件首部形如100973253376520135863467354876809590911739292749453754204805…pi1000000.txtπ 的 100 万位小数不含整数部分 3 和小数点首部为1415926535897932384626433832795028841971693993751058209749445923…这正是3.14159265…去掉3.之后的数字串。两份文件的大小都约 1MBpi1000000.txt为 1,000,000 个字符加一个换行符milliondigits.txt为 1,000,000 个字符的单行文本与百万位/百万个随机数字的描述吻合。4.2 用preload()载入数据p5.js 的preload()会在setup()之前执行适合同步加载外部文件。两个变体的写法一致let data; function preload() { data loadStrings(milliondigits.txt); // from-random 变体 // data loadStrings(pi1000000.txt); // from-pi 变体 }loadStrings()按行读取文本返回字符串数组由于数据文件是单行数字串data[0]就是整串数字。4.3setup()把数字串切成 5 位一组from-random/sketch.js 中的切分逻辑function setup() { createCanvas(400, 400); let digits data[0]; while (digits.length 0) { let num digits.slice(0, 5); digits digits.slice(5); // Original code was randomSequence.push(parseInt(num)); // JavaScript will default to reading number as base 8 if it begins with a 0 randomSequence.push(parseInt(num, 10)); } }这里有两个值得注意的工程细节每 5 位数字切分为一个整数100 万位数字 → 200,000 个整数每个整数取值范围 0000099999正好可以两两配对成 100,000 对parseInt(num, 10)显式指定十进制源码注释明确警告——如果某段数字以0开头例如07321旧版 JavaScript 的parseInt(07321)可能按八进制解析导致数值错误。第二个变体 from-pi/sketch.js 保留了不带进制参数的原始写法parseInt(num)这也正好呼应了原文档时间线中的Code! Lets load the random digits.一节所讲解的坑。五、draw()驱动的估算循环与实时可视化5.1 每帧处理 500 对from-random/sketch.js 的核心循环function draw() { for (let n 0; n 500; n) { let a randomSequence[index] 1; let b randomSequence[index 1] 1; // console.log(a,b); if (gcd(a, b) 1) { coprimeCount; } total; index 2; if (index randomSequence.length) { noLoop(); console.log(complete); break; } } let pie sqrt((6 * total) / coprimeCount); // ... 绘制部分 }设计要点加 1 偏移a randomSequence[index] 1把 099999 映射到 1100000避免出现 0若允许 0gcd(a, 0) a会污染互质统计一次取两数index每次递增 2从序列中依次取出相邻的两数构成一对分帧批处理draw()默认每秒约 60 帧每帧 500 对总共 100,000 对只需约 3.3 秒即可跑完同时保证画面实时刷新完成后停止index randomSequence.length时调用noLoop()并打印complete让估算值定格在最终结果上。5.2 实时显示与进度条from-random/sketch.js 的绘制逻辑let pie sqrt((6 * total) / coprimeCount); background(0); textAlign(CENTER, CENTER); textSize(64); fill(255); textFont(Courier); text(nf(pie, 1, 5), width / 2, height / 2); let w (width * index) / randomSequence.length; stroke(255); noFill(); rect(0, 10, width, 20); fill(255); rect(0, 10, w, 20);nf(pie, 1, 5)是 p5.js 的数字格式化函数把估计值格式化为整数部分至少 1 位、小数部分固定 5 位如3.14213避免长小数溢出画布顶部进度条用width * index / randomSequence.length反映已处理数据的比例让观众直观看到估算值随样本增加逐步收敛的过程——这正是原文档时间线中Code! Lets use draw() for our loop.与Code! Estimating π.两节的完整落地。六、变体二用 π 的数字估算 π第二个变体 from-pi 几乎与随机数版本完全一致唯一的数据层差异是function preload() { data loadStrings(pi1000000.txt); // 改用 π 的 100 万位小数 }其余逻辑切分、gcd、估算、绘制完全相同。这个变体的趣味点在于π 的小数位序列本身并非真随机但被认为是足够随机正态数猜想。因此用 π 的数字切分出的整数对其互质比例依然会收敛到 (6/\pi^2)从而估算出 π 本身——某种意义上这是用 π 证明 π。对比两个变体的完整实现唯一实质差异是 from-random/sketch.js 使用了parseInt(num, 10)而 from-pi/sketch.js 使用parseInt(num)其余代码逐行对应非常适合做对照学习。七、运行方式与结果验证7.1 如何运行两个变体都遵循 p5.js 的标准目录结构index.htmlsketch.js 数据文件。以 from-random/index.html 为例!DOCTYPE html html head script srchttps://cdn.jsdelivr.net/npm/p51.4.1/lib/p5.min.js/script meta charsetutf-8 / /head body script srcsketch.js/script /body /html运行方式克隆本仓库后直接用浏览器打开CodingChallenges/CC_161_pi_from_random/from-random/index.html或 from-pi 版本p5.js 通过 CDN版本 1.4.1加载loadStrings()会读取同目录下的数据文件页面中央实时显示不断收敛的 π 估计值顶部进度条走满后估算结束浏览器控制台输出complete。需要注意的前提该实现依赖 CDN 加载 p5.js 与本地数据文件的读取浏览器对file://协议下本地文本读取通常可用若要获得更稳定的运行环境可启动本地静态服务器后访问。7.2 预期结果100,000 对样本全部处理完毕后互质对数约 60,790即 (100000 \times 6/\pi^2) 附近估计值通常落在3.14 左右误差取决于随机波动若想逼近 3.14159 以上的精度需要更大的样本量例如把数据扩展到数百万对因为统计估计的标准差按 (\sqrt{N}) 量级衰减从源码结构可以推断from-pi变体由于数据完全确定每次运行会得到完全相同的互质计数与估计值而from-random变体基于固定的随机数字表同样可复现但体现的是伪随机序列下的统计行为。八、扩展思路与社区实践原文档在结尾的Ideas! Thanks for watching!一节中鼓励观众自行扩展仓库的 161-pi-from-random.md 也收录了 2021 年 π Day 的社区贡献代表性方向包括可视化演进把估算值随样本数的变化绘制成折线/动画直观展示收敛过程社区有PI estimate evolution类作品混合数据源如用量子随机数生成器原文档列出的参考方向之一产生的真随机数替换伪随机表比较不同随机源下的收敛表现与其他估算方法对比可与仓库内其他 π 相关挑战对照例如 CC_139 用碰撞次数估算 π、CC_140 用莱布尼茨级数计算 π、CC_141 Mandelbrot 与 π 等体会同一个 π 的不同数学面孔。值得一提的对照学习资源Stand-up Maths 的《Generating π from 1,000 random numbers》原文档在 videos 一节收录它将本实验规模缩小到仅 1,000 个随机数便于快速验证样本量越小波动越大的统计本质。结语本期挑战用一个极其优雅的数学恒等式互质概率 (6/\pi^2)串起了数论欧几里得算法、概率统计大数定律与可视化编程p5.js 的分帧处理与实时绘制。通过阅读 from-random/sketch.js 与 from-pi/sketch.js 两份逐行对应的实现你不仅掌握了gcd的递归写法、parseInt的进制陷阱与draw()批处理技巧更能真正理解统计模拟验证数学恒等式这一通用方法——它同样适用于蒙特卡洛求积分、随机游走模拟等更广泛的场景。赞分享教程文档示例工程【免费下载链接】website-archiveArchive of the Coding Train website (first version)项目地址https://gitcode.com/gh_mirrors/we/website-archive点击查看免费下载相关推荐Coding Train 编码挑战 070.1用欧几里得距离计算用户相似度得分搭建电影推荐引擎的第一步Coding Train 编码挑战 070.1用欧几里得距离计算用户相似度得分搭建电影推荐引擎的第一步 本篇文章对应 Coding Train 网站归档仓库教程文档示例工程数论算法终极指南欧几里得与扩展欧几里得算法在CLRS中的完整解析数论算法终极指南欧几里得与扩展欧几里得算法在CLRS中的完整解析 想要深入理解数论算法的核心精髓吗欧几里得算法和扩展欧几里得算法作为计算机科学中最重要的数论文档教程示例工程CLRS 31.2 数论算法详解欧几里得算法与扩展欧几里得算法的原理、习题与源码实现CLRS 31.2 数论算法详解欧几里得算法与扩展欧几里得算法的原理、习题与源码实现 《算法导论》CLRS第 31 章系统讲解数论算法其中 31.2 节文档教程示例工程上一篇Flet 地图 Marker 标记控件完全指南在地图上精确定位任意内容下一篇逆向解密Navicat试用重置从技术实现到决策框架的思维升级创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
