1 /*
2 Copyright (C) 2011 Fredrik Johansson
3 Copyright (C) 2012 William Hart
4 Copyright (C) 2013 Mike Hansen
5
6 This file is part of FLINT.
7
8 FLINT is free software: you can redistribute it and/or modify it under
9 the terms of the GNU Lesser General Public License (LGPL) as published
10 by the Free Software Foundation; either version 2.1 of the License, or
11 (at your option) any later version. See <http://www.gnu.org/licenses/>.
12 */
13
14 #ifdef T
15
16 #include "templates.h"
17
TEMPLATE(T,poly_struct)18 TEMPLATE(T, poly_struct) **
19 _TEMPLATE(T, poly_tree_alloc)(slong len, const TEMPLATE(T, ctx_t) ctx)
20 {
21 TEMPLATE(T, poly_struct) ** tree = NULL;
22
23 if (len)
24 {
25 slong i, j, height = FLINT_CLOG2(len);
26
27 tree = flint_malloc(sizeof(TEMPLATE(T, poly_struct) *) * (height + 1));
28 for (i = 0; i <= height; i++, len = (len + 1)/2)
29 {
30 tree[i] = flint_malloc(sizeof(TEMPLATE(T, poly_struct)) * len);
31 for (j = 0; j < len; j++)
32 TEMPLATE(T, poly_init)(tree[i] + j, ctx);
33 }
34
35 }
36
37 return tree;
38 }
39
40 void
_TEMPLATE(T,poly_tree_free)41 _TEMPLATE(T, poly_tree_free)(TEMPLATE(T, poly_struct) ** tree, slong len,
42 const TEMPLATE(T, ctx_t) ctx)
43 {
44 if (len)
45 {
46 slong i, j, height = FLINT_CLOG2(len);
47
48 for (i = 0; i <= height; i++, len = (len + 1)/2)
49 {
50 for (j = 0; j < len; j++)
51 TEMPLATE(T, poly_clear)(tree[i] + j, ctx);
52 flint_free(tree[i]);
53 }
54
55 flint_free(tree);
56 }
57 }
58
59 void
_TEMPLATE(T,poly_tree_build)60 _TEMPLATE(T, poly_tree_build)(TEMPLATE(T, poly_struct) ** tree,
61 const TEMPLATE(T, struct) * roots,
62 slong len,
63 const TEMPLATE(T, ctx_t) ctx)
64 {
65 slong height, pow, left, i;
66 TEMPLATE(T, poly_struct) * pa, * pb;
67
68 if (len == 0)
69 return;
70
71 height = FLINT_CLOG2(len);
72
73 /* zeroth level, (x-a) */
74 for (i = 0; i < len; i++)
75 {
76 TEMPLATE(T, poly_gen)(tree[0] + i, ctx);
77 TEMPLATE(T, neg)((tree[0] + i)->coeffs, roots + i, ctx);
78 }
79
80 for (i = 0; i < height - 1; i++)
81 {
82 left = len;
83 pow = WORD(1) << i;
84 pa = tree[i];
85 pb = tree[i + 1];
86
87 while (left >= 2 * pow)
88 {
89 TEMPLATE(T, poly_fit_length)(pb, pa->length + (pa + 1)->length - 1,
90 ctx);
91 _TEMPLATE(T, poly_mul)(pb->coeffs,
92 pa->coeffs, pa->length,
93 (pa + 1)->coeffs, (pa + 1)->length,
94 ctx);
95 _TEMPLATE(T, poly_set_length)(pb, pa->length + (pa + 1)->length - 1,
96 ctx);
97 left -= 2 * pow;
98 pa += 2;
99 pb += 1;
100 }
101
102 if (left > pow)
103 {
104 TEMPLATE(T, poly_fit_length)(pb, pa->length + (pa + 1)->length - 1,
105 ctx);
106 _TEMPLATE(T, poly_mul)(pb->coeffs,
107 pa->coeffs, pa->length,
108 (pa + 1)->coeffs, (pa + 1)->length,
109 ctx);
110 _TEMPLATE(T, poly_set_length)(pb, pa->length + (pa + 1)->length - 1,
111 ctx);
112 } else if (left > 0)
113 TEMPLATE(T, poly_set)(pb, pa, ctx);
114 }
115 }
116
117
118 #endif
119