Representation and arithmetic of rational functions

An fmpz_poly_q_t represents f \in \mathbb{Q}(x) as a quotient a/b of integer polynomials with \gcd(a, b) = 1 in \mathbb{Z}[x] and b having positive leading coefficient. Any f has exactly one such representation: clearing denominators of a representation over \mathbb{Q}[x] gives one over \mathbb{Z}[x], and two coprime representations a/b = a'/b' satisfy a b' = a' b, so b \mid b' and b' \mid b by Gauss's lemma, hence b' = \pm b. Since the gcd in \mathbb{Z}[x] includes the content, (2x + 2)/(4x) is not canonical, while (x + 1)/(2x) is.

Canonical forms make equality testing a comparison of coefficients, but reducing a quotient costs a polynomial gcd in \mathbb{Z}[x], which is much more expensive than a product. The arithmetic functions therefore never reduce a full product. They use Henrici's algorithms [Hen1956], which exploit the coprimality of the inputs to cancel common factors before multiplying.

Henrici's algorithms#

Let a/b and c/d be canonical.

So a sum costs one gcd of the denominators and one gcd of t with the (usually small) g, and a product two gcds of polynomials of the size of the inputs, instead of a gcd of the full numerator and denominator. When the denominators are coprime, which is the common case, no cancellation happens at all. fmpz_poly_q_add, fmpz_poly_q_sub, fmpz_poly_q_mul and fmpz_poly_q_div implement these formulas, with shortcuts for zero operands, for denominators equal to 1 and for constant denominators, where the arithmetic of fmpq_poly is used. The derivative is computed with a similar saving: (a/b)' = (a' b_1 - a b'/d)/(b b_1) with d = \gcd(b, b') and b_1 = b/d, whose numerator and denominator can only share a constant factor [Hor1972].

Working with numerators and denominators#

fmpz_poly_q_numref and fmpz_poly_q_denref give access to the two fmpz_poly_structs, so any fmpz_poly function can be used to build a rational function, after which fmpz_poly_q_canonicalise restores the canonical form. Strings in the format of fmpz_poly_q_set_str are an alternative for small inputs.

#include <flint/flint.h>
#include <flint/fmpq.h>
#include <flint/fmpz_poly.h>
#include <flint/fmpz_poly_q.h>

int main(void)
{
    fmpz_poly_q_t f, g, h;
    fmpq_t a, v;

    fmpz_poly_q_init(f);
    fmpz_poly_q_init(g);
    fmpz_poly_q_init(h);
    fmpq_init(a);
    fmpq_init(v);

    /* f = (2x^2 - 2)/(4x^2 + 4x), built directly, then canonicalised */
    fmpz_poly_set_str(fmpz_poly_q_numref(f), "3  -2 0 2");
    fmpz_poly_set_str(fmpz_poly_q_denref(f), "3  0 4 4");
    fmpz_poly_q_canonicalise(f);
    flint_printf("f = "); fmpz_poly_q_print_pretty(f, "x");
    flint_printf("  ("); fmpz_poly_q_print(f); flint_printf(")\n");

    fmpz_poly_q_set_str(g, "2  1 3/1  2");          /* (3x + 1)/2 */
    fmpz_poly_q_mul(h, f, g);
    flint_printf("f g = "); fmpz_poly_q_print_pretty(h, "x"); flint_printf("\n");
    fmpz_poly_q_add(h, f, g);
    flint_printf("f + g = "); fmpz_poly_q_print_pretty(h, "x"); flint_printf("\n");
    fmpz_poly_q_derivative(h, f);
    flint_printf("f' = "); fmpz_poly_q_print_pretty(h, "x"); flint_printf("\n");

    fmpq_set_si(a, 1, 3);
    if (fmpz_poly_q_evaluate_fmpq(v, f, a) == 0)
    {
        flint_printf("f(1/3) = "); fmpq_print(v); flint_printf("\n");
    }
    fmpq_set_si(a, 0, 1);
    flint_printf("f(0) defined: %d\n", fmpz_poly_q_evaluate_fmpq(v, f, a) == 0);

    fmpz_poly_q_clear(f);
    fmpz_poly_q_clear(g);
    fmpz_poly_q_clear(h);
    fmpq_clear(a);
    fmpq_clear(v);
    return 0;
}

f = (x-1)/(2*x)  (2  -1 1/2  0 2)
f g = (3*x^2-2*x-1)/(4*x)
f + g = (3*x^2+2*x-1)/(2*x)
f' = 1/(2*x^2)
f(1/3) = -1
f(0) defined: 0

The common factor 2(x + 1) of the numerator and denominator of f is removed by fmpz_poly_q_canonicalise. In f + g the denominators 2x and 2 have the gcd g = 2, and since the numerator 3x^2 + 2x - 1 is coprime to 2 in \mathbb{Z}[x], nothing more cancels.