Fifty seconds for half a megabyte: the optimisation that fixed the constant, not the order

A cryptography library had a bottleneck no test could see : encrypting half a megabyte took fifty seconds. Every test passed. They had been passing for months. The cause is a trap that keeps recurring: a correct, well-documented optimisation that fixes the constant and not the order — and whose comment, precisely because it is well written, convinces the reader the problem is already solved. What the code did Quipu renders encrypted data as a sequence of symbols. To do that it converts the whole message into a single huge integer and repeatedly divides it to extract digits, the same way you would convert a base-10 number to base 2 by hand. The code did not divide one digit at a time. It carried a sensible optimisation: divide by the largest power of the base that fits in a machine word, extracting nine digits per pass instead of one. The comment explaining it opened by saying that doing it one at a time would be quadratic , and then described the improvement. All true. And the result was still quadratic: extracting nine digits per pass divides the work by nine; it does not change how the work grows. That sentence — "doing it this way would be quadratic" — reads in the past tense, as if it described the previous state. It described the current one. The measurement, which is the only thing that says so Size Time Factor per doubling 64 KiB 0.79 s — 128 KiB 3.16 s ×4.0 256 KiB 12.6 s ×4.0 512 KiB 50.7 s ×4.0 Exactly four, three times running. That is textbook quadratic: every time the input doubles, the time quadruples. Extrapolating, ten megabytes would have cost about five and a half hours . And here is the point: a correctness test sees none of this . A slow algorithm produces exactly the same bytes as a fast one. The suite stayed green, and would have stayed green forever. The fix is two hundred years old Nothing had to be invented. Divide-and-conquer radix conversion is a classical algorithm: instead of peeling digits off one end, you split the number in half — div