雜記 › 技術筆記 › 同一個數打兩遍,最小公倍數成了 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 結果本身,代價由這一項主導。兩個十幾位的質數就足夠讓分頁一直轉,輸入到一半也一樣——計算掛在每一次按鍵上。

📎 相關文章

PNG 壓了三遍只減 426 位元組:無損壓縮的真實邊界 2026-10-22 WebP 轉 PNG 後體積漲了幾倍:什麼時候必須轉,怎麼把漲幅壓住 2026-10-22 截圖縮到四分之一,小字糊成一團的三種原因 2026-10-22 同樣裁 300×300,頭像為什麼總偏右下角半格 2026-10-22 按每月 1.7 倍預估 18 個月,腳本和表格為什麼給出兩個數 2026-10-22