FLINT3.7.0-dev
/

_fmpz_poly_pow_multinomial, fmpz_poly_pow_multinomial

Synopsis#include <flint/fmpz_poly.h>
void _fmpz_poly_pow_multinomial(fmpz * res, const fmpz * poly, slong len, ulong e)source
void fmpz_poly_pow_multinomial(fmpz_poly_t res, const fmpz_poly_t poly, ulong e)source

Set res to poly raised to the power e using the J. C. P. Miller recurrence [Knu1997, §4.6.1, exercise 16], [Zei1995]: if P(x) = \sum_{i=0}^m p_i x^i with p_0 \ne 0 and P(x)^e = \sum_k a_k x^k, then a_0 = p_0^e and

a_k = \frac{1}{k p_0} \sum_{i=1}^{\min(k, m)} p_i \bigl((e + 1) i - k\bigr) a_{k-i}, \qquad k \ge 1.

Each coefficient costs O(m) multiplications and one exact division. Low zero coefficients are removed first. The underscore version requires \mathit{len} > 0 and e > 0 and does not allow aliasing.

References#

  • [Knu1997] Knuth, D. E. The Art of Computer Programming, volume 2: Seminumerical algorithms, 1997
  • [Zei1995] D. Zeilberger. The J. C. P. Miller recurrence for exponentiating a polynomial, and its q-analog. Journal of Difference Equations and Applications 1 (1995), 57–60. https://doi.org/10.1080/10236199508808006
Cite this page

The FLINT team, “_fmpz_poly_pow_multinomial, fmpz_poly_pow_multinomial (fmpz_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fmpz_poly/_fmpz_poly_pow_multinomial.html (generated 2026-10-20).