FLINT3.7.0-dev
/

_gr_poly_pow_series_fmpq_recurrence, gr_poly_pow_series_fmpq_recurrence

Synopsis#include <flint/gr_poly.h>
int _gr_poly_pow_series_fmpq_recurrence(gr_ptr h, gr_srcptr f, slong flen, const fmpq_t exp, slong len, int precomp, gr_ctx_t ctx)source
int gr_poly_pow_series_fmpq_recurrence(gr_poly_t res, const gr_poly_t poly, const fmpq_t exp, slong len, gr_ctx_t ctx)source

Set res to the power series fp/q mod xlenf^{p/q} \bmod x^{\mathit{len}} for a rational exponent p/qp/q, using the recurrence obtained from qfh′=pf′hq f h' = p f' h for h=fp/qh = f^{p/q} (often attributed to J. C. P. Miller, see [Knu1997, §4.7]), which costs O(flen⋅len)O(\mathit{flen} \cdot \mathit{len}) operations. The constant term f0p/qf_0^{p/q} is computed with gr_pow_fmpq, and the recurrence divides by iqf0i q f_0 for i=1,…,len−1i = 1, \ldots, \mathit{len} - 1, so f0f_0 and these integers must be invertible (or the divisions exact).

The underscore version writes len coefficients. Its flags precomp allow precomputed data: if bit 0 is set, h[0] already contains f0p/qf_0^{p/q}; if bit 1 is set, h[i] contains 1/i1/i for 1≤i<len1 \le i < \mathit{len} on input. Over integral domains of characteristic zero and integer exponents, the divisions are exact divisions.

References#

  • [Knu1997] Knuth, D. E. The Art of Computer Programming, volume 2: Seminumerical algorithms, 1997
Cite this page

The FLINT team, “_gr_poly_pow_series_fmpq_recurrence, gr_poly_pow_series_fmpq_recurrence (gr_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/gr_poly/_gr_poly_pow_series_fmpq_recurrence.html (generated 2026-11-02).