FLINT3.7.0-dev
/
Overview

Generic algorithms

FLINT's generic rings framework gr lets one implementation of an algorithm run over every ring, from \mathbb{Z}/n\mathbb{Z} to power series over complex balls, while the type-specific modules keep their speed by overriding the critical operations. The sections below describe the design decisions behind the framework and the guarantees that generic algorithms rely on. The design is described in detail by Johansson [Joh2025gr]; the sections below follow the current source.

The algorithms themselves (polynomial multiplication, GCDs, linear algebra, series) are described in their own groups, which start from the generic version: see Polynomial arithmetic over generic rings and its specialisations and Linear algebra over generic rings and its specialisations.

In this section#

OverviewThe design of generic ringsAn overview of the generic rings framework: run-time ring objects with method tables, headerless elements, explicit status codes and three-valued predicates, and how these choices make generic code both rigorous and fast.AlgorithmContexts, method tables and specialisationHow rings and elements are represented, how a generic call is dispatched through the method table, the three levels of operations with their defaults, specialised parametric types, and why contexts are cheap to create.AlgorithmInexact elements and truth valuesThe enclosure semantics that make ball arithmetic, power series with error terms and exact real numbers rigorous in generic code: inclusion-preserving operations, three-valued predicates, and weak normalisation of polynomials.AlgorithmDomain errors and unable errorsThe meaning of the status codes GR_DOMAIN and GR_UNABLE, how statuses compose, why there are no junk values, how algorithms use the distinction for fallback strategies, and dynamic evaluation in rings that pretend to be fields.AlgorithmRandomised testing of ring axiomsHow ring implementations are tested by checking algebraic identities on random elements from skewed distributions, why such tests stay valid for inexact rings, and how generic algorithms are tested over many rings at once.AlgorithmGeneric poweringBinary exponentiation and the sliding window method as implemented for any ring, with operation counts, and when each is preferable.

References#

Cite this page

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