1 /*
2 Copyright (C) 2011 Fredrik Johansson
3
4 This file is part of FLINT.
5
6 FLINT is free software: you can redistribute it and/or modify it under
7 the terms of the GNU Lesser General Public License (LGPL) as published
8 by the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version. See <https://www.gnu.org/licenses/>.
10 */
11
12 #include <gmp.h>
13 #include "flint.h"
14 #include "ulong_extras.h"
15 #include "nmod_vec.h"
16 #include "nmod_poly.h"
17
18 void
_nmod_poly_exp_series_monomial_ui(mp_ptr res,mp_limb_t coeff,ulong power,slong n,nmod_t mod)19 _nmod_poly_exp_series_monomial_ui(mp_ptr res, mp_limb_t coeff, ulong power,
20 slong n, nmod_t mod)
21 {
22 slong k, r;
23 mp_limb_t rfac;
24 mp_limb_t a;
25
26 r = (n - 1) / power;
27 rfac = n_factorial_mod2_preinv(r, mod.n, mod.ninv);
28 rfac = n_invmod(rfac, mod.n);
29
30 if (power > 1)
31 _nmod_vec_zero(res, n);
32
33 res[0] = UWORD(1);
34
35 if (coeff == UWORD(1))
36 {
37 a = rfac;
38 for (k = r; k >= 1; k--)
39 {
40 res[k * power] = a;
41 a = n_mulmod2_preinv(a, k, mod.n, mod.ninv);
42 }
43 }
44 else
45 {
46 a = coeff;
47 for (k = power; k < n; k += power)
48 {
49 res[k] = a;
50 a = n_mulmod2_preinv(a, coeff, mod.n, mod.ninv);
51 }
52
53 a = rfac;
54 for (k = r; k >= 1; k--)
55 {
56 res[k * power] = n_mulmod2_preinv(res[k * power],
57 a, mod.n, mod.ninv);
58 a = n_mulmod2_preinv(a, k, mod.n, mod.ninv);
59 }
60 }
61 }
62
63 void
nmod_poly_exp_series_monomial_ui(nmod_poly_t res,mp_limb_t coeff,ulong power,slong n)64 nmod_poly_exp_series_monomial_ui(nmod_poly_t res, mp_limb_t coeff,
65 ulong power, slong n)
66 {
67 if (n == 0)
68 {
69 nmod_poly_zero(res);
70 return;
71 }
72
73 if (coeff == UWORD(0))
74 {
75 nmod_poly_fit_length(res, 1);
76 res->coeffs[0] = UWORD(1);
77 res->length = 1;
78 return;
79 }
80
81 if (power == 0)
82 {
83 flint_printf("Exception (nmod_poly_exp_series_monomial_ui). \n"
84 "Constant term != 0.\n");
85 flint_abort();
86 }
87
88 if (coeff != UWORD(1))
89 coeff = n_mod2_preinv(coeff, res->mod.n, res->mod.ninv);
90
91 if (n == 1 || power >= n)
92 {
93 nmod_poly_fit_length(res, 1);
94 res->coeffs[0] = UWORD(1);
95 res->length = 1;
96 }
97
98 nmod_poly_fit_length(res, n);
99 _nmod_poly_exp_series_monomial_ui(res->coeffs, coeff, power, n, res->mod);
100 res->length = n;
101 _nmod_poly_normalise(res);
102 }
103