Multiplication by a fixed scalar

When every entry of a vector is multiplied by the same scalar c, data for multiplying by c can be precomputed once and used for every entry. _nmod_vec_scalar_mul_nmod and _nmod_vec_scalar_addmul_nmod each have variants that differ in what they precompute and in their requirements on n, and choose among them from c, n and the length.

The variants#

Shoup multiplication needs one high and two low products per entry and no reduction step, against a full product and a two-word reduction for the generic code. It is usually the fastest choice but needs one spare bit in n. Montgomery multiplication handles moduli with the top bit set, where Shoup's method does not apply. Only _nmod_vec_scalar_mul_nmod has a _redc variant.

Choice of variant#

_nmod_vec_scalar_mul_nmod handles c = 0, c = 1 and c = n - 1 by zeroing, copying and negating. Otherwise:

• If n has FLINT_BITS bits, it uses _redc for odd n and length at least 8, and otherwise a generic loop without normalisation shifts.
• If n has fewer bits, it uses _shoup from length FLINT_MULMOD_SHOUP_THRESHOLD on, and _generic below.

_nmod_vec_scalar_addmul_nmod handles c = 0, c = 1 and c = n - 1 with no operation, _nmod_vec_add and _nmod_vec_sub. Otherwise it uses _shoup from length FLINT_MULMOD_SHOUP_THRESHOLD on when n has fewer than FLINT_BITS bits, and _generic in all other cases.

The threshold FLINT_MULMOD_SHOUP_THRESHOLD is set in flint-mparam.h for each target; on some recent x86-64 processors it is 0 (always use Shoup). The precomputation for Shoup's method costs one hardware division, which a short vector does not amortise.

Example#

#include <flint/flint.h>
#include <flint/nmod.h>
#include <flint/nmod_vec.h>

int main(void)
{
    nmod_t mod;
    ulong u[5] = { 1, 2, 3, 4, 5 };
    ulong v[5] = { 10, 20, 30, 40, 50 };
    ulong w[5], x[5], y[5];
    ulong c = 12345;
    int i;

    nmod_init(&mod, 1000003);

    /* w = c u + 3 v - v */
    _nmod_vec_scalar_mul_nmod(w, u, 5, c, mod);
    _nmod_vec_scalar_addmul_nmod(w, v, 5, 3, mod);
    _nmod_vec_sub(w, w, v, 5, mod);
    _nmod_vec_print_pretty(w, 5, mod);

    /* the variants agree; _shoup also accepts unreduced entries */
    _nmod_vec_scalar_mul_nmod_generic(x, v, 5, c, mod);
    _nmod_vec_scalar_mul_nmod_redc(y, v, 5, c, mod);     /* n is odd */
    flint_printf("generic = redc: %d\n", _nmod_vec_equal(x, y, 5));

    for (i = 0; i < 5; i++)
        y[i] = v[i] + 7 * mod.n;                         /* not reduced */
    _nmod_vec_scalar_mul_nmod_shoup(y, y, 5, c, mod);    /* n < 2^(FLINT_BITS - 1) */
    flint_printf("generic = shoup: %d\n", _nmod_vec_equal(x, y, 5));
    return 0;
}

<length-5 integer vector mod 1000003>
[  12365   24730   37095   49460   61825]
generic = redc: 1
generic = shoup: 1