nmod_geometric_progression_init, _nmod_geometric_progression_init_function

The precomputation takes $O(\mathit{len})$ operations and space for at most $11 \mathit{len}$ coefficients: $3 \mathit{len}$ for evaluation, $3 \mathit{len}$ for interpolation and $6 \mathit{len}$ for extrapolation, of which $\mathit{len}$ are shared with interpolation. The constraints on $r$ are those of the section introduction; evaluation alone (function = 1 or 9) only needs $r$ invertible.

If bit 3 is set, _nmod_geometric_progression_init_fft is called with all three bounds equal to len. It stores the fft_small transforms of the polynomials that the selected functionalities multiply by, for those functionalities whose largest product would use fft_small, so that a product with a stored transform costs two transforms instead of three. The products of evaluation and extrapolation are middle products with the fixed polynomial $v$ as the long operand; for them the stored data are the images of $v$ through the transposed inverse transform (_mul_precomp_init_tr), and each product is a transposed product (_nmod_poly_mul_tr_precomp) with transforms of length $v_n$ rounded up to a multiple of 256, where $v_n = 2 \mathit{len} - 1$ (evaluation) or $\mathit{len} - 1$ (extrapolation), instead of a power of two; see Transposed FFT. Interpolation stores the forward transform of its series (_mul_precomp_init). A call uses the stored data only where it is cheaper than the product without them. The bit is ignored without fft_small. Each stored transform takes $\mathit{np} \cdot 2^d$ doubles, where $\mathit{np}$ is the number of primes fft_small needs for the modulus and $2^d$ is the smallest power of two at least $2 \mathit{len} - 1$ (evaluation, interpolation) or at least $\mathit{len} - 1$ (each of the two transforms for extrapolation).

@misc{flint-doc-nmod-poly-nmod-geometric-progression-init,
  author       = {{The FLINT team}},
  title        = {{nmod\_geometric\_progression\_init, \_nmod\_geometric\_progression\_init\_function (nmod\_poly.h)}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/nmod_poly/nmod_geometric_progression_init.html},
  note         = {Generated 2026-11-02}
}