nmod_vec.h – vectors over integers mod n (word-size n)

Memory management

nn_ptr _nmod_vec_init(slong len)

Returns a vector of the given length. The entries are not necessarily zero.

void _nmod_vec_clear(nn_ptr vec)

Frees the memory used by the given vector.

Random functions

void _nmod_vec_randtest(nn_ptr vec, flint_rand_t state, slong len, nmod_t mod)

Sets vec to a random vector of the given length with entries reduced modulo mod.n.

Basic manipulation and comparison

void _nmod_vec_set(nn_ptr res, nn_srcptr vec, slong len)

Copies len entries from the vector vec to res.

void _nmod_vec_zero(nn_ptr vec, slong len)

Zeros the given vector of the given length.

void _nmod_vec_swap(nn_ptr a, nn_ptr b, slong length)

Swaps the vectors a and b of length \(n\) by actually swapping the entries.

void _nmod_vec_reduce(nn_ptr res, nn_srcptr vec, slong len, nmod_t mod)

Reduces the entries of (vec, len) modulo mod.n and set res to the result.

flint_bitcnt_t _nmod_vec_max_bits(nn_srcptr vec, slong len)

Returns the maximum number of bits of any entry in the vector.

int _nmod_vec_equal(nn_srcptr vec, nn_srcptr vec2, slong len)

Returns \(1\) if (vec, len) is equal to (vec2, len), otherwise returns \(0\).

Printing

void _nmod_vec_print_pretty(nn_srcptr vec, slong len, nmod_t mod)

Pretty-prints vec to stdout. A header is printed followed by the vector enclosed in brackets. Each entry is right-aligned to the width of the modulus written in decimal, and the entries are separated by spaces. For example:

<length-12 integer vector mod 197>
[ 33 181 107  61  32  11  80 138  34 171  86 156]
int _nmod_vec_fprint_pretty(FILE *file, nn_srcptr vec, slong len, nmod_t mod)

Same as _nmod_vec_print_pretty but printing to file.

int _nmod_vec_print(nn_srcptr vec, slong len, nmod_t mod)

Currently, same as _nmod_vec_print_pretty.

int _nmod_vec_fprint(FILE *f, nn_srcptr vec, slong len, nmod_t mod)

Currently, same as _nmod_vec_fprint_pretty.

Arithmetic operations

void _nmod_vec_add(nn_ptr res, nn_srcptr vec1, nn_srcptr vec2, slong len, nmod_t mod)

Sets (res, len) to the sum of (vec1, len) and (vec2, len).

void _nmod_vec_sub(nn_ptr res, nn_srcptr vec1, nn_srcptr vec2, slong len, nmod_t mod)

Sets (res, len) to the difference of (vec1, len) and (vec2, len).

void _nmod_vec_neg(nn_ptr res, nn_srcptr vec, slong len, nmod_t mod)

Sets (res, len) to the negation of (vec, len).

void _nmod_vec_scalar_mul_nmod(nn_ptr res, nn_srcptr vec, slong len, ulong c, nmod_t mod)

Sets (res, len) to (vec, len) multiplied by \(c\). The element \(c\) and all elements of vec are assumed to be less than mod.n.

void _nmod_vec_scalar_mul_nmod_shoup(nn_ptr res, nn_srcptr vec, slong len, ulong c, nmod_t mod)

Sets (res, len) to (vec, len) multiplied by \(c\) using n_mulmod_shoup(). mod.n should be less than \(2^{\mathtt{FLINT\_BITS} - 1}\), and \(c\) should be less than mod.n. There is no constraint on elements of vec.

void _nmod_vec_scalar_addmul_nmod(nn_ptr res, nn_srcptr vec, slong len, ulong c, nmod_t mod)

Adds (vec, len) times \(c\) to the vector (res, len). The element \(c\) and all elements of vec are assumed to be less than mod.n.

Dot products

