nmod_vec.h – vectors over integers mod n (wordsize n)¶
Memory management¶
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 modulomod.n
.
Basic manipulation and comparison¶

void _nmod_vec_set(nn_ptr res, nn_srcptr vec, slong len)¶
Copies
len
entries from the vectorvec
tores
.

void _nmod_vec_swap(nn_ptr a, nn_ptr b, slong length)¶
Swaps the vectors
a
andb
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)
modulomod.n
and setres
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.
Printing¶

void _nmod_vec_print_pretty(nn_srcptr vec, slong len, nmod_t mod)¶
Prettyprints
vec
tostdout
. A header is printed followed by the vector enclosed in brackets. Each entry is rightaligned to the width of the modulus written in decimal, and the entries are separated by spaces. For example:<length12 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 tofile
.
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 ofvec
are assumed to be less thanmod.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\) usingn_mulmod_shoup()
.mod.n
should be less than \(2^{\mathtt{FLINT\_BITS}  1}\), and \(c\) should be less thanmod.n
. There is no constraint on elements ofvec
.
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 subproducts 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 modulomod.n
and whose length is less than or equal tolen
.Internals, subject to change: its field
method
indicates the method that will be used to compute a dot product of this lengthlen
when working with the givenmod
. Its fieldpow2_precomp
is set to2**DOT_SPLIT_BITS % mod.n
ifmethod == _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 inputparams
has typedot_params_t
and must have been computed via_nmod_vec_dot_params
with the specifiedmod
and with a length greater than or equal tolen
.

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

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 atvec2[i][offset]
. The inputparams
has typedot_params_t
and must have been computed via_nmod_vec_dot_params
with the specifiedmod
and with a length greater than or equal tolen
.

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 inputparams
has typedot_params_t
and must have been computed via_nmod_vec_dot_params
with the specifiedmod
and with a length greater than or equal tolen
.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 modulomod.n
, assuming thatlen
is nonnegative and thatmod.n
is nonzero. The computed bound is tight. In other words, this function returns the precise limb size oflen
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 inputparams
to reduce the amount of computations; for correctnessparams
must have been computed for the specifiedlen
andmod
.