兩路公車什麼時候再次同時進站,公式只有一行
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 |
|---|---|---|---|---|
| 94906266 | 9007199326062756 | 9007199326062756 | 0 | 94906266 |
| 94906267 | 9007199515875289 | 9007199515875288 | -1 | 94906266.99999999 |
| 94906269 | 9007199895500361 | 9007199895500360 | -1 | 94906268.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,先除後乘只把條件放寬到「結果不越界」。
圖 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。
圖 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 結果本身,代價由這一項主導。兩個十幾位的質數就足夠讓分頁一直轉,輸入到一半也一樣——計算掛在每一次按鍵上。