Notes › Tech Notes › The GCD page prints the zero-remainder row too: step counts, fold order, and the 29-step Fibonacci worst case

The GCD page prints the zero-remainder row too: step counts, fold order, and the 29-step Fibonacci worst case

1. Three numbers split by ideographic commas, one number left

I wanted the GCD of 48, 36, 60, so I typed them the way Chinese lists items, with an ideographic comma between each pair. What came back was blank: result area, process area, factor area and statistics area all hidden at the same time.

The answer is the character class on line 68 of the template: split(/[,,\s]+/) has only 3 members, a half-width comma, a full-width comma, and JavaScript \s. Newlines, Tab and the full-width space U+3000 all cut cleanly, but the ideographic comma U+3001, semicolons, vertical bars, slashes and the Chinese full stop are not on the list. That mark, 、, is the ordinary list separator of Chinese prose, used where English would write a comma, so it is exactly what a careful Chinese typist reaches for: "48、36、60" is taken as one single token, parseInt stops the moment it strikes the mark, the parse ends as [48], and the last two numbers disappear without a word. Mixing separators is subtler, because "12,18、24" yields [12, 18] plus 6, which looks like an answer.

2. A bad token never breaks the batch, it only disappears quietly

The guard !isNaN(n) && n > 0 on line 72 is the only whitelist. The script holds try 0 times and catch 0 times, so a broken token cannot bring the batch down; it simply removes itself:

InputnumbersWhat the page shows
"3.9,4.1"[3, 4]Decimals are truncated, never rounded
"0x10,20"[20]Line 71 pins radix=10
"-12,18"[18]Negatives never reach the algorithm
"48,36"[]Full-width digits are all refused

Bypass line 72 and feed the pair straight to gcd2WithSteps on line 111, and the function body finally shows itself: (-12,-18) returns -6 and there is no Math.abs anywhere in the script, while (0,0) is 0 steps. That branch is unreachable in a browser.

3. Multi-value input folds left to right, and both order and zero rows move the row count

The only routine the page uses is gcd2WithSteps on line 111, the one that records steps; the gcd2 on lines 101–108 is dead code, which is why every division row of the greatest common divisor tool can be counted by hand.

Multi-value input is a strict left fold (lines 126–136) with no sorting and no deduplication: gcdMulti([48,36,60,72]) spends 3 groups and 6 steps to reach 12, whereas [60,48,36] needs only 4 steps and [36,48,60] needs 5. The step that separates the two comes from lines 115–117: as soon as a < b, the very first row is necessarily a swap row with a zero quotient, written out as a = b × 0 + a. The push on line 117 is unconditional, so the closing row whose remainder is 0 is printed too, and (65536,4096), one division row, still occupies 4 rows. The row arithmetic: for a pair it is steps + 3, for k numbers it is each group (steps + 3) plus (k − 2) joining rows, measured at 10 rows for 48,36,60 and 25 rows for 6 numbers.

The layout is 48 = 36 × <span class="highlight">1</span> + 12; when the remainder is 0 it writes "+ 0", and it never writes how many steps the run took.

4. The worst input really is an adjacent Fibonacci pair, but the page carries no step field

Adjacent Fibonacci pairs sit at the worst case: F(31)=1346269 with F(30)=832040 measured 29 division steps, printed 32 rows, and produced process HTML 2488 characters long; reverse them and it becomes 30 steps and 33 rows. The rule is steps = index of the larger entry − 2, and F(41)=102334155 with F(40)=63245986 measured 38 steps. Every step count and row count here is the reading of a Node v24 script that runs lines 60–209 of the template on this machine.

Fig. 1 step countslimit 45F(41) F(40)38 stepsF(31) F(30)29 stepsReversed pair30 stepsRandom 2000 max22 stepsRandom 2000 mean12.134 steps

