fft_small.h – FFT modulo word-size primes¶

This module currently requires building FLINT with support for AVX2 or NEON instructions.

The truncated FFT routines used internally by this module follow the approach described by van der Hoeven in [vdH2004].

Integer multiplication¶

type mpn_ctx_struct¶
type mpn_ctx_t¶: Context object for multiplications allowing non-FFT moduli. The structure contains FFT context objects for multiple FFT primes (currently 8) together with tables for Chinese remaindering.

void mpn_ctx_init(mpn_ctx_t R, ulong p)¶: Initialize multiplication context object with initial prime p. Usually p is a constant provided by get_default_mpn_ctx().

void mpn_ctx_clear(mpn_ctx_t R)¶: Free memory allocated by the context object.

mpn_ctx_struct *get_default_mpn_ctx(void)¶: Return a pointer to a cached thread-local context object used by default for multiplications. Calling flint_cleanup() or flint_cleanup_master() frees the cache.

void mpn_ctx_mpn_mul(mpn_ctx_t R, ulong *r1, const ulong *i1, ulong n1, const ulong *i2, ulong n2)¶
void mpn_mul_default_mpn_ctx(nn_ptr r1, nn_srcptr i1, slong n1, nn_srcptr i2, slong n2)¶: Writes to r1 the product of the integers (i1, n1) and (i2, n2). Assumes that \(n_1 \ge n_2 \ge 1\), respectively using a given context object R or the default thread-local object.

void _nmod_poly_mul_mid_mpn_ctx(ulong *z, ulong zl, ulong zh, const ulong *a, ulong an, const ulong *b, ulong bn, nmod_t mod, mpn_ctx_t R)¶
void _nmod_poly_mul_mid_default_mpn_ctx(nn_ptr res, slong zl, slong zh, nn_srcptr a, slong an, nn_srcptr b, slong bn, nmod_t mod)¶: Writes to z the middle product containing coefficients in the range \([zl, zh)\) of the product of the polynomials (a, an) and (b, bn), respectively using a given context object R or the default thread-local object. Assumes that \(an \ge bn \ge 1\).

int _fmpz_poly_mul_mid_mpn_ctx(fmpz *z, ulong zl, ulong zh, const fmpz *a, ulong an, const fmpz *b, ulong bn, mpn_ctx_t R)¶
int _fmpz_poly_mul_mid_default_mpn_ctx(fmpz *z, ulong zl, ulong zh, const fmpz *a, ulong an, const fmpz *b, ulong bn)¶: Like the nmod functions. Performs the multiplication and returns 1 if there are sufficiently many primes R to compute the result; otherwise returns 0 without touching the output.

void _nmod_poly_divrem_mpn_ctx(ulong *q, ulong *r, const ulong *a, ulong an, const ulong *b, ulong bn, nmod_t mod, mpn_ctx_t R)¶: Polynomial division with remainder.

void _mul_precomp_init(mul_precomp_struct *M, const ulong *b, ulong bn, ulong btrunc, ulong depth, nmod_t mod, mpn_ctx_t R)¶
void _mul_precomp_clear(mul_precomp_struct *M)¶: Represents (b, bn) in transformed form for preconditioned multiplication.

int _nmod_poly_mul_mid_precomp(ulong *z, ulong zl, ulong zh, const ulong *a, ulong an, mul_precomp_struct *M, nmod_t mod, mpn_ctx_t R)¶: Polynomial multiplication given a precomputed transform M. Returns 1 if successful, 0 if the precomputed transform is too short.

void _nmod_poly_divrem_precomp_init(nmod_poly_divrem_precomp_struct *M, const ulong *b, ulong bn, ulong Bn, nmod_t mod, mpn_ctx_t R)¶
void _nmod_poly_divrem_precomp_clear(nmod_poly_divrem_precomp_struct *M)¶: Represents (b, bn) and its inverse in transformed form for preconditioned multiplication.

int _nmod_poly_divrem_precomp(ulong *q, ulong *r, const ulong *a, ulong an, nmod_poly_divrem_precomp_struct *M, nmod_t mod, mpn_ctx_t R)¶: Polynomial multiplication given a precomputed transform M. Returns 1 if successful, 0 if the precomputed transform is too short.