FLINT3.7.0-dev
/

_gr_poly_exp_series, gr_poly_exp_series, _gr_poly_exp_series_generic, _gr_poly_exp_series_basecase, gr_poly_exp_series_basecase, _gr_poly_exp_series_basecase_mul, gr_poly_exp_series_basecase_mul, _gr_poly_exp_series_newton, gr_poly_exp_series_newton

Synopsis#include <flint/gr_poly.h>
int _gr_poly_exp_series(gr_ptr res, gr_srcptr f, slong flen, slong len, gr_ctx_t ctx)source
int gr_poly_exp_series(gr_poly_t f, const gr_poly_t h, slong n, gr_ctx_t ctx)source
int _gr_poly_exp_series_generic(gr_ptr f, gr_srcptr h, slong hlen, slong n, gr_ctx_t ctx)source
int _gr_poly_exp_series_basecase(gr_ptr f, gr_srcptr h, slong hlen, slong n, gr_ctx_t ctx)source
int gr_poly_exp_series_basecase(gr_poly_t f, const gr_poly_t h, slong n, gr_ctx_t ctx)source
int _gr_poly_exp_series_basecase_mul(gr_ptr f, gr_srcptr h, slong hlen, slong n, gr_ctx_t ctx)source
int gr_poly_exp_series_basecase_mul(gr_poly_t f, const gr_poly_t h, slong n, gr_ctx_t ctx)source
int _gr_poly_exp_series_newton(gr_ptr f, gr_ptr g, gr_srcptr h, slong hlen, slong n, slong cutoff, gr_ctx_t ctx)source
int gr_poly_exp_series_newton(gr_poly_t f, const gr_poly_t h, slong n, slong cutoff, gr_ctx_t ctx)source

Set f to \exp(h) \bmod x^n.

The basecase version uses the recurrence k f_k = \sum_{j=1}^{k} j h_j f_{k-j} from f' = h' f, with O(\mathit{hlen} \cdot n) operations and divisions by 1, \ldots, n - 1. The basecase_mul version computes the low third with the recurrence and corrects the rest with two truncated products, using \exp(a + b) = \exp(a)(1 + b + b^2/2 + \cdots) for b divisible by x^{\lceil n/3 \rceil}. The newton version uses the iteration f \gets f(1 + h - \log f) with the simultaneous iteration for 1/f of [HZ2004; Ber2008], starting from the basecase below cutoff; if g is not NULL, the underscore version also writes 1/f \bmod x^n to it.

_gr_poly_exp_series calls the ring method GR_METHOD_POLY_EXP_SERIES (overridden by nmod), whose default _gr_poly_exp_series_generic uses the basecase for n < 10, \mathit{hlen} < 10 or rings with classical multiplication, the basecase_mul version for n < 30 when h is nearly as long as n, and Newton iteration with cutoff 30 otherwise.

References#

  • [HZ2004] G. Hanrot and P. Zimmermann, "Newton Iteration Revisited" (2004), http://www.loria.fr/~zimmerma/papers/fastnewton.ps.gz
  • [Ber2008] D. J. Bernstein, "Fast multiplication and its applications", in Algorithmic Number Theory, MSRI Publications 44 (2008), 325–384
Cite this page

The FLINT team, “_gr_poly_exp_series, gr_poly_exp_series, _gr_poly_exp_series_generic, _gr_poly_exp_series_basecase, gr_poly_exp_series_basecase, _gr_poly_exp_series_basecase_mul, gr_poly_exp_series_basecase_mul, _gr_poly_exp_series_newton, gr_poly_exp_series_newton (gr_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/gr_poly/_gr_poly_exp_series.html (generated 2026-10-20).