FLINT3.7.0-dev

radix_mul_1

Synopsis#include <flint/radix.h>
ulong radix_mul_1(nn_ptr res, nn_srcptr a, slong n, ulong c, const radix_t radix)source

Sets (res,n)(\mathit{res}, n) to ac mod Bnac \bmod B^n and returns the carry ⌊ac/Bn⌋\lfloor ac / B^n \rfloor. Requires n≥1n \ge 1 and c<Bc < B.

When B2B^2 does not fit a word, each product is divided by BB on its own, aic=qiB+ria_i c = q_i B + r_i with qi≤B−2q_i \le B - 2, and limb ii of the result is ri+qi−1r_i + q_{i-1} plus a carry of 0 or 1 from limb i−1i - 1, with one conditional subtraction of BB. The divisions are independent, so that only additions and comparisons remain on the carry chain. They are Barrett steps (NMOD_DIVREM2_BOUNDED, Two words below a bound) for B<2FLINT_BITS−2B < 2^{\mathtt{FLINT\_BITS} - 2}, and 2/1 divisions with a precomputed inverse otherwise.

Cite this page

The FLINT team, “radix_mul_1 (radix.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/radix/radix_mul_1.html (generated 2026-11-20).