Dot products functions and macros rely on several implementations, depending on the length of this dot product and on the underlying modulus. What implementations will be called is determined via _nmod_vec_dot_params, which returns a dot_params_t element which can then be used as input to the dot product routines.

The efficiency of the different approaches range roughly as follows, from faster to slower, on 64 bit machines. In all cases, modular reduction is only performed at the very end of the computation.

  • moduli up to \(1515531528\) (about \(2^{30.5}\)): implemented via single limb integer multiplication, using explicit vectorization if supported (current support is for AVX2);

  • moduli that are a power of \(2\) up to \(2^{32}\): same efficiency as the above case;

  • moduli that are a power of \(2\) between \(2^{33}\) and \(2^{63}\): efficiency between that of the above case and that of the below one (depending on the machine and on automatic vectorization);

  • other moduli up to \(2^{32}\): implemented via single limb integer multiplication combined with accumulation in two limbs;

  • moduli more than \(2^{32}\), unreduced dot product fits in two limbs: implemented via two limbs integer multiplication, with a final modular reduction;

  • unreduced dot product fits in three limbs, moduli up to about \(2^{62.5}\): implemented via two limbs integer multiplication, with intermediate accumulation of sub-products in two limbs, and overall accumulation in three limbs;

  • unreduced dot product fits in three limbs, other moduli: implemented via two limbs integer multiplication, with accumulation in three limbs.

type dot_params_t
dot_params_t _nmod_vec_dot_params(slong len, nmod_t mod)

Returns a dot_params_t element. This element can be used as input for the dot product macros and functions that require it, for any dot product of vector with entries reduced modulo mod.n and whose length is less than or equal to len.

Internals, subject to change: its field method indicates the method that will be used to compute a dot product of this length len when working with the given mod. Its field pow2_precomp is set to 2**DOT_SPLIT_BITS % mod.n if method == _DOT2_SPLIT, and to \(0\) otherwise.

ulong _nmod_vec_dot(nn_srcptr vec1, nn_srcptr vec2, slong len, nmod_t mod, dot_params_t params)

Returns the dot product of (vec1, len) and (vec2, len). The input params has type dot_params_t and must have been computed via _nmod_vec_dot_params with the specified mod and with a length greater than or equal to len.

ulong _nmod_vec_dot_rev(nn_srcptr vec1, nn_srcptr vec2, slong len, nmod_t mod, dot_params_t params)

The same as _nmod_vec_dot, but reverses vec2.

ulong _nmod_vec_dot_ptr(nn_srcptr vec1, const nn_ptr *vec2, slong offset, slong len, nmod_t mod, dot_params_t params)

Returns the dot product of (vec1, len) and the values at vec2[i][offset]. The input params has type dot_params_t and must have been computed via _nmod_vec_dot_params with the specified mod and with a length greater than or equal to len.

NMOD_VEC_DOT(res, i, len, expr1, expr2, mod, params)

Effectively performs the computation:

res = 0;
for (i = 0; i < len; i++)
    res += (expr1) * (expr2);

but with the arithmetic performed modulo mod. The input params has type dot_params_t and must have been computed via _nmod_vec_dot_params with the specified mod and with a length greater than or equal to len.

nmod.h has to be included in order for this macro to work (order of inclusions does not matter).

int _nmod_vec_dot_bound_limbs(slong len, nmod_t mod)

Returns the number of limbs (0, 1, 2 or 3) needed to represent the unreduced dot product of two vectors of length len having entries modulo mod.n, assuming that len is nonnegative and that mod.n is nonzero. The computed bound is tight. In other words, this function returns the precise limb size of len times (mod.n - 1)**2.

int _nmod_vec_dot_bound_limbs_from_params(slong len, nmod_t mod, dot_params_t params)

Same specification as _nmod_vec_dot_bound_limbs, but uses the additional input params to reduce the amount of computations; for correctness params must have been computed for the specified len and mod.