fft_small.h – FFT modulo word-size primes¶

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

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.

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(mp_ptr r1, mp_srcptr i1, mp_size_t n1, mp_srcptr i2, mp_size_t 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(mp_ptr res, slong zl, slong zh, mp_srcptr a, slong an, mp_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.