FLINT3.7.0-dev
/
Overview

Integer arithmetic

This section describes how FLINT computes with multiprecision integers: the algorithms behind the fmpz functions and the limb-level routines of mpn_extras on which they are built, from schoolbook methods to fast Fourier transforms and Newton iteration. Multiplication comes first, since the cost of every other operation is measured in multiplications: division and square roots by Newton iteration cost a constant factor more, and GCDs, radix conversion and binary splitting a logarithmic factor more. FLINT uses GMP for part of this work (Toom–Cook multiplication in a middle range of sizes, GCDs, n-th roots, most modular exponentiation, radix conversion in a middle range of sizes and in bases other than 10) and its own code elsewhere; each page says which.

OverviewMultiplying integersHow FLINT multiplies integers of each size — its own assembly basecases, Karatsuba, GMP's Toom–Cook algorithms, and FFT multiplication with fft_small or Schönhage–Strassen — with the algorithms, their costs and the dispatch in flint_mpn_mul.

In this section#

OverviewMultiplying integersHow FLINT multiplies integers of each size — its own assembly basecases, Karatsuba, GMP's Toom–Cook algorithms, and FFT multiplication with fft_small or Schönhage–Strassen — with the algorithms, their costs and the dispatch in flint_mpn_mul.AlgorithmBasecase multiplication kernelsSchoolbook multiplication of short limb arrays by a table of straight-line routines, one for each pair of small sizes (assembly with two independent carry chains on x86-64 and ARM64, C elsewhere), and Karatsuba multiplication built on them.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.AlgorithmInteger division and Newton iterationEuclidean division of multiprecision integers by schoolbook division with a 3-by-2 inverse, Burnikel–Ziegler divide and conquer, and Newton iteration with the Karp–Markstein trick; exact division by 2-adic (Hensel) methods; division by a fixed divisor with a precomputed inverse; and square roots by the same techniques.AlgorithmInteger GCDGreatest common divisors of multiprecision integers by the binary algorithm, Lehmer's algorithm and the subquadratic half-GCD, in the matrix formulation shared with continued fractions; GMP's implementations behind fmpz_gcd and fmpz_xgcd, and FLINT's own half-GCD for continued fractions and rational reconstruction.AlgorithmRadix conversionConversion between binary and decimal (or any radix b^e) in quasi-linear time by divide and conquer with multiplications only, carrying out the arithmetic in the target radix.AlgorithmMultimodular reduction and Chinese remainderingConverting an integer to and from its residues modulo many word-size primes in quasi-linear time with a subproduct tree, using fractional cofactors so that Chinese remaindering needs no large inverses and no intermediate reductions.AlgorithmBinary splitting and product treesProducts of many integers by balanced product trees, sums of hypergeometric series by binary splitting, and simultaneous reduction and Chinese remaindering by product and remainder trees; how FLINT uses them for factorials, primorials, vector products, Chinese remaindering, radix conversion, constants and series.
Cite this page

The FLINT team, “Integer arithmetic,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/integers/index.html (generated 2026-10-20).