The same-magnitude random control (LCG seed=20261027, 2000 pairs per band) peaked at 22 steps @(923408,1247609) and averaged 12.134 steps, 7 steps short of the Fibonacci pair. Lamé's sentence, that the step count never exceeds 5 times the digit count of the smaller number, does hold for this code: drawing 30000 pairs at limit=1000, 1000000 and 1000000000 makes 90,000 pairs with 0 violations, and the tightest case (458528519,627075196) is 30 steps against 9 digits, a limit of 45. Yet lines 189–192 fix the statistics bar at 4 fields and 0 step fields.

5. What gets the first digit wrong is parseInt, not Euclid

BigInt appears 0 times in the script. The parseInt on line 71 returns a double precision number whose safe integer ceiling is 9007199254740991, and the modulo runs on the Number at line 116; the loop from line 111 to 122 agrees with BigInt truth step by step, so the whole error sits in parsing.

The most glaring case is 9007199254740993,9007199254740992: two neighbours fold into one and the same value, the page prints "9,007,199,254,740,992" while the true gcd is 1, and the divergence starts at the very first digit. One notch smaller: 9007199254740993,3 gives 1 on the page against a true 3; 12345678901234567891,2 gives 2 against a true 1, and the input itself is rewritten as 12345678901234567000.

6. What freezes the tab is the factor table, not Euclid

Take one and the same 20-digit input and weigh the cost apart: gcdMulti on line 160 spends only 0.06 ms to reach gcd=2 (2 division steps), while the getFactors call that line 181 makes for each input number spends 35654 ms on its own — the bound i * i <= n on line 141 iterates 3513641828 times and hands back only 96 factors. The whole chain blocks synchronously for 30798 ms, the 1e20 case for 83505 ms, and a 30-digit input was killed within 240000 ms without writing any output.

Fig. 2 cost by stageEuclid gcdMulti0.06 msFactor list getFactors35654 msWhole input chain30798 msThe 1e20 input83505 ms30-digit input240000 ms, no return

The tail of line 76 calls calcGcd directly, so the price is paid between keystrokes; and the 1e20 case, when it does finish, writes only 441 factors.

7. The scale cliff is not reproducible: 124000 passes, 125000 throws

Every extra number adds a fixed 4 rows (rows = 4n − 4): 1000 numbers give 3996 rows and 328726 characters, 100000 numbers give 399996 rows, a 3800000 character label area and 312 MB resident memory. The cliff is Math.max.apply(null, numbers) on line 191: in a fresh process 124000 numbers still write out the statistics bar, 125000 numbers always throw RangeError and leave that bar empty, and yet the process area on line 177 and the factor area on line 186 had already been written by then, so the page stops in a half rendered state that has an answer and no statistics; running 200000 numbers five times in one and the same process passes every time. So a promise about how many numbers are supported does not hold on this page.

The Euclid core is trustworthy: the zero row is printed for you, and the row count can be turned back into a step count. The layer around it is not, because separators, filtering and the factor table all fail without a fallback.

FAQ

Q: Why did three numbers written with ideographic commas compute only one of them?

Line 68 recognises only 3 members, a half-width comma, a full-width comma and whitespace, and the ideographic comma is not among them; once fewer than 2 numbers survive, lines 154–157 only set display to none and nothing on the page explains why.

Q: Is there a step count computed on the page anywhere?

No. The 4 items in the statistics bar do not contain steps, so to get steps you count the rows of the process area and subtract 3 for a pair.

Q: Why does pasting one twenty-digit number freeze the page?

What hangs is the factor table on line 181: it spends 35654 ms by itself, while the Euclid loop on line 160 needs only 0.06 ms. And parseInt had already folded that number into 12345678901234567000 long before.

📎 Related articles

Factorial page says 0 to 1000 cannot overflow: Number loses exactness at 23! and only overflows at 171! 2026-10-27 A Single CJK Character Is Worth 5 bits: When Crack Time Turns Into Age of the Universe 2026-10-27 The ASCII in text-to-ASCII is really UTF-8: one Han character prints three numbers, and 100% cannot be reversed 2026-10-27 Resizing a GIF Keeps Only the First Frame: a PNG File Named .gif 2026-10-27 A BMP Goes In, a PNG Comes Out: 12342 Bytes Become 281, but the File Is Still Named .bmp 2026-10-27