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 <http://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_log_series_monomial_ui(mp_ptr res,mp_limb_t coeff,ulong power,slong n,nmod_t mod)19 _nmod_poly_log_series_monomial_ui(mp_ptr res, mp_limb_t coeff, ulong power,
20 slong n, nmod_t mod)
21 {
22 slong j, k, rlen;
23 mp_limb_t a;
24
25 _nmod_vec_zero(res, n);
26
27 if (power >= n)
28 return;
29
30 rlen = (n - 1) / power;
31 a = coeff;
32 coeff = n_negmod(coeff, mod.n);
33
34 /* Construct geometric series */
35 if (coeff == UWORD(1))
36 {
37 for (j = 0; j < rlen; j++)
38 res[j] = a;
39 }
40 else if (a == UWORD(1))
41 {
42 for (j = 0; j < rlen; j++)
43 res[j] = (j % 2) ? coeff : a;
44 }
45 else
46 {
47 for (j = 0; j < rlen; j++)
48 {
49 res[j] = a;
50 a = n_mulmod2_preinv(a, coeff, mod.n, mod.ninv);
51 }
52 }
53
54 /* Integrate */
55 _nmod_poly_integral(res, res, rlen + 1, mod);
56
57 /* Expand */
58 if (power != 1)
59 {
60 for (j = rlen * power + 1; j < n; j++)
61 res[j] = UWORD(0);
62 for (j = rlen; j > 0; j--)
63 {
64 res[j * power] = res[j];
65 for (k = power; k > 0; k--)
66 res[j * power - k] = UWORD(0);
67 }
68 }
69 }
70
71 void
nmod_poly_log_series_monomial_ui(nmod_poly_t res,mp_limb_t coeff,ulong power,slong n)72 nmod_poly_log_series_monomial_ui(nmod_poly_t res, mp_limb_t coeff,
73 ulong power, slong n)
74 {
75 if (power == 0)
76 {
77 flint_printf("Exception (nmod_poly_log_series_monomial_ui). \n"
78 "Constant term != 1.\n");
79 flint_abort();
80 }
81
82 if (coeff != UWORD(1))
83 coeff = n_mod2_preinv(coeff, res->mod.n, res->mod.ninv);
84
85 if (n <= 1 || coeff == UWORD(0))
86 {
87 nmod_poly_zero(res);
88 return;
89 }
90
91 nmod_poly_fit_length(res, n);
92 _nmod_poly_log_series_monomial_ui(res->coeffs, coeff, power, n, res->mod);
93 res->length = n;
94 _nmod_poly_normalise(res);
95 }
96