1 /*
2 Copyright (C) 2017 William Hart
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 <https://www.gnu.org/licenses/>.
10 */
11
12 #include <stdio.h>
13 #include <stdlib.h>
14 #include <gmp.h>
15 #include "flint.h"
16 #include "fmpz.h"
17 #include "fmpz_mpoly.h"
18 #include "ulong_extras.h"
19
20 int
main(void)21 main(void)
22 {
23 int i, j, result, ok1, ok2;
24 FLINT_TEST_INIT(state);
25
26 flint_printf("divides_array....");
27 fflush(stdout);
28
29 /* Check f*g/g = f */
30 for (i = 0; i < 10 * flint_test_multiplier(); i++)
31 {
32 fmpz_mpoly_ctx_t ctx;
33 fmpz_mpoly_t f, g, h, k;
34 ordering_t ord;
35 slong nvars, len, len1, len2, exp_bound, exp_bound1, exp_bound2;
36 slong coeff_bits;
37
38 ord = mpoly_ordering_randtest(state);
39 nvars = n_randint(state, 10) + 1;
40
41 fmpz_mpoly_ctx_init(ctx, nvars, ord);
42
43 fmpz_mpoly_init(f, ctx);
44 fmpz_mpoly_init(g, ctx);
45 fmpz_mpoly_init(h, ctx);
46 fmpz_mpoly_init(k, ctx);
47
48 len = n_randint(state, 100);
49 len1 = n_randint(state, 100);
50 len2 = n_randint(state, 100) + 1;
51
52 exp_bound = n_randint(state, 1000/nvars/nvars) + 1;
53 exp_bound1 = n_randint(state, 1000/nvars/nvars) + 1;
54 exp_bound2 = n_randint(state, 1000/nvars/nvars) + 1;
55
56 coeff_bits = n_randint(state, 200);
57
58 for (j = 0; j < 4; j++)
59 {
60 fmpz_mpoly_randtest_bound(f, state, len1, coeff_bits, exp_bound1, ctx);
61 do {
62 fmpz_mpoly_randtest_bound(g, state, len2, coeff_bits + 1, exp_bound2, ctx);
63 } while (g->length == 0);
64 fmpz_mpoly_randtest_bound(h, state, len, coeff_bits, exp_bound, ctx);
65 fmpz_mpoly_randtest_bound(k, state, len, coeff_bits, exp_bound, ctx);
66
67 fmpz_mpoly_mul_johnson(h, f, g, ctx);
68 fmpz_mpoly_assert_canonical(h, ctx);
69
70 ok1 = fmpz_mpoly_divides_array(k, h, g, ctx);
71 fmpz_mpoly_assert_canonical(k, ctx);
72
73 result = (ok1 == -1) || (ok1 && fmpz_mpoly_equal(f, k, ctx));
74
75 if (!result)
76 {
77 printf("FAIL\n");
78 flint_printf("Check f*g/g = f\ni = %wd, j = %wd\n", i, j);
79 flint_abort();
80 }
81 }
82
83 fmpz_mpoly_clear(f, ctx);
84 fmpz_mpoly_clear(g, ctx);
85 fmpz_mpoly_clear(h, ctx);
86 fmpz_mpoly_clear(k, ctx);
87 }
88
89 /* Check random polys don't divide */
90 for (i = 0; i < 10 * flint_test_multiplier(); i++)
91 {
92 fmpz_mpoly_ctx_t ctx;
93 fmpz_mpoly_t f, g, h, k;
94 ordering_t ord;
95 slong nvars, len, len1, len2, exp_bound, exp_bound1, exp_bound2;
96 slong coeff_bits;
97
98 ord = mpoly_ordering_randtest(state);
99 nvars = n_randint(state, 10) + 1;
100
101 fmpz_mpoly_ctx_init(ctx, nvars, ord);
102
103 fmpz_mpoly_init(f, ctx);
104 fmpz_mpoly_init(g, ctx);
105 fmpz_mpoly_init(h, ctx);
106 fmpz_mpoly_init(k, ctx);
107
108 len = n_randint(state, 30);
109 len1 = n_randint(state, 30);
110 len2 = n_randint(state, 30) + 1;
111
112 exp_bound = n_randint(state, 1000/nvars/nvars) + 1;
113 exp_bound1 = n_randint(state, 1000/nvars/nvars) + 1;
114 exp_bound2 = n_randint(state, 1000/nvars/nvars) + 1;
115
116 coeff_bits = n_randint(state, 200);
117
118 for (j = 0; j < 4; j++)
119 {
120 fmpz_mpoly_randtest_bound(f, state, len1, coeff_bits, exp_bound1, ctx);
121 do {
122 fmpz_mpoly_randtest_bound(g, state, len2, coeff_bits + 1, exp_bound2, ctx);
123 } while (g->length == 0);
124 fmpz_mpoly_randtest_bound(h, state, len, coeff_bits, exp_bound, ctx);
125 fmpz_mpoly_randtest_bound(k, state, len, coeff_bits, exp_bound, ctx);
126
127 ok1 = fmpz_mpoly_divides_array(h, f, g, ctx);
128 fmpz_mpoly_assert_canonical(h, ctx);
129
130 if (ok1)
131 {
132 fmpz_mpoly_mul_johnson(k, h, g, ctx);
133 fmpz_mpoly_assert_canonical(k, ctx);
134 }
135
136 result = (ok1 == -1 || ok1 == 0) || (ok1 == 1 && fmpz_mpoly_equal(f, k, ctx));
137
138 if (!result)
139 {
140 printf("FAIL\n");
141 flint_printf("Check random polys don't divide\ni = %wd, j = %wd\n", i, j);
142 flint_abort();
143 }
144 }
145
146 fmpz_mpoly_clear(f, ctx);
147 fmpz_mpoly_clear(g, ctx);
148 fmpz_mpoly_clear(h, ctx);
149 fmpz_mpoly_clear(k, ctx);
150 }
151
152 /* Check aliasing first argument */
153 for (i = 0; i < 10 * flint_test_multiplier(); i++)
154 {
155 fmpz_mpoly_ctx_t ctx;
156 fmpz_mpoly_t f, g, h, k;
157 ordering_t ord;
158 slong nvars, len, len1, len2, exp_bound, exp_bound1, exp_bound2;
159 slong coeff_bits;
160
161 ord = mpoly_ordering_randtest(state);
162 nvars = n_randint(state, 10) + 1;
163
164 fmpz_mpoly_ctx_init(ctx, nvars, ord);
165
166 fmpz_mpoly_init(f, ctx);
167 fmpz_mpoly_init(g, ctx);
168 fmpz_mpoly_init(h, ctx);
169 fmpz_mpoly_init(k, ctx);
170
171 len = n_randint(state, 100);
172 len1 = n_randint(state, 100);
173 len2 = n_randint(state, 100) + 1;
174
175 exp_bound = n_randint(state, 1000/nvars/nvars) + 1;
176 exp_bound1 = n_randint(state, 1000/nvars/nvars) + 1;
177 exp_bound2 = n_randint(state, 1000/nvars/nvars) + 1;
178
179 coeff_bits = n_randint(state, 200);
180
181 for (j = 0; j < 4; j++)
182 {
183 fmpz_mpoly_randtest_bound(f, state, len1, coeff_bits, exp_bound1, ctx);
184 do {
185 fmpz_mpoly_randtest_bound(g, state, len2, coeff_bits + 1, exp_bound2, ctx);
186 } while (g->length == 0);
187 fmpz_mpoly_randtest_bound(h, state, len, coeff_bits, exp_bound, ctx);
188 fmpz_mpoly_randtest_bound(k, state, len, coeff_bits, exp_bound, ctx);
189
190 fmpz_mpoly_mul_johnson(h, f, g, ctx);
191 fmpz_mpoly_assert_canonical(h, ctx);
192
193 ok1 = fmpz_mpoly_divides_array(k, h, g, ctx);
194 fmpz_mpoly_assert_canonical(k, ctx);
195 ok2 = fmpz_mpoly_divides_array(h, h, g, ctx);
196 fmpz_mpoly_assert_canonical(h, ctx);
197
198 result = (ok1 == -1 || ok2 == -1) ||
199 (ok1 == 1 && ok2 == 1 && fmpz_mpoly_equal(h, k, ctx));
200
201 if (!result)
202 {
203 printf("FAIL\n");
204 flint_printf("Check aliasing first argument\ni = %wd, j = %wd\n", i, j);
205 flint_abort();
206 }
207 }
208
209 fmpz_mpoly_clear(f, ctx);
210 fmpz_mpoly_clear(g, ctx);
211 fmpz_mpoly_clear(h, ctx);
212 fmpz_mpoly_clear(k, ctx);
213 }
214
215 /* Check aliasing second argument */
216 for (i = 0; i < 10 * flint_test_multiplier(); i++)
217 {
218 fmpz_mpoly_ctx_t ctx;
219 fmpz_mpoly_t f, g, h, k;
220 ordering_t ord;
221 slong nvars, len, len1, len2, exp_bound, exp_bound1, exp_bound2;
222 slong coeff_bits;
223
224 ord = mpoly_ordering_randtest(state);
225 nvars = n_randint(state, 10) + 1;
226
227 fmpz_mpoly_ctx_init(ctx, nvars, ord);
228
229 fmpz_mpoly_init(f, ctx);
230 fmpz_mpoly_init(g, ctx);
231 fmpz_mpoly_init(h, ctx);
232 fmpz_mpoly_init(k, ctx);
233
234 len = n_randint(state, 100);
235 len1 = n_randint(state, 100);
236 len2 = n_randint(state, 100) + 1;
237
238 exp_bound = n_randint(state, 1000/nvars/nvars) + 1;
239 exp_bound1 = n_randint(state, 1000/nvars/nvars) + 1;
240 exp_bound2 = n_randint(state, 1000/nvars/nvars) + 1;
241
242 coeff_bits = n_randint(state, 200);
243
244 for (j = 0; j < 4; j++)
245 {
246 fmpz_mpoly_randtest_bound(f, state, len1, coeff_bits, exp_bound1, ctx);
247 do {
248 fmpz_mpoly_randtest_bound(g, state, len2, coeff_bits + 1, exp_bound2, ctx);
249 } while (g->length == 0);
250 fmpz_mpoly_randtest_bound(h, state, len, coeff_bits, exp_bound, ctx);
251 fmpz_mpoly_randtest_bound(k, state, len, coeff_bits, exp_bound, ctx);
252
253 fmpz_mpoly_mul_johnson(h, f, g, ctx);
254 fmpz_mpoly_assert_canonical(h, ctx);
255
256 ok1 = fmpz_mpoly_divides_array(k, h, g, ctx);
257 fmpz_mpoly_assert_canonical(k, ctx);
258 ok2 = fmpz_mpoly_divides_array(g, h, g, ctx);
259 fmpz_mpoly_assert_canonical(g, ctx);
260
261 result = (ok1 == -1 && ok2 == -1) ||
262 (ok1 == 1 && ok2 == 1 && fmpz_mpoly_equal(g, k, ctx));
263
264 if (!result)
265 {
266 printf("FAIL\n");
267 flint_printf("Check aliasing second argument\ni = %wd, j = %wd\n", i, j);
268 flint_abort();
269 }
270 }
271
272 fmpz_mpoly_clear(f, ctx);
273 fmpz_mpoly_clear(g, ctx);
274 fmpz_mpoly_clear(h, ctx);
275 fmpz_mpoly_clear(k, ctx);
276 }
277
278 FLINT_TEST_CLEANUP(state);
279
280 flint_printf("PASS\n");
281 return 0;
282 }
283
284