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 ff to exp⁡(h) mod xn\exp(h) \bmod x^n.

The basecase version uses the recurrence kfk=∑j=1kjhjfk−jk f_k = \sum_{j=1}^{k} j h_j f_{k-j} from f′=h′ff' = h' f, with O(hlen⋅n)O(\mathit{hlen} \cdot n) operations and divisions by 1,…,n−11, \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+b2/2+⋯ )\exp(a + b) = \exp(a)(1 + b + b^2/2 + \cdots) for bb divisible by x⌈n/3⌉x^{\lceil n/3 \rceil}. The newton version uses the iteration f←f(1+h−log⁡f)f \gets f(1 + h - \log f) with the simultaneous iteration for 1/f1/f of [HZ2004; Ber2008], starting from the basecase below cutoff; if g is not NULL, the underscore version also writes 1/f mod xn1/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<10n < 10, hlen<10\mathit{hlen} < 10 or rings with classical multiplication, the basecase_mul version for n<30n < 30 when hh is nearly as long as nn, 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-11-02).