High and low products
#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)sourceSets to an approximation of and returns an approximation of limb of the product. Together they form a lower bound for that is wrong by a few units of the returned limb at most. Requires . The output may alias an input (see High products).
mp_limb_t flint_mpn_sqrhigh_n(mp_ptr res, mp_srcptr u, mp_size_t n)sourceThe square with the contract of flint_mpn_mulhigh_n.
mp_limb_t flint_mpn_mulhigh(mp_ptr res, mp_srcptr x, mp_size_t xn, mp_srcptr y, mp_size_t yn, mp_size_t n)sourcemp_limb_t flint_mpn_sqrhigh(mp_ptr res, mp_srcptr x, mp_size_t xn, mp_size_t n)sourceGeneral high products: the top limbs of the product (resp. ) of operands of any lengths, written to , and the limb just below them, returned. With the limb count of the product and , the -limb number satisfies FLINT_MPN_MULHIGH_GUARD_ERR_BOUND(n) (likewise FLINT_MPN_SQRHIGH_GUARD_ERR_BOUND(n)). The product is zero padded above if it is shorter than limbs (then exact, with ). Operands longer than limbs are truncated internally, the leading cross term of the dropped limbs being added back, so the cost is that of a product of operands of at most limbs. res may be one of the operands. For this is flint_mpn_mulhigh_n; see High products of any shape for the other shapes.
mp_limb_t flint_mpn_mullow_n(mp_ptr res, mp_srcptr u, mp_srcptr v, mp_size_t n)sourceSets to and returns limb of the product, that is, (this extra limb may be removed from the interface in the future). Requires ; res must not alias u.
void flint_mpn_mul_or_mullow_n(mp_ptr res, mp_srcptr u, mp_srcptr v, mp_size_t n)sourceWrites to the low limbs of res. The output must have room for limbs: the high limbs may be used as scratch space, or the whole product may be written when this is fastest.
void flint_mpn_mul_or_mulhigh_n(mp_ptr res, mp_srcptr u, mp_srcptr v, mp_size_t n)sourceWrites a high product (with the error of flint_mpn_mulhigh_n) as limbs to res + n - 1; the low limbs of the -limb output may be used as scratch space, or the full product may be written.
Many algorithms need only part of a product. Newton iteration for the reciprocal or the square root needs the top half of a product (or the middle part, when the low part is known to cancel); floating-point multiplication needs the top limbs of the product of two mantissas; Hensel division and 2-adic arithmetic need the bottom half. A short product computes such a part in less time than the full product: about half the time for quadratic multiplication, and a fraction between and 1 for Karatsuba and Toom–Cook multiplication. The descriptions below state precisely what the functions compute; the algorithms and the proofs of the error bounds are on the algorithm page.
AlgorithmHigh, low and middle products of integersComputing only the low half, an approximation of the high half, or an arbitrary window of the limbs of an integer product, with hard-coded kernels, Mulders' recursive short products and proved error bounds.Low products#
The low product of two -limb integers is well defined, and flint_mpn_mullow_n computes it exactly. The function also returns limb of the product, , which comes almost for free from the carries; flint_mpn_mul_or_mullow_n stores the same limbs in an output of limbs, which lets it compute the full product when that is the fastest method (from FLINT_MPN_MULHIGH_MUL_CUTOFF limbs without fft_small) or use the high half as scratch space.
High products#
The top limbs of a -limb product depend on all the partial products through the carries, and cannot be computed exactly faster than the full product in the worst case. A high product therefore computes an approximation. We use three notions [HZ2011]:
- a rough high product sums enough partial products to produce limbs of which the top are essentially correct, the lowest one having an error of units;
- a precise high product sums one more diagonal of partial products and produces limbs, the top being essentially correct and the lowest one having an error of units;
- the exact high product is .
flint_mpn_mulhigh_n and flint_mpn_sqrhigh_n compute precise high products: the limbs written to res and the returned limb form an -limb number with
The result is never too large, so is either or one less, and it is the exact value unless , since only then can the missing amount carry into the high limbs. For random inputs this almost never happens, so in practice one knows the exact top limbs without further work; when it does happen, the exact value can be found from a low product, as _flint_mpn_mulhigh_known_low does. Above FLINT_MPN_MULHIGH_MUL_CUTOFF limbs (without fft_small) the full product is computed and the result is exact.
More precisely, the deficit is at most FLINT_MPN_MULHIGH_N_GUARD_ERR_BOUND(n) for (zero for , where the kernels are exact). All backends accumulate every partial-product limb landing in columns and above; the dropped low halves of the products on the diagonal contribute less than units and the diagonals below less than , and a careful count gives a dropped amount below units, so the integer deficit is at most . This is sharp: the inputs , attain . The same bound FLINT_MPN_SQRHIGH_N_GUARD_ERR_BOUND(n) holds for flint_mpn_sqrhigh_n.
For floating-point arithmetic, flint_mpn_mulhigh_n_normalised and flint_mpn_sqrhigh_n_normalised also shift the result left by one bit when necessary so that the top bit of res[n-1] is set, returning the guard limb (shifted along) in m1 and the shift (0 or 1) in m2, so that the value is in units of . The inputs must have their top bits set. The shift doubles the deficit and can add one unit, giving the bounds FLINT_MPN_MULHIGH_N_NORMALISED_GUARD_ERR_BOUND(n) and FLINT_MPN_SQRHIGH_N_NORMALISED_GUARD_ERR_BOUND(n) .
All the high products (flint_mpn_mulhigh_n, flint_mpn_sqrhigh_n, flint_mpn_mulhigh, flint_mpn_sqrhigh and their normalised variants) allow the output to be one of the operands (the same pointer; partial overlap is not supported). The assembly kernels read their operands into registers, Mulders' algorithm works on a scratch buffer and the FFT transforms both operands before writing; the basecase routines, the C wrappers for 10 to 13 limbs on x86-64 and the unbalanced paths of the general products copy an aliased operand to scratch first.
High products of any shape#
Floating-point multiplication needs the top limbs of the product of mantissas of any lengths and , with set by the precision; the dot products need the same with the guard limb as data. flint_mpn_mulhigh and flint_mpn_sqrhigh compute this directly, with the deficit of the guard limb at most FLINT_MPN_MULHIGH_GUARD_ERR_BOUND(n) for every shape, so that callers no longer truncate, pad or pick a method themselves. The shapes reduce as follows.
- Operands longer than limbs are truncated to their top limbs. Dropping the low limbs of loses , up to units of the guard limb, of which the dominant part, the high half of the product of the limb just below the cut with the top limb of , is added back; what remains is below 3 units per truncated operand.
- :
flint_mpn_mulhigh_n(deficit at most ). - , or nearly the whole product wanted: the full product, since a full product with its own kernel followed by a copy beats any split there (the normalised variants use the normalised kernel on one operand padded by one or two limbs from , where its in-register shift wins over the full product and a shift).
- Both operands at least
FLINT_MPN_MULHIGH_FFT_SMALL_CUTOFFlimbs: the window of the product throughfft_small, with its two lowest limbs diverted to a separate buffer (the lowest absorbs the carry deficit of the window, below units of it, the next is the guard limb), so the output is written in place without a larger temporary. One operand in that range and the other below it: the full product, which the FFT computes faster than any split. - , or from : both operands zero padded below to limbs for
flint_mpn_mulhigh_n, which computes the same limbs of the product with the same deficit (thresholds measured on Zen 3; on an architecture whose high products save less of the full product, 7/8 would also be right at larger ). - : with , the full product lands exactly on the output and the balanced high product of is added to it.
- Both operands shorter than and not nearly balanced: the full product (splitting off high products does not pay in the Karatsuba range).
Adding the truncation remainder to the deficit of the balanced products gives a dropped amount below , hence the integer bound for and 5 for ; the macro states . Squares follow the same scheme with flint_mpn_sqrhigh_n, the cross term of a truncation counted twice, and a full square where the product case would split.
Middle products#
The windowed middle product flint_mpn_mulmid generalises both: it computes any range of limbs of a product of operands of any lengths, as a lower approximation with a deficit of less than units of its lowest limb, exact for . For -limb operands, the low product is the window and the high product is (up to the error bound) the window ; flint_mpn_mulmid calls flint_mpn_mullow_n for windows of the former shape and flint_mpn_mulhigh for every window reaching the top of the product. The balanced middle product of a -limb and an -limb operand (the window ), which is what a Newton step for the reciprocal needs, can be computed in the time of an product by the transposition principle [HQZ2004]; FLINT has it from GMP (flint_mpn_mulmid_n, where available) and, for large operands, from fft_small, which computes such a window as a transposed product of the length of the shorter operand and the window (Middle products by transposed small-prime FFTs), or with a cyclic convolution.
Choice of algorithm#
On x86-64 with ADX, high products of up to 13 limbs, square high products of up to 8 limbs and low products of up to 8 limbs are hard-coded assembly routines (on ARM64, high products and square high products up to 8 limbs). Beyond, high products use a quadratic basecase up to 40 limbs, Mulders' recursive algorithm up to FLINT_MPN_MULHIGH_FFT_SMALL_CUTOFF (500 limbs by default), and above, a middle product computed with fft_small; low products use the basecase up to 50 limbs, then Mulders' algorithm and fft_small in the same way. Without fft_small, the last step is a full product from 2000 limbs.
Example#
The high product of two 30-limb numbers, checked against the full product:
#include <gmp.h>
#include <flint/flint.h>
#include <flint/mpn_extras.h>
#define N 30
int main(void)
{
flint_rand_t state;
mp_limb_t u[N], v[N], full[2 * N], hi[N + 1], lo[N];
mp_limb_t diff[N + 1];
int i, ok_bound = 1, ok_low = 1;
flint_rand_init(state);
for (i = 0; i < 1000; i++)
{
flint_mpn_rrandom(u, state, N);
flint_mpn_rrandom(v, state, N);
flint_mpn_mul_n(full, u, v, N);
/* hi[0] is the returned limb, hi[1..N] the high limbs */
hi[0] = flint_mpn_mulhigh_n(hi + 1, u, v, N);
/* 0 <= floor(uv / B^(N-1)) - h < 2N */
if (mpn_cmp(full + N - 1, hi, N + 1) < 0)
ok_bound = 0;
mpn_sub_n(diff, full + N - 1, hi, N + 1);
if (!flint_mpn_zero_p(diff + 1, N) || diff[0] >= 2 * N)
ok_bound = 0;
/* the low product and its extra limb are exact */
if (flint_mpn_mullow_n(lo, u, v, N) != full[N]
|| mpn_cmp(lo, full, N) != 0)
ok_low = 0;
}
flint_printf("high product within bound: %d\n", ok_bound);
flint_printf("low product exact: %d\n", ok_low);
flint_rand_clear(state);
return 0;
}high product within bound: 1 low product exact: 1
References#
- [HZ2011] D. Harvey and P. Zimmermann, "Short division of long integers" (2011), Proceedings of the 20th Symposium on Computer Arithmetic (ARITH-20), July 25-27, 2011, pages 7-14. https://web.maths.unsw.edu.au/~davidharvey/research/shortdiv.pdf
- [HQZ2004] G. Hanrot, M. Quercia and P. Zimmermann, "The middle product algorithm I. Speeding up the division and square root of power series", Applicable Algebra in Engineering, Communication and Computing 14:6 (2004), 415–438
The FLINT team, “High and low products (mpn_extras.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/mpn_extras/mulhigh.html (generated 2026-11-20).
@misc{flint-doc-mpn-extras-mulhigh,
author = {{The FLINT team}},
title = {{High and low products (mpn\_extras.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/mpn_extras/mulhigh.html},
note = {Generated 2026-11-20}
}