FLINT3.7.0-dev
/

nmod_geometric_progression_init, _nmod_geometric_progression_init_function

Synopsis#include <flint/nmod_poly.h>
void nmod_geometric_progression_init(nmod_geometric_progression_t G, ulong r, slong len, nmod_t mod)source
void _nmod_geometric_progression_init_function(nmod_geometric_progression_t G, ulong r, slong len, nmod_t mod, ulong function)source

Initialise G for the points 1, r^2, \ldots, r^{2(\mathit{len}-1)}. len must be at least the number of points and at least the length of the polynomials used. nmod_geometric_progression_init prepares evaluation, interpolation and extrapolation; the second function only the functionalities selected by the bits of function: bit 0 evaluation, bit 1 interpolation, bit 2 extrapolation, and bit 3 stored transforms.

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).

Cite this page

The FLINT team, “nmod_geometric_progression_init, _nmod_geometric_progression_init_function (nmod_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/nmod_poly/nmod_geometric_progression_init.html (generated 2026-10-20).