1 /*
2 Copyright (C) 2019 Daniel Schultz
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 "fq_nmod_mpoly.h"
13
14
fq_nmod_mpoly_geobucket_init(fq_nmod_mpoly_geobucket_t B,const fq_nmod_mpoly_ctx_t ctx)15 void fq_nmod_mpoly_geobucket_init(fq_nmod_mpoly_geobucket_t B,
16 const fq_nmod_mpoly_ctx_t ctx)
17 {
18 B->length = 0;
19 }
20
fq_nmod_mpoly_geobucket_clear(fq_nmod_mpoly_geobucket_t B,const fq_nmod_mpoly_ctx_t ctx)21 void fq_nmod_mpoly_geobucket_clear(fq_nmod_mpoly_geobucket_t B,
22 const fq_nmod_mpoly_ctx_t ctx)
23 {
24 slong i;
25 for (i = 0; i < B->length; i++)
26 fq_nmod_mpoly_clear(B->polys + i, ctx);
27 }
28
29 /* empty out bucket B into polynomial p */
fq_nmod_mpoly_geobucket_empty(fq_nmod_mpoly_t p,fq_nmod_mpoly_geobucket_t B,const fq_nmod_mpoly_ctx_t ctx)30 void fq_nmod_mpoly_geobucket_empty(fq_nmod_mpoly_t p, fq_nmod_mpoly_geobucket_t B,
31 const fq_nmod_mpoly_ctx_t ctx)
32 {
33 slong i;
34 fq_nmod_mpoly_zero(p, ctx);
35 for (i = 0; i < B->length; i++)
36 {
37 fq_nmod_mpoly_add(p, p, B->polys + i, ctx);
38 fq_nmod_mpoly_clear(B->polys + i, ctx);
39 }
40 B->length = 0;
41 }
42
fq_nmod_mpoly_geobucket_print(fq_nmod_mpoly_geobucket_t B,const char ** x,const fq_nmod_mpoly_ctx_t ctx)43 void fq_nmod_mpoly_geobucket_print(fq_nmod_mpoly_geobucket_t B, const char ** x,
44 const fq_nmod_mpoly_ctx_t ctx)
45 {
46 slong i;
47 printf("{");
48 for (i = 0; i < B->length; i++)
49 {
50 fq_nmod_mpoly_print_pretty(B->polys + i, x, ctx);
51 if (i + 1 < B->length)
52 printf(", ");
53 }
54 printf("}");
55 }
56
57 /* ceiling(log_4(x)) - 1 */
fq_nmod_mpoly_geobucket_clog4(slong x)58 slong fq_nmod_mpoly_geobucket_clog4(slong x)
59 {
60 if (x <= 4)
61 return 0;
62 /*
63 FLINT_BIT_COUNT returns unsigned int.
64 Signed division is not defined.
65 Do the calculation with unsigned ints and then convert to slong.
66 */
67 x = (FLINT_BIT_COUNT(x - 1) - (unsigned int) 1)/((unsigned int) 2);
68 return x;
69 }
70
fq_nmod_mpoly_geobucket_fit_length(fq_nmod_mpoly_geobucket_t B,slong len,const fq_nmod_mpoly_ctx_t ctx)71 void fq_nmod_mpoly_geobucket_fit_length(fq_nmod_mpoly_geobucket_t B, slong len,
72 const fq_nmod_mpoly_ctx_t ctx)
73 {
74 slong j;
75 for (j = B->length; j < len; j++)
76 {
77 fq_nmod_mpoly_init(B->polys + j, ctx);
78 fq_nmod_mpoly_zero(B->polys + j, ctx);
79 }
80 B->length = j;
81 }
82
83 /* set bucket B to polynomial p */
fq_nmod_mpoly_geobucket_set(fq_nmod_mpoly_geobucket_t B,fq_nmod_mpoly_t p,const fq_nmod_mpoly_ctx_t ctx)84 void fq_nmod_mpoly_geobucket_set(fq_nmod_mpoly_geobucket_t B, fq_nmod_mpoly_t p,
85 const fq_nmod_mpoly_ctx_t ctx)
86 {
87 slong i;
88 fq_nmod_mpoly_geobucket_clear(B, ctx);
89 i = fq_nmod_mpoly_geobucket_clog4(p->length);
90 fq_nmod_mpoly_geobucket_fit_length(B, i + 1, ctx);
91 fq_nmod_mpoly_set(B->polys + i, p, ctx);
92 B->length = i + 1;
93 }
94
95 /* internal function for fixing overflows */
_fq_nmod_mpoly_geobucket_fix(fq_nmod_mpoly_geobucket_t B,slong i,const fq_nmod_mpoly_ctx_t ctx)96 void _fq_nmod_mpoly_geobucket_fix(fq_nmod_mpoly_geobucket_t B, slong i,
97 const fq_nmod_mpoly_ctx_t ctx)
98 {
99 while (fq_nmod_mpoly_geobucket_clog4((B->polys + i)->length) > i)
100 {
101 FLINT_ASSERT(i + 1 <= B->length);
102 if (i + 1 == B->length)
103 {
104 fq_nmod_mpoly_init(B->polys + i + 1, ctx);
105 fq_nmod_mpoly_zero(B->polys + i + 1, ctx);
106 B->length = i + 2;
107 }
108 fq_nmod_mpoly_add(B->polys + i + 1, B->polys + i + 1, B->polys + i, ctx);
109 fq_nmod_mpoly_zero(B->polys + i, ctx);
110 i++;
111 }
112 }
113
114 /* add polynomial p to buckect B */
fq_nmod_mpoly_geobucket_add(fq_nmod_mpoly_geobucket_t B,fq_nmod_mpoly_t p,const fq_nmod_mpoly_ctx_t ctx)115 void fq_nmod_mpoly_geobucket_add(fq_nmod_mpoly_geobucket_t B, fq_nmod_mpoly_t p,
116 const fq_nmod_mpoly_ctx_t ctx)
117 {
118 slong i;
119 i = fq_nmod_mpoly_geobucket_clog4(p->length);
120 fq_nmod_mpoly_geobucket_fit_length(B, i + 1, ctx);
121 fq_nmod_mpoly_add(B->polys + i, B->polys + i, p, ctx);
122 _fq_nmod_mpoly_geobucket_fix(B, i, ctx);
123 }
124
125 /* sub polynomial p to buckect B */
fq_nmod_mpoly_geobucket_sub(fq_nmod_mpoly_geobucket_t B,fq_nmod_mpoly_t p,const fq_nmod_mpoly_ctx_t ctx)126 void fq_nmod_mpoly_geobucket_sub(fq_nmod_mpoly_geobucket_t B, fq_nmod_mpoly_t p,
127 const fq_nmod_mpoly_ctx_t ctx)
128 {
129 slong i;
130 i = fq_nmod_mpoly_geobucket_clog4(p->length);
131 fq_nmod_mpoly_geobucket_fit_length(B, i + 1, ctx);
132 fq_nmod_mpoly_sub(B->polys + i, B->polys + i, p, ctx);
133 _fq_nmod_mpoly_geobucket_fix(B, i, ctx);
134 }
135
fq_nmod_mpoly_geobucket_set_ui(fq_nmod_mpoly_geobucket_t B,ulong c,const fq_nmod_mpoly_ctx_t ctx)136 void fq_nmod_mpoly_geobucket_set_ui(fq_nmod_mpoly_geobucket_t B, ulong c,
137 const fq_nmod_mpoly_ctx_t ctx)
138 {
139 slong i;
140 if (B->length == 0)
141 fq_nmod_mpoly_init(B->polys + 0, ctx);
142 for (i = 1; i < B->length; i++)
143 fq_nmod_mpoly_clear(B->polys + i, ctx);
144 B->length = 1;
145 fq_nmod_mpoly_set_ui(B->polys + 0, c, ctx);
146 }
147
fq_nmod_mpoly_geobucket_set_fq_nmod_gen(fq_nmod_mpoly_geobucket_t B,const fq_nmod_mpoly_ctx_t ctx)148 void fq_nmod_mpoly_geobucket_set_fq_nmod_gen(fq_nmod_mpoly_geobucket_t B,
149 const fq_nmod_mpoly_ctx_t ctx)
150 {
151 slong i;
152 if (B->length == 0)
153 fq_nmod_mpoly_init(B->polys + 0, ctx);
154 for (i = 1; i < B->length; i++)
155 fq_nmod_mpoly_clear(B->polys + i, ctx);
156 B->length = 1;
157 fq_nmod_mpoly_set_fq_nmod_gen(B->polys + 0, ctx);
158 }
159
fq_nmod_mpoly_geobucket_gen(fq_nmod_mpoly_geobucket_t B,slong var,const fq_nmod_mpoly_ctx_t ctx)160 void fq_nmod_mpoly_geobucket_gen(fq_nmod_mpoly_geobucket_t B, slong var,
161 const fq_nmod_mpoly_ctx_t ctx)
162 {
163 slong i;
164 if (B->length == 0)
165 fq_nmod_mpoly_init(B->polys + 0, ctx);
166 for (i = 1; i < B->length; i++)
167 fq_nmod_mpoly_clear(B->polys + i, ctx);
168 B->length = 1;
169 fq_nmod_mpoly_gen(B->polys + 0, var, ctx);
170 }
171
fq_nmod_mpoly_geobucket_add_inplace(fq_nmod_mpoly_geobucket_t A,fq_nmod_mpoly_geobucket_t B,const fq_nmod_mpoly_ctx_t ctx)172 void fq_nmod_mpoly_geobucket_add_inplace(fq_nmod_mpoly_geobucket_t A,
173 fq_nmod_mpoly_geobucket_t B, const fq_nmod_mpoly_ctx_t ctx)
174 {
175 slong i;
176 for (i = 0; i < B->length; i++)
177 fq_nmod_mpoly_geobucket_add(A, B->polys + i, ctx);
178
179 }
180
fq_nmod_mpoly_geobucket_sub_inplace(fq_nmod_mpoly_geobucket_t A,fq_nmod_mpoly_geobucket_t B,const fq_nmod_mpoly_ctx_t ctx)181 void fq_nmod_mpoly_geobucket_sub_inplace(fq_nmod_mpoly_geobucket_t A,
182 fq_nmod_mpoly_geobucket_t B, const fq_nmod_mpoly_ctx_t ctx)
183 {
184 slong i;
185 for (i = 0; i < B->length; i++)
186 fq_nmod_mpoly_geobucket_sub(A, B->polys + i, ctx);
187 }
188
fq_nmod_mpoly_geobucket_neg_inplace(fq_nmod_mpoly_geobucket_t A,const fq_nmod_mpoly_ctx_t ctx)189 void fq_nmod_mpoly_geobucket_neg_inplace(fq_nmod_mpoly_geobucket_t A,
190 const fq_nmod_mpoly_ctx_t ctx)
191 {
192 slong i;
193 for (i = 0; i < A->length; i++)
194 fq_nmod_mpoly_neg(A->polys + i, A->polys + i, ctx);
195 }
196
fq_nmod_mpoly_geobucket_mul_inplace(fq_nmod_mpoly_geobucket_t A,fq_nmod_mpoly_geobucket_t B,const fq_nmod_mpoly_ctx_t ctx)197 void fq_nmod_mpoly_geobucket_mul_inplace(fq_nmod_mpoly_geobucket_t A,
198 fq_nmod_mpoly_geobucket_t B, const fq_nmod_mpoly_ctx_t ctx)
199 {
200 fq_nmod_mpoly_t a, b;
201 fq_nmod_mpoly_init(a, ctx);
202 fq_nmod_mpoly_init(b, ctx);
203
204 fq_nmod_mpoly_geobucket_empty(a, A, ctx);
205 fq_nmod_mpoly_geobucket_empty(b, B, ctx);
206 fq_nmod_mpoly_mul(a, a, b, ctx);
207 fq_nmod_mpoly_geobucket_set(A, a, ctx);
208
209 fq_nmod_mpoly_clear(a, ctx);
210 fq_nmod_mpoly_clear(b, ctx);
211 }
212
fq_nmod_mpoly_geobucket_pow_ui(fq_nmod_mpoly_geobucket_t A,ulong k,const fq_nmod_mpoly_ctx_t ctx)213 void fq_nmod_mpoly_geobucket_pow_ui(fq_nmod_mpoly_geobucket_t A,
214 ulong k, const fq_nmod_mpoly_ctx_t ctx)
215 {
216 fq_nmod_mpoly_t a;
217 fq_nmod_mpoly_init(a, ctx);
218
219 fq_nmod_mpoly_geobucket_empty(a, A, ctx);
220 if (!fq_nmod_mpoly_pow_ui(a, a, k, ctx))
221 flint_throw(FLINT_ERROR, "fq_nmod_mpoly_pow_ui failed");
222 fq_nmod_mpoly_geobucket_set(A, a, ctx);
223
224 fq_nmod_mpoly_clear(a, ctx);
225 }
226
fq_nmod_mpoly_geobucket_pow_fmpz_inplace(fq_nmod_mpoly_geobucket_t A,const fmpz_t k,const fq_nmod_mpoly_ctx_t ctx)227 void fq_nmod_mpoly_geobucket_pow_fmpz_inplace(fq_nmod_mpoly_geobucket_t A,
228 const fmpz_t k, const fq_nmod_mpoly_ctx_t ctx)
229 {
230 fq_nmod_mpoly_t a;
231 fq_nmod_mpoly_init(a, ctx);
232
233 fq_nmod_mpoly_geobucket_empty(a, A, ctx);
234 if (!fq_nmod_mpoly_pow_fmpz(a, a, k, ctx))
235 flint_throw(FLINT_ERROR, "fq_nmod_mpoly_pow_fmpz failed");
236
237 fq_nmod_mpoly_geobucket_set(A, a, ctx);
238
239 fq_nmod_mpoly_clear(a, ctx);
240 }
241
242
fq_nmod_mpoly_geobucket_divides_inplace(fq_nmod_mpoly_geobucket_t A,fq_nmod_mpoly_geobucket_t B,const fq_nmod_mpoly_ctx_t ctx)243 int fq_nmod_mpoly_geobucket_divides_inplace(fq_nmod_mpoly_geobucket_t A,
244 fq_nmod_mpoly_geobucket_t B, const fq_nmod_mpoly_ctx_t ctx)
245 {
246 int ret = 0;
247 fq_nmod_mpoly_t a, b;
248 fq_nmod_mpoly_init(a, ctx);
249 fq_nmod_mpoly_init(b, ctx);
250
251 fq_nmod_mpoly_geobucket_empty(a, A, ctx);
252 fq_nmod_mpoly_geobucket_empty(b, B, ctx);
253
254 if (!fq_nmod_mpoly_is_zero(b, ctx))
255 {
256 ret = fq_nmod_mpoly_divides(a, a, b, ctx);
257 fq_nmod_mpoly_geobucket_set(A, a, ctx);
258 }
259
260 fq_nmod_mpoly_clear(a, ctx);
261 fq_nmod_mpoly_clear(b, ctx);
262 return ret;
263 }
264