雜記 › 技術筆記 › 它把餘數為 0 的那一行也打給你:GCD 過程展示頁的步數、摺疊順序與 29 步斐波那契

它把餘數為 0 的那一行也打給你:GCD 過程展示頁的步數、摺疊順序與 29 步斐波那契

一、三個數用頓號分開,結果只剩一個數

要算 48、36、60,我照中文習慣用頓號分開敲進輸入框,等到的是空白:結果區、過程區、因數區、統計區同時隱藏。

謎底在模板第 68 行的字元類別:split(/[,,\s]+/) 只有 3 個成員——半形逗號、全形逗號、JS 的 \s。換行、Tab、全形空格 U+3000 都切得開,但頓號 U+3001、分號、豎線、斜線、中文句號不在名單裡:"48、36、60" 整串被當成一個段,parseInt 撞到頓號就停,解析只剩 [48],後兩個數靜默消失。混用更陰,"12,18、24" 得到 [12, 18] 和 6,看起來像算對了。

二、非法段從不炸整批,它只是安靜地消失

第 72 行的 !isNaN(n) && n > 0 是唯一白名單,腳本裡 try 與 catch 各 0 次,壞段炸不了整批,只是自己消失:

輸入numbers頁面表現
"3.9,4.1"[3, 4]小數只截不進
"0x10,20"[20]第 71 行寫了 radix=10
"-12,18"[18]負數進不到演算法
"48,36"[]全形數字一個不認

繞過第 72 行、直接餵給第 111 行的 gcd2WithSteps 才看得到函式本體:(-12,-18) 返回 -6,全腳本沒有 Math.abs;(0,0) 是 0 步。這條分支在瀏覽器裡不可達。

三、多值是由左往右摺的,順序與零行都會改行數

頁面唯一在用的是第 111 行記步數的 gcd2WithSteps,第 101–108 行那個 gcd2 是死代碼,所以最大公因數計算的每一行除法都能數。

多值是嚴格左摺疊(第 126–136 行),不排序也不去重:gcdMulti([48,36,60,72]) 分 3 組共 6 步得 12,而 [60,48,36] 只要 4 步、[36,48,60] 要 5 步。差的那步來自第 115–117 行——只要 a < b,第一條必然寫成 a = b × 0 + a 這種 0 商交換行。第 117 行 push 無條件,餘數為 0 的收尾行照打,(65536,4096) 那 1 行除法也要佔 4 行。行數換算式:兩數時 = 步數 + 3,k 個數時 = 各組(步數 + 3)加 (k − 2) 個銜接行,實測 48,36,60 是 10 行、6 個數是 25 行。

版面是 48 = 36 × <span class="highlight">1</span> + 12,餘數為 0 就寫「+ 0」,不寫共幾步。

四、最壞輸入確實是相鄰斐波那契對,可頁面沒有步數欄

相鄰斐波那契對頂到最壞:F(31)=1346269 與 F(30)=832040 實測 29 個除法步、打出 32 行、過程 HTML 長 2488 字元;反序變 30 步 33 行。規律是步數 = 較大者下標 − 2,F(41)=102334155 與 F(40)=63245986 實測 38 步。步數與行數均為本機 Node v24 跑模板第 60–209 行的腳本口徑。

圖 1 步數對照上界 45F(41) F(40)38 步F(31) F(30)29 步同對反序30 步隨機 2000 對最大22 步隨機 2000 對平均12.134 步

同量級隨機對照(LCG seed=20261027,各 2000 對)最大 22 步 @(923408,1247609)、平均 12.134 步,少 7 步。拉梅那句「步數不超過較小者位數的 5 倍」在這份程式碼裡成立:limit=1000、1000000、1000000000 各抽 30000 對共 9 萬對,違例 0 對,最緊的 (458528519,627075196) 是 30 步對 9 位數、上界 45。可第 189–192 行統計欄固定 4 項、0 個步數欄位。

五、錯在第 1 位的是 parseInt,不是輾轉相除

腳本裡 BigInt 出現 0 次,第 71 行 parseInt 返回雙精度(上限 9007199254740991),取模跑在第 116 行的 Number 上;第 111 到 122 行的迴圈與 BigInt 真值逐步一致,誤差全在解析。

最刺眼的是 9007199254740993,9007199254740992:相鄰兩數摺成同一個,頁面顯示「9,007,199,254,740,992」而真值 1,差異從第 1 位就開始。再小一檔:9007199254740993,3 頁面給 1、真值 3;12345678901234567891,2 頁面給 2、真值 1,連輸入本身都被寫成 12345678901234567000。

六、把分頁跑死的是因數表,不是歐幾里得

同一條 20 位輸入,把耗時拆開分段計時:第 160 行 gcdMulti 只花 0.06 毫秒就得 gcd=2(2 步除法),第 181 行為每個輸入數呼叫的 getFactors 卻單獨花 35654 毫秒——第 141 行的上界 i * i <= n 迭代 3513641828 次,只給 96 個因數。整條鏈路同步阻塞 30798 毫秒,1e20 那條是 83505 毫秒,30 位輸入在 240000 毫秒內沒輸出就被 kill。

圖 2 耗時歸屬拆分輾轉相除 gcdMulti0.06 毫秒因數表 getFactors35654 毫秒整條 input 鏈路30798 毫秒1e20 那條輸入83505 毫秒30 位輸入240000 毫秒未返回

第 76 行末尾直接呼叫 calcGcd,代價落在每次按鍵之間;1e20 那條最終也只寫出 441 個因數。

七、規模崩潰點不可重現:124000 過、125000 拋

每多 1 個數固定多 4 行(行數 = 4n − 4):1000 個數 3996 行、328726 字元;100000 個數 399996 行、標籤區 3800000 字元、常駐記憶體 312 MB。崩潰點在第 191 行的 Math.max.apply(null, numbers):另開一支全新程序時,124000 個數還能寫出統計欄,125000 個數必拋 RangeError 且統計欄留空,而第 177 行過程區與第 186 行因數區那時已寫完,頁面停在「有答案、沒統計」的半渲染狀態;同一支程序連跑 5 次 200000 個數又全部通過。所以「最多支援 N 個數」在這頁站不住腳。

可信的是演算法核心:零行肯打給你,行數還能反推步數。不可信的是外面那層——分隔符、過濾與因數表都不兜底。

常見問題

Q:三個數用頓號分開為什麼只算了一個?

第 68 行只認半形逗號、全形逗號、空白這 3 個成員,頓號不在裡面;不足 2 個數時第 154–157 行只把 display 設成 none,頁面不解釋。

Q:頁面上有沒有算好的步數?

沒有,統計欄那 4 項裡不含步數;要步數只能去數過程區的行數,兩數時減 3。

Q:貼上一個二十位數為什麼就卡死了?

卡的是第 181 行那張因數表:它單獨花 35654 毫秒,而第 160 行的輾轉相除只要 0.06 毫秒。parseInt 還早把它摺成了 12345678901234567000。

📎 相關文章

171! 才溢出,23! 就已經算錯:階乘頁那句「0~1000 不會溢出」的實測邊界 2026-10-27 一個漢字只算 5 bits:密碼強度評估器的破解時間什麼時候變成宇宙壽命級別 2026-10-27 文字↔ASCII 裡的「ASCII」其實是 UTF-8:1 個漢字吐出 3 個數,無分隔檔 100% 回不去 2026-10-27 GIF 縮完尺寸只剩首格:一個檔名叫 .gif 的 PNG 檔案 2026-10-27 BMP 進、PNG 出:12342 位元組的位圖變成 281 位元組,檔名卻還寫著 .bmp 2026-10-27