FLINT3.7.0-dev
/

_acb_poly_compose_series, acb_poly_compose_series

Synopsis#include <flint/acb_poly.h>
void _acb_poly_compose_series(acb_ptr res, acb_srcptr poly1, slong len1, acb_srcptr poly2, slong len2, slong n, slong prec)source
void acb_poly_compose_series(acb_poly_t res, const acb_poly_t poly1, const acb_poly_t poly2, slong n, slong prec)source

Set res to the power series composition f(g(x)) \bmod x^n. The constant term of g must be exactly zero; acb_poly_compose_series throws an exception otherwise. The underscore version does not allow aliasing. Wrappers of _gr_poly_compose_series.

The generic function uses Horner's scheme if f or n is short (length at most 7), divide and conquer if \mathit{len1}^2 < n or the untruncated composition is shorter than 4n, and otherwise the Brent–Kung baby-step giant-step algorithm [BrentKung1978] for n below \max(100, 15000/\sqrt{\max(64, \mathit{prec})}) and the algorithm of Kinoshita and Li [KL2024] above (Composition and modular composition). If some coefficients of the inputs are not finite, only the coefficients that depend on finite input are computed; the others are set to indeterminate balls.

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, “_acb_poly_compose_series, acb_poly_compose_series (acb_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/acb_poly/_acb_poly_compose_series.html (generated 2026-10-20).