FLINT3.7.0-dev
/

_gr_poly_compose_series, gr_poly_compose_series, _gr_poly_compose_series_horner, gr_poly_compose_series_horner, _gr_poly_compose_series_brent_kung, gr_poly_compose_series_brent_kung, _gr_poly_compose_series_divconquer, gr_poly_compose_series_divconquer, _gr_poly_compose_series_kinoshita_li, gr_poly_compose_series_kinoshita_li

Synopsis#include <flint/gr_poly.h>
int _gr_poly_compose_series(gr_ptr res, gr_srcptr poly1, slong len1, gr_srcptr poly2, slong len2, slong n, gr_ctx_t ctx)source
int gr_poly_compose_series(gr_poly_t res, const gr_poly_t poly1, const gr_poly_t poly2, slong n, gr_ctx_t ctx)source
int _gr_poly_compose_series_horner(gr_ptr res, gr_srcptr poly1, slong len1, gr_srcptr poly2, slong len2, slong n, gr_ctx_t ctx)source
int gr_poly_compose_series_horner(gr_poly_t res, const gr_poly_t poly1, const gr_poly_t poly2, slong n, gr_ctx_t ctx)source
int _gr_poly_compose_series_brent_kung(gr_ptr res, gr_srcptr poly1, slong len1, gr_srcptr poly2, slong len2, slong n, gr_ctx_t ctx)source
int gr_poly_compose_series_brent_kung(gr_poly_t res, const gr_poly_t poly1, const gr_poly_t poly2, slong n, gr_ctx_t ctx)source
int _gr_poly_compose_series_divconquer(gr_ptr res, gr_srcptr poly1, slong len1, gr_srcptr poly2, slong len2, slong n, gr_ctx_t ctx)source
int gr_poly_compose_series_divconquer(gr_poly_t res, const gr_poly_t poly1, const gr_poly_t poly2, slong n, gr_ctx_t ctx)source
int _gr_poly_compose_series_kinoshita_li(gr_ptr res, gr_srcptr poly1, slong len1, gr_srcptr poly2, slong len2, slong n, gr_ctx_t ctx)source
int gr_poly_compose_series_kinoshita_li(gr_poly_t res, const gr_poly_t poly1, const gr_poly_t poly2, slong n, gr_ctx_t ctx)source

Set res to the power series composition f(g(x)) \bmod x^n, where f is poly1 and g is poly2 with g(0) = 0 (the non-underscore versions return GR_DOMAIN if g(0) is nonzero and GR_UNABLE if it is not provably zero). The algorithms are Horner's rule, the baby-step giant-step method of Brent and Kung [BrentKung1978], divide and conquer, and the algorithm of Kinoshita and Li [KL2024] with O(M(n) \log n) operations.

The default version handles n \le 3 and a monomial g = a x^k directly, uses Horner's rule when \mathit{len1} \le 7 or n \le 7, Brent-Kung when \mathit{len1}^2 < n or the full composition is shorter than 4n, and otherwise divide and conquer below a cutoff and Kinoshita-Li above it. The cutoff is 500, and for rings with a real precision p (balls, floating-point numbers) it is \max(100, 15000 / \sqrt{\max(64, p)}). See Composition of power series. The underscore versions require g(0) = 0, do not allow aliasing of the output with an input, and write n coefficients without zero-padding beyond the length of the composition.

References#

  • [BrentKung1978] Brent, R. P. and Kung, H. T. : Fast Algorithms for Manipulating Formal Power Series, J. ACM 25:4 (1978) 581–595
  • [KL2024] Y. Kinoshita and B. Li, "Power series composition in near-linear time", 2024, https://arxiv.org/abs/2404.05177
Cite this page

The FLINT team, “_gr_poly_compose_series, gr_poly_compose_series, _gr_poly_compose_series_horner, gr_poly_compose_series_horner, _gr_poly_compose_series_brent_kung, gr_poly_compose_series_brent_kung, _gr_poly_compose_series_divconquer, gr_poly_compose_series_divconquer, _gr_poly_compose_series_kinoshita_li, gr_poly_compose_series_kinoshita_li (gr_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/gr_poly/_gr_poly_compose_series.html (generated 2026-10-20).