1 /*
2 Copyright (C) 2010 William Hart
3 Copyright (C) 2010, 2012 Sebastian Pancratz
4
5 This file is part of FLINT.
6
7 FLINT is free software: you can redistribute it and/or modify it under
8 the terms of the GNU Lesser General Public License (LGPL) as published
9 by the Free Software Foundation; either version 2.1 of the License, or
10 (at your option) any later version. See <http://www.gnu.org/licenses/>.
11 */
12
13 #include "nmod_poly.h"
14
15 void
_nmod_poly_compose(mp_ptr res,mp_srcptr poly1,slong len1,mp_srcptr poly2,slong len2,nmod_t mod)16 _nmod_poly_compose(mp_ptr res, mp_srcptr poly1, slong len1,
17 mp_srcptr poly2, slong len2, nmod_t mod)
18 {
19 if (len1 == 1)
20 res[0] = poly1[0];
21 else if (len2 == 1)
22 res[0] = _nmod_poly_evaluate_nmod(poly1, len1, poly2[0], mod);
23 else if (len1 <= 7)
24 _nmod_poly_compose_horner(res, poly1, len1, poly2, len2, mod);
25 else
26 _nmod_poly_compose_divconquer(res, poly1, len1, poly2, len2, mod);
27 }
28
nmod_poly_compose(nmod_poly_t res,const nmod_poly_t poly1,const nmod_poly_t poly2)29 void nmod_poly_compose(nmod_poly_t res,
30 const nmod_poly_t poly1, const nmod_poly_t poly2)
31 {
32 const slong len1 = poly1->length;
33 const slong len2 = poly2->length;
34
35 if (len1 == 0)
36 {
37 nmod_poly_zero(res);
38 }
39 else if (len1 == 1 || len2 == 0)
40 {
41 nmod_poly_fit_length(res, 1);
42 res->coeffs[0] = poly1->coeffs[0];
43 res->length = (res->coeffs[0] != 0);
44 }
45 else
46 {
47 const slong lenr = (len1 - 1) * (len2 - 1) + 1;
48
49 if (res != poly1 && res != poly2)
50 {
51 nmod_poly_fit_length(res, lenr);
52 _nmod_poly_compose_horner(res->coeffs, poly1->coeffs, len1,
53 poly2->coeffs, len2, poly1->mod);
54 }
55 else
56 {
57 nmod_poly_t t;
58 nmod_poly_init2(t, poly1->mod.n, lenr);
59 _nmod_poly_compose_horner(t->coeffs, poly1->coeffs, len1,
60 poly2->coeffs, len2, poly1->mod);
61 nmod_poly_swap(res, t);
62 nmod_poly_clear(t);
63 }
64
65 res->length = lenr;
66 _nmod_poly_normalise(res);
67 }
68 }
69