FLINT3.7.0-dev
/

_flint_mpn_mulhigh_n, _flint_mpn_mulhigh_basecase, _flint_mpn_mulhigh_n_recursive, _flint_mpn_mulhigh_n_mulders, _flint_mpn_mulhigh_n_mul, _flint_mpn_mulhigh_n_naive

Synopsis#include <flint/mpn_extras.h>
mp_limb_t _flint_mpn_mulhigh_n(mp_ptr res, mp_srcptr u, mp_srcptr v, mp_size_t n)source
mp_limb_t _flint_mpn_mulhigh_basecase(mp_ptr res, mp_srcptr u, mp_srcptr v, mp_size_t n)source
mp_limb_t _flint_mpn_mulhigh_n_recursive(mp_ptr r, mp_srcptr x, mp_srcptr y, mp_size_t n)source
mp_limb_t _flint_mpn_mulhigh_n_mulders(mp_ptr res, mp_srcptr u, mp_srcptr v, mp_size_t n)source
mp_limb_t _flint_mpn_mulhigh_n_mul(mp_ptr res, mp_srcptr u, mp_srcptr v, mp_size_t n)source
mp_limb_t _flint_mpn_mulhigh_n_naive(mp_ptr rp, mp_srcptr up, mp_srcptr vp, mp_size_t n)source

The algorithms behind flint_mpn_mulhigh_n, with its interface.

  • _flint_mpn_mulhigh_n is the dispatcher used beyond the hard-coded sizes: the basecase up to FLINT_MPN_MULHIGH_MULDERS_CUTOFF (40) limbs, Mulders' algorithm up to FLINT_MPN_MULHIGH_FFT_SMALL_CUTOFF (with fft_small) or FLINT_MPN_MULHIGH_MUL_CUTOFF (2000), and above, a middle product with fft_small respectively a full product.
  • _flint_mpn_mulhigh_basecase is the quadratic algorithm (an assembly routine on x86-64 with ADX, which requires n \ge 6, and on ARM64, which requires n > 8). On x86-64 with ADX the basecase used by the dispatcher is _flint_mpn_mulhigh_n_recursive up to 22 limbs: it splits off a block handled by the fastest hard-coded routine (FLINT_MPN_MULHIGH_BEST_TAB_N limbs) and recurses.
  • _flint_mpn_mulhigh_n_mulders computes a rough high product with one extra limb using _flint_mpn_mulhigh_n_mulders_recursive.
  • _flint_mpn_mulhigh_n_mul computes the full product; its result is the exact truncation.
  • _flint_mpn_mulhigh_n_naive is a portable reference implementation of the basecase, against which the assembly routines are tested (they return identical results).
Cite this page

The FLINT team, “_flint_mpn_mulhigh_n, _flint_mpn_mulhigh_basecase, _flint_mpn_mulhigh_n_recursive, _flint_mpn_mulhigh_n_mulders, _flint_mpn_mulhigh_n_mul, _flint_mpn_mulhigh_n_naive (mpn_extras.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/mpn_extras/_flint_mpn_mulhigh_n.html (generated 2026-10-20).