2.8. Costs🔗

Multiplication uses the schoolbook method, about n²/2 multiplications of coefficients at precision n. It needs only addition and multiplication in R, so it is the same code for every coefficient ring. With bounded Newton steps, the inverse, square root, logarithm and exponential each cost a constant number of multiplications at precision n, so O(n²) operations on coefficients. Composition costs O(√n) multiplications plus O(n²) coefficient operations, so O(n^2.5) in all, and reversion costs about as much as a composition. Over ℚ the coefficients themselves grow: the coefficients of exp x have denominators k!.

The report reports/hex-truncated-series-performance.md measures each operation on one core of a shared machine. A product of two series of precision 4096 with integer coefficients from 1 to 101 takes 0.10 s, and 1.7 s with rational coefficients drawn from the same range of integers.

Newton's method is not the fastest way to invert a series when multiplication is schoolbook. The direct recurrence bₖ = -u Σⱼ<ₖ aₖ₋ⱼ bⱼ takes n²/2 coefficient multiplications against about 4n²/3, and when inverting 1 - x over ℚ at precision 4096 the recurrence is 2.7 times as fast. Newton's method is used because it turns a fast multiplication into a fast inverse: HexPolyFast runs the same iteration with its fast polynomial multiplication to divide polynomials, and proves the result equal to invOfUnit. For composition, Brent and Kung's algorithm is 12 times as fast as Horner's rule at precision 512, and Newton reversion is 5 times as fast as Lagrange's formula there.

FLINT's series functions over ℚ, which use fast multiplication, are 14 to 350 times as fast at the precisions n in this table, where the column Hex gives the time taken by this library: