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