18.8. Performance🔗

The packed representation exists for speed, so it is worth saying what the speed is. Two comparisons are recorded in reports/hex-gf2-performance.md.

Against the generic FpPoly 2 path inside Hex, on the same GF(2) coefficient inputs at n = 64, packed GCD runs in 14.1 ms against 1.41 s, and the Berlekamp-style Frobenius-column construction in 9.77 ms against 419 ms. That is roughly 100x and 43x: the packed long division is 64-bit XOR and shift on whole words, while the generic path pays per-bit ZMod64-wrapped arithmetic for every coefficient.

Against NTL's GF2X, the picture depends on where you look, and the honest summary is that Hex wins at small degree and loses at large. Multiplication crosses over near n = 512: below it Hex is ahead, at n = 2048 NTL spends about 4% of Hex's wall time on the same product. The reason is algorithmic and known — NTL switches to Karatsuba and then FFT multiplication, and the schoolbook packed-word loop here does not. Addition is not a useful comparison at all: NTL's measured time is dominated by marshaling across the process boundary at every rung, so those ratios describe the harness rather than the kernel.