杂记 › 技术笔记 › 同一个数打两遍,最小公倍数成了 94906266.99999999:先乘后除撞上限的是中间量

同一个数打两遍,最小公倍数成了 94906266.99999999:先乘后除撞上限的是中间量

两路公交什么时候再次同时进站,公式只有一行

6 分钟一班和 8 分钟一班的两路车,同时发车后多久再次同时进站,是那道求最小公倍数的题,答案 24。通分、齿轮的齿、周期对齐用的是同一个式子 LCM(a, b) = |a × b| ÷ GCD(a, b)。输入 8, 12, 20 时过程行写着 |24 × 20| ÷ 4 = 480 ÷ 4 = 120:先把两个数整个乘出来,再除。

这一行就是源码第 146 行的 Math.abs(result * numbers[i]) / g,先乘后除。最小公倍数计算给的数对不对,卡的是这个中间量而不是结果:真正的 LCM 也许还能精确表示,a × b 已经先越界。

边界不是 9007199254740991,而是 9490 万

最大安全整数 9007199254740991(2^53-1)看着像输入上限,实测管的是中间量:1 ≤ a ≤ b ≤ 1000 的 500500 对全枚举失败 0 对;a 放宽到 2000、b 加到乘积越界为止,共 148001000 对,仍失败 0 对。所以条件是乘积形式,翻回输入就是两个数都不超过约 9490 万:94906265² = 9007199136250225 还在界内,94906266² = 9007199326062756 已越过去。

越界不等于算错:这段里 double 的行间距是 2,只有偶数能精确表示,GCD 吃掉舍掉的 1 就照样对。我在 [94906266, 94906366] 全枚举 5151 对(下界已证明),失真 1275 对、占 24.75%,第一个失败对是同一个数打两遍的 94906267, 94906267;窗口里 101 个等值对,偶数失败 0 个、奇数失败 50 个。

n 打两遍n² 的真值双精度 a × b乘积误差页面给出的 LCM
9490626690071993260627569007199326062756094906266
9490626790071995158752899007199515875288-194906266.99999999
9490626990071998955003619007199895500360-194906268.99999999

机理在最后一列:奇数的平方是奇数,被舍成相邻偶数(误差 1),再除以奇数 g = n 时 1 除不尽,商就成了带小数的「最小公倍数」。首个算成整数却错 1 的对是 94906267, 94906269,g = 1,偏差 1。

把除法挪到乘法前面,多救回 271 对

同一批 5151 对、同一个 g,只把除法提前成 (a / g) * b:两种写法都精确 3876 对,只有先除后乘精确 271 对,两种都不精确 1004 对,只有先乘后除精确 0 对。那 1004 对不是顺序问题:真 LCM 本身就大于 2^53-1,先除后乘只把条件放宽到「结果不越界」。

两种写法都精确 3876 对 只有先除后乘精确 271 对 两种写法都不精确 1004 对 只有先乘后除精确 0 对 条形按对数等比

图 1|5151 对穷举里两种写法的精确情况分类,失真 1275 对 = 1004 + 271,最后一格是 0 对。

取余次数:相邻斐波那契数要走 40 步

那个 g 来自第 97-100 行的迭代辗转相除 while (b !== 0),实测按余数条数算:gcd2(18, 12) 走 2 次,gcd2(12, 18) 要先换位置、走 3 次,顺序影响次数。最慢的是相邻斐波那契数,每步商都是 1、余数只削一层,102334155 配 165580141 要 40 步;这一对互质,LCM 就是乘积,代码给 16944503814015856、真值 16944503814015855。

(1, 1) 1 次 (18, 12) 2 次 (12, 18) 3 次 (94906266, 94906267) 3 次 (102334155, 165580141) 40 次

图 2|实测取余次数,条形按次数等比;最后一行是相邻斐波那契数,辗转相除的最坏情况。

一张卡片两副面孔,换个顺序换个数

大字走第 152 行的 toLocaleString()、过程行走字符串相加,同一个数两副面孔:输入 1073741824, 95367431640625 时大字展开成 102,400,000,000,000,000,000,000,过程行写成 1.024e+23。这条本身是精确的,2^30 与 5^20 互质;通分时可以直接看公分母(分数通分计算)。多个数按第 142-149 行严格左折叠,不去重也不排序,所以顺序在浮点上有效:94906267, 94906267, 3 的 6 个排列给出 284718801 与 6369051764850687,真值前者,按输入顺序的第一个排列恰好是错的。

输入端的静默改写,分解端的平方根

第 70 行是 parseInt(p, 10),非法输入不报错,只被截断或丢掉:4.9 变 4、12abc 剩 12,负数与 0 被第 71 行的 n > 0 滤掉。分隔符只认第 67 行的逗号与空白,于是 1,000, 2,000 被切成 1 和 2,LCM 显示 2,无提示;解析不足 2 个时第 138 行直接 return,结果区整个消失。个数也有天花板:124746 个能跑完,124747 个让第 179 行的 Math.max.apply 抛 RangeError。

分解是逐个试除,第 114 行条件 d * d <= num,代价按平方根长:999983 要 998 次,1000000007 要 31621 次,15 位的 999999999999989 要 31622775 次,模板里 0 处上限、0 处超时。两条实测路径真能把标签页钉住:100000000001, 99999999989 的 22 位结果写出来后卡在第 173 行分解它;309 位数字被读成 Infinity 后进死循环,wall=8013ms 一次 DOM 都没再写。

Q:为什么两个大数算出来的最小公倍数会带小数?

错在中间量不在结果。乘积一旦超过 9007199254740991 就被舍到相邻偶数、误差 1,接着除以 g,g 是奇数时 1 除不尽,界面上就出现 94906266.99999999。两个数都在 9490 万以内就没这个问题。

Q:输入小数、负数、千分位会怎样?

都不报错:小数被截断、负数与 0 被丢弃、1,000 被当成两个数,剩下的正整数不足 2 个时结果区直接不出现。要核对公因子,可以先用最大公因数计算跑一遍。

Q:质因数分解转圈是因为什么?

试除只跑到平方根且没有上限,页面还要在分解每个输入之外多分解一次 LCM 结果本身,代价由这一项主导。两个十几位的质数就足够让标签页一直转,输入到一半也一样——计算挂在每一次按键上。

📎 相关文章

把质量调到 100 再压一次,图片其实一个字节都没动 2026-10-21 后缀从最后一个点算起:LICENSE、.gitignore、archive.tar.gz 为什么会漏改 2026-10-21 批量建目录的脚本里,编号补零和 CON 这两个坑最容易被忽略 2026-10-21 同一句中文,UTF-8 存 12 字节、GBK 只存 8 字节:编码是怎么被判错的 2026-10-21 接口返回的 JSON 导成 CSV,Excel 里为什么少了一列 2026-10-21