8.7. Costs🔗

The fast algorithms are faster only for large enough inputs, and how large depends on the operation. These times were measured with the library's benchmark program, hexpolyfast_bench, on one core of a shared machine (chungus2) on 2026-10-05, using karatsubaPlan 32. Each time is the average over repeated calls with the same input, in a single run. The inputs are:

• products: two factors with n coefficients, which are integers of absolute value at most 51, stored as Int or as Rat;

• division: a polynomial with 2n + 1 coefficients divided by one with n + 1, over the field with 65537 elements;

• extended gcd: two polynomials of degree about n over the field with two elements;

• evaluation: a polynomial with n coefficients at n points, over the field with 65537 elements;

• Padé approximation: the [n/n] approximant of the series with coefficients 1 / (i + 1) over the field with 65537 elements.

The direct methods are the schoolbook product, long division, Euclid's algorithm, Horner's rule at each point, and, for the Padé approximant, Gauss–Jordan elimination on its linear equations.

Karatsuba multiplication is already faster than the schoolbook method at 64 coefficients. Division with a cached plan is as fast as long division at 64 coefficients and faster beyond, while one-shot division, which also computes the inverse, overtakes long division only between 1024 and 2048. The half-gcd algorithm and multipoint evaluation are still slower than Euclid's algorithm and Horner's rule at 4096, although the gap is closing as n grows. Building an evaluation plan for 4096 points takes a further 170 ms. Interpolation has no HexPoly counterpart. Recovering x³ - 7x + 11 from its values at 0, 1, …, 1023 over the field with 65537 elements takes 39 ms including building the plan, and 6 ms with a plan built in advance.

For full products of integer and prime-field polynomials, the plans of HexPolyZ and HexPolyFp can be much faster than karatsubaPlan. The Hex libraries use the fast algorithms only where they measured a gain. The finite-field and factorization libraries keep Euclidean division and gcd. HexHensel multiplies long lists of small linear factors with a product tree and ZPoly.fastPlan, and HexRationalFn divides with divModWith and karatsubaPlan 8.