FLINT3.7.0-dev
/
Module · 42 functions

fmpz_poly_q.h

#include <flint/fmpz_poly_q.h>

This module implements arithmetic in the field \mathbb{Q}(x) of rational functions. An element is an fmpz_poly_q_t, stored as a quotient of two integer polynomials of type fmpz_poly_t in a canonical form: numerator and denominator are coprime in \mathbb{Z}[x] and the denominator has positive leading coefficient. Every function except fmpz_poly_q_canonicalise assumes that its inputs are canonical and returns a canonical result. Sums, products and quotients are computed with Henrici's algorithms [Hen1956], which keep the intermediate polynomials small by taking gcds of the factors before multiplying, and derivatives with a variant of the algorithm of Horowitz [Hor1972]; the guide Representation and arithmetic of rational functions explains these algorithms and shows how to work with the numerator and denominator directly.

For multivariate rational functions see fmpz_mpoly_q; for polynomials with rational coefficients, fmpq_poly.

Guides#

GuideRepresentation and arithmetic of rational functionsThe canonical form of an fmpz_poly_q_t, how Henrici's algorithms produce canonical sums and products with small gcds, and how to build a rational function from its numerator and denominator.

Types and canonical form#

A rational function over \mathbb{Q}. The structure has two fields num and den, pointers to separately allocated fmpz_poly_structs holding the numerator and the denominator. An fmpz_poly_q_t is an array of one fmpz_poly_q_struct, so it is passed by reference.

  • A rational function is canonical if its denominator is nonzero with positive leading coefficient and the numerator and denominator are coprime in \mathbb{Z}[x], which includes that their contents are coprime. The zero function is 0/1. This representation is unique.
  • All functions allow aliasing between their inputs and outputs. Two distinct fmpz_poly_q_t must not share their numerator or denominator objects.

Pointers (fmpz_poly_struct *) to the numerator and the denominator of op, which can be passed to any fmpz_poly function. If they are modified, the rational function must be brought back into canonical form with fmpz_poly_q_canonicalise.

Brings rop into canonical form by dividing the numerator and the denominator by their gcd in \mathbb{Z}[x] and making the leading coefficient of the denominator positive. The denominator must be nonzero; a zero denominator causes an exception (FLINT_ERROR).

Returns whether op is in canonical form.

Memory management#

Initialises rop as the zero function 0/1, allocating its numerator and denominator.

Frees the memory used by rop.

Assignment and basic operations#

Sets rop to op.

Sets rop to the constant function op.

Swaps op1 and op2 efficiently, by exchanging the pointers to the numerators and the denominators.

Set rop to 0 or 1.

Sets rop to -\mathit{op}.

Sets rop to 1/\mathit{op}, by exchanging numerator and denominator and fixing the sign. Raises an exception (FLINT_ERROR) if op is zero.

Randomisation#

Set poly to a random rational function, the canonical form of a/b with a a random polynomial of length at most len1 and coefficients of at most bits1 bits (fmpz_poly_randtest) and b a random nonzero polynomial of length at most len2 and at most bits2 bits. In the _not_zero version a is nonzero as well. Lengths and bit sizes less than 1 are replaced by 1 where a nonzero polynomial is needed.

Comparison#

Return whether op is 0, respectively 1.

Returns whether op1 and op2 are equal. Since the canonical form is unique, this compares numerators and denominators.

Addition and subtraction#

Set rop to \mathit{op1} + \mathit{op2}, respectively \mathit{op1} - \mathit{op2}, by Henrici's algorithm: with g the gcd of the denominators, only \gcd(\text{numerator}, g) has to be cancelled.

Set rop to \mathit{rop} + \mathit{op}, respectively \mathit{rop} - \mathit{op}. fmpz_poly_q_add and fmpz_poly_q_sub call these when the output is aliased with the first input.

Set rop to \mathit{rop} + \mathit{op1} \cdot \mathit{op2}, respectively \mathit{rop} - \mathit{op1} \cdot \mathit{op2}, using a temporary for the product.

Scalar multiplication and division#

Set rop to x \cdot \mathit{op}.

Set rop to \mathit{op} / x. A zero x raises an exception (FLINT_DIVZERO).

Multiplication and division#

Sets rop to \mathit{op1} \cdot \mathit{op2}. Writing \mathit{op1} = a/b and \mathit{op2} = c/d, Henrici's algorithm cancels \gcd(a, d) and \gcd(c, b) before multiplying, which gives the canonical result directly.

Sets rop to \mathit{op1} / \mathit{op2}, computed like the product with \mathit{op2} inverted. A zero op2 raises an exception (FLINT_DIVZERO).

Powering#

Sets rop to \mathit{op}^{\mathit{exp}}, by raising the numerator and the denominator to the power exp. For exp = 0 the result is 1, also when op is zero.

Derivative#

Sets rop to the derivative of op.

More

Evaluation#

If the denominator of f does not vanish at the rational number a, sets rop to f(a) and returns 0. Otherwise returns a nonzero value and leaves rop unchanged.

Input and output#

The string format is based on that of fmpz_poly_get_str: a polynomial a_0 + a_1 x + \cdots + a_n x^n is written as "n+1 a_0 a_1 ... a_n", with two spaces after the length, and the zero polynomial as "0". A rational function with numerator and denominator strings num and den is written as num/den, or as num alone if the denominator is 1. The pretty format uses fmpz_poly_get_str_pretty for both parts and puts parentheses around nonconstant ones, for example (3*t+1)/2. These functions are intended for debugging and small inputs, not as fast parsers.

int fmpz_poly_q_set_str(fmpz_poly_q_t rop, const char * s)

Sets rop to the rational function described by s, in the format above, and canonicalises it. Returns 0 on success and a nonzero value if s is not valid, in which case the value of rop is unspecified. A denominator string that describes the zero polynomial raises an exception.

char * fmpz_poly_q_get_str_pretty(const fmpz_poly_q_t op, const char * x)

Return the string representation of op, in the plain format or in the pretty format with the variable name x. The string is allocated with flint_malloc and must be freed with flint_free.

int fmpz_poly_q_print_pretty(const fmpz_poly_q_t op, const char * x)

Print the plain or the pretty representation of op to standard output, and return 1.

References#

  • [Hen1956] Peter Henrici : "A Subroutine for Computations with Rational Numbers" J. ACM (1956), https://doi.org/10.1145/320815.320818
  • [Hor1972] Ellis Horowitz : "Algorithms for Rational Function Arithmetic Operations" Annual ACM Symposium on Theory of Computing: Proceedings of the Fourth Annual ACM Symposium on Theory of Computing (Denver) (1972), https://doi.org/10.1145/800152.804903
Cite this page

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