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("divrem_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, r;
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 fmpz_mpoly_init(r, ctx);
48
49 len = n_randint(state, 100);
50 len1 = n_randint(state, 100);
51 len2 = n_randint(state, 100) + 1;
52
53 exp_bound = n_randint(state, 1000/nvars/nvars) + 1;
54 exp_bound1 = n_randint(state, 1000/nvars/nvars) + 1;
55 exp_bound2 = n_randint(state, 1000/nvars/nvars) + 1;
56
57 coeff_bits = n_randint(state, 200);
58
59 for (j = 0; j < 4; j++)
60 {
61 fmpz_mpoly_randtest_bound(f, state, len1, coeff_bits, exp_bound1, ctx);
62 do {
63 fmpz_mpoly_randtest_bound(g, state, len2, coeff_bits + 1, exp_bound2, ctx);
64 } while (g->length == 0);
65 fmpz_mpoly_randtest_bound(h, state, len, coeff_bits, exp_bound, ctx);
66 fmpz_mpoly_randtest_bound(k, state, len, coeff_bits, exp_bound, ctx);
67 fmpz_mpoly_randtest_bound(r, state, len, coeff_bits, exp_bound, ctx);
68
69 fmpz_mpoly_mul_johnson(h, f, g, ctx);
70 fmpz_mpoly_assert_canonical(h, ctx);
71
72 ok1 = fmpz_mpoly_divrem_array(k, r, h, g, ctx);
73 if (ok1)
74 fmpz_mpoly_remainder_test(r, g, ctx);
75
76 result = (ok1 == 0) || (ok1 && fmpz_mpoly_equal(f, k, ctx));
77
78 if (!result)
79 {
80 printf("FAIL\n");
81 flint_printf("Check f*g/g = f\ni = %wd, j = %wd\n", i, j);
82 flint_abort();
83 }
84 }
85
86 fmpz_mpoly_clear(f, ctx);
87 fmpz_mpoly_clear(g, ctx);
88 fmpz_mpoly_clear(h, ctx);
89 fmpz_mpoly_clear(k, ctx);
90 fmpz_mpoly_clear(r, ctx);
91 }
92
93 /* Check f = g*q + r for random polys */
94 for (i = 0; i < 10 * flint_test_multiplier(); i++)
95 {
96 fmpz_mpoly_ctx_t ctx;
97 fmpz_mpoly_t f, g, h, k, r;
98 ordering_t ord;
99 slong nvars, len, len1, len2, exp_bound, exp_bound1, exp_bound2;
100 slong coeff_bits;
101
102 ord = mpoly_ordering_randtest(state);
103
104 nvars = n_randint(state, 10) + 1;
105
106 fmpz_mpoly_ctx_init(ctx, nvars, ord);
107
108 fmpz_mpoly_init(f, ctx);
109 fmpz_mpoly_init(g, ctx);
110 fmpz_mpoly_init(h, ctx);
111 fmpz_mpoly_init(k, ctx);
112 fmpz_mpoly_init(r, ctx);
113
114 len = n_randint(state, 16);
115 len1 = n_randint(state, 16);
116 len2 = n_randint(state, 16) + 1;
117
118 exp_bound = n_randint(state, 1000/nvars/nvars) + 1;
119 exp_bound1 = n_randint(state, 1000/nvars/nvars) + 1;
120 exp_bound2 = n_randint(state, 1000/nvars/nvars) + 1;
121
122 coeff_bits = n_randint(state, 70);
123
124 for (j = 0; j < 4; j++)
125 {
126 fmpz_mpoly_randtest_bound(f, state, len1, coeff_bits, exp_bound1, ctx);
127 do {
128 fmpz_mpoly_randtest_bound(g, state, len2, coeff_bits + 1, exp_bound2, ctx);
129 } while (g->length == 0);
130 fmpz_mpoly_randtest_bound(h, state, len, coeff_bits, exp_bound, ctx);
131 fmpz_mpoly_randtest_bound(k, state, len, coeff_bits, exp_bound, ctx);
132
133 ok1 = fmpz_mpoly_divrem_array(h, r, f, g, ctx);
134 fmpz_mpoly_assert_canonical(h, ctx);
135 fmpz_mpoly_assert_canonical(r, ctx);
136 if (ok1)
137 {
138 fmpz_mpoly_remainder_test(r, g, ctx);
139 fmpz_mpoly_mul_johnson(k, h, g, ctx);
140 fmpz_mpoly_add(k, k, r, ctx);
141 }
142
143 result = (ok1 == 0) || (ok1 == 1 && fmpz_mpoly_equal(f, k, ctx));
144
145 if (!result)
146 {
147 printf("FAIL\n");
148 flint_printf("Check f = g*q + r for random polys\ni = %wd, j = %wd\n", i, j);
149 flint_abort();
150 }
151 }
152
153 fmpz_mpoly_clear(f, ctx);
154 fmpz_mpoly_clear(g, ctx);
155 fmpz_mpoly_clear(h, ctx);
156 fmpz_mpoly_clear(k, ctx);
157 fmpz_mpoly_clear(r, ctx);
158 }
159
160 /* Check aliasing of quotient with first argument */
161 for (i = 0; i < 5 * flint_test_multiplier(); i++)
162 {
163 fmpz_mpoly_ctx_t ctx;
164 fmpz_mpoly_t f, g, h, r1, r2;
165 ordering_t ord;
166 slong nvars, len, len1, len2, exp_bound, exp_bound1, exp_bound2;
167 slong coeff_bits;
168
169 ord = mpoly_ordering_randtest(state);
170 nvars = n_randint(state, 10) + 1;
171
172 fmpz_mpoly_ctx_init(ctx, nvars, ord);
173
174 fmpz_mpoly_init(f, ctx);
175 fmpz_mpoly_init(g, ctx);
176 fmpz_mpoly_init(h, ctx);
177 fmpz_mpoly_init(r1, ctx);
178 fmpz_mpoly_init(r2, ctx);
179
180 len = n_randint(state, 16);
181 len1 = n_randint(state, 16);
182 len2 = n_randint(state, 16) + 1;
183
184 exp_bound = n_randint(state, 1000/nvars/nvars) + 1;
185 exp_bound1 = n_randint(state, 1000/nvars/nvars) + 1;
186 exp_bound2 = n_randint(state, 1000/nvars/nvars) + 1;
187
188 coeff_bits = n_randint(state, 70);
189
190 for (j = 0; j < 4; j++)
191 {
192 fmpz_mpoly_randtest_bound(f, state, len1, coeff_bits, exp_bound1, ctx);
193 do {
194 fmpz_mpoly_randtest_bound(g, state, len2, coeff_bits + 1, exp_bound2, ctx);
195 } while (g->length == 0);
196 fmpz_mpoly_randtest_bound(h, state, len, coeff_bits, exp_bound, ctx);
197 fmpz_mpoly_randtest_bound(r1, state, len, coeff_bits, exp_bound, ctx);
198 fmpz_mpoly_randtest_bound(r2, state, len, coeff_bits, exp_bound, ctx);
199
200 ok1 = fmpz_mpoly_divrem_array(h, r1, f, g, ctx);
201 fmpz_mpoly_assert_canonical(h, ctx);
202 fmpz_mpoly_assert_canonical(r1, ctx);
203 if (ok1)
204 fmpz_mpoly_remainder_test(r1, g, ctx);
205
206 ok2 = fmpz_mpoly_divrem_array(f, r2, f, g, ctx);
207 fmpz_mpoly_assert_canonical(f, ctx);
208 fmpz_mpoly_assert_canonical(r2, ctx);
209 if (ok2)
210 fmpz_mpoly_remainder_test(r2, g, ctx);
211
212 result = (ok1 == 0 || ok2 == 0) ||
213 (ok1 == 1 && ok2 == 1 && fmpz_mpoly_equal(h, f, ctx)
214 && fmpz_mpoly_equal(r1, r2, ctx));
215
216 if (!result)
217 {
218 printf("FAIL\n");
219 flint_printf("Check aliasing of quotient with first argument\ni = %wd, j = %wd\n", i, j);
220 flint_abort();
221 }
222 }
223
224 fmpz_mpoly_clear(f, ctx);
225 fmpz_mpoly_clear(g, ctx);
226 fmpz_mpoly_clear(h, ctx);
227 fmpz_mpoly_clear(r1, ctx);
228 fmpz_mpoly_clear(r2, ctx);
229 }
230
231 /* Check aliasing of quotient with second argument */
232 for (i = 0; i < 5 * flint_test_multiplier(); i++)
233 {
234 fmpz_mpoly_ctx_t ctx;
235 fmpz_mpoly_t f, g, h, r1, r2;
236 ordering_t ord;
237 slong nvars, len, len1, len2, exp_bound, exp_bound1, exp_bound2;
238 slong coeff_bits;
239
240 ord = mpoly_ordering_randtest(state);
241 nvars = n_randint(state, 10) + 1;
242
243 fmpz_mpoly_ctx_init(ctx, nvars, ord);
244
245 fmpz_mpoly_init(f, ctx);
246 fmpz_mpoly_init(g, ctx);
247 fmpz_mpoly_init(h, ctx);
248 fmpz_mpoly_init(r1, ctx);
249 fmpz_mpoly_init(r2, ctx);
250
251 len = n_randint(state, 16);
252 len1 = n_randint(state, 16);
253 len2 = n_randint(state, 16) + 1;
254
255 exp_bound = n_randint(state, 1000/nvars/nvars) + 1;
256 exp_bound1 = n_randint(state, 1000/nvars/nvars) + 1;
257 exp_bound2 = n_randint(state, 1000/nvars/nvars) + 1;
258
259 coeff_bits = n_randint(state, 70);
260
261 for (j = 0; j < 4; j++)
262 {
263 fmpz_mpoly_randtest_bound(f, state, len1, coeff_bits, exp_bound1, ctx);
264 do {
265 fmpz_mpoly_randtest_bound(g, state, len2, exp_bound2, coeff_bits + 1, ctx);
266 } while (g->length == 0);
267 fmpz_mpoly_randtest_bound(h, state, len, coeff_bits, exp_bound, ctx);
268 fmpz_mpoly_randtest_bound(r1, state, len, coeff_bits, exp_bound, ctx);
269 fmpz_mpoly_randtest_bound(r2, state, len, coeff_bits, exp_bound, ctx);
270
271 ok1 = fmpz_mpoly_divrem_array(h, r1, f, g, ctx);
272 fmpz_mpoly_assert_canonical(h, ctx);
273 fmpz_mpoly_assert_canonical(r1, ctx);
274 if (ok1)
275 fmpz_mpoly_remainder_test(r1, g, ctx);
276
277 ok2 = fmpz_mpoly_divrem_array(g, r2, f, g, ctx);
278 fmpz_mpoly_assert_canonical(g, ctx);
279 fmpz_mpoly_assert_canonical(r2, ctx);
280
281 result = (ok1 == 0 || ok2 == 0) ||
282 (ok1 == 1 && ok2 == 1 && fmpz_mpoly_equal(h, g, ctx)
283 && fmpz_mpoly_equal(r1, r2, ctx));
284
285 if (!result)
286 {
287 printf("FAIL\n");
288 flint_printf("Check aliasing of quotient with second argument\ni = %wd, j = %wd\n", i, j);
289 flint_abort();
290 }
291 }
292
293 fmpz_mpoly_clear(f, ctx);
294 fmpz_mpoly_clear(g, ctx);
295 fmpz_mpoly_clear(h, ctx);
296 fmpz_mpoly_clear(r1, ctx);
297 fmpz_mpoly_clear(r2, ctx);
298 }
299
300 /* Check aliasing of remainder with first argument */
301 for (i = 0; i < 5 * flint_test_multiplier(); i++)
302 {
303 fmpz_mpoly_ctx_t ctx;
304 fmpz_mpoly_t f, g, h, k, r1;
305 ordering_t ord;
306 slong nvars, len, len1, len2, exp_bound, exp_bound1, exp_bound2;
307 slong coeff_bits;
308
309 ord = mpoly_ordering_randtest(state);
310 nvars = n_randint(state, 10) + 1;
311
312 fmpz_mpoly_ctx_init(ctx, nvars, ord);
313
314 fmpz_mpoly_init(f, ctx);
315 fmpz_mpoly_init(g, ctx);
316 fmpz_mpoly_init(h, ctx);
317 fmpz_mpoly_init(k, ctx);
318 fmpz_mpoly_init(r1, ctx);
319
320 len = n_randint(state, 16);
321 len1 = n_randint(state, 16);
322 len2 = n_randint(state, 16) + 1;
323
324 exp_bound = n_randint(state, 1000/nvars/nvars) + 1;
325 exp_bound1 = n_randint(state, 1000/nvars/nvars) + 1;
326 exp_bound2 = n_randint(state, 1000/nvars/nvars) + 1;
327
328 coeff_bits = n_randint(state, 70);
329
330 for (j = 0; j < 4; j++)
331 {
332 fmpz_mpoly_randtest_bound(f, state, len1, coeff_bits, exp_bound1, ctx);
333 do {
334 fmpz_mpoly_randtest_bound(g, state, len2, coeff_bits + 1, exp_bound2, ctx);
335 } while (g->length == 0);
336 fmpz_mpoly_randtest_bound(h, state, len, coeff_bits, exp_bound, ctx);
337 fmpz_mpoly_randtest_bound(k, state, len, coeff_bits, exp_bound, ctx);
338 fmpz_mpoly_randtest_bound(r1, state, len, coeff_bits, exp_bound, ctx);
339
340 fmpz_mpoly_mul_johnson(h, f, g, ctx);
341 fmpz_mpoly_assert_canonical(h, ctx);
342
343 ok1 = fmpz_mpoly_divrem_array(h, r1, f, g, ctx);
344 fmpz_mpoly_assert_canonical(h, ctx);
345 fmpz_mpoly_assert_canonical(r1, ctx);
346 if (ok1)
347 fmpz_mpoly_remainder_test(r1, g, ctx);
348
349 ok2 = fmpz_mpoly_divrem_array(k, f, f, g, ctx);
350 fmpz_mpoly_assert_canonical(k, ctx);
351 fmpz_mpoly_assert_canonical(f, ctx);
352 if (ok2)
353 fmpz_mpoly_remainder_test(f, g, ctx);
354
355 result = (ok1 == 0 || ok2 == 0) ||
356 (ok1 == 1 && ok2 == 1 && fmpz_mpoly_equal(h, k, ctx)
357 && fmpz_mpoly_equal(r1, f, ctx));
358
359 if (!result)
360 {
361 printf("FAIL\n");
362 flint_printf("Check aliasing of remainder with first argument\ni = %wd, j = %wd\n", i, j);
363 flint_abort();
364 }
365 }
366
367 fmpz_mpoly_clear(f, ctx);
368 fmpz_mpoly_clear(g, ctx);
369 fmpz_mpoly_clear(h, ctx);
370 fmpz_mpoly_clear(k, ctx);
371 fmpz_mpoly_clear(r1, ctx);
372 }
373
374 /* Check aliasing of remainder with second argument */
375 for (i = 0; i < 5 * flint_test_multiplier(); i++)
376 {
377 fmpz_mpoly_ctx_t ctx;
378 fmpz_mpoly_t f, g, h, k, r1;
379 ordering_t ord;
380 slong nvars, len, len1, len2, exp_bound, exp_bound1, exp_bound2;
381 slong coeff_bits;
382
383 ord = mpoly_ordering_randtest(state);
384 nvars = n_randint(state, 10) + 1;
385
386 fmpz_mpoly_ctx_init(ctx, nvars, ord);
387
388 fmpz_mpoly_init(f, ctx);
389 fmpz_mpoly_init(g, ctx);
390 fmpz_mpoly_init(h, ctx);
391 fmpz_mpoly_init(k, ctx);
392 fmpz_mpoly_init(r1, ctx);
393
394 len = n_randint(state, 16);
395 len1 = n_randint(state, 16);
396 len2 = n_randint(state, 16) + 1;
397
398 exp_bound = n_randint(state, 1000/nvars/nvars) + 1;
399 exp_bound1 = n_randint(state, 1000/nvars/nvars) + 1;
400 exp_bound2 = n_randint(state, 1000/nvars/nvars) + 1;
401
402 coeff_bits = n_randint(state, 70);
403
404 for (j = 0; j < 4; j++)
405 {
406 fmpz_mpoly_randtest_bound(f, state, len1, coeff_bits, exp_bound1, ctx);
407 do {
408 fmpz_mpoly_randtest_bound(g, state, len2, coeff_bits + 1, exp_bound2, ctx);
409 } while (g->length == 0);
410 fmpz_mpoly_randtest_bound(h, state, len, coeff_bits, exp_bound, ctx);
411 fmpz_mpoly_randtest_bound(k, state, len, coeff_bits, exp_bound, ctx);
412 fmpz_mpoly_randtest_bound(r1, state, len, coeff_bits, exp_bound, ctx);
413
414 fmpz_mpoly_mul_johnson(h, f, g, ctx);
415 fmpz_mpoly_assert_canonical(h, ctx);
416
417 ok1 = fmpz_mpoly_divrem_array(h, r1, f, g, ctx);
418 fmpz_mpoly_assert_canonical(h, ctx);
419 fmpz_mpoly_assert_canonical(r1, ctx);
420 if (ok1)
421 fmpz_mpoly_remainder_test(r1, g, ctx);
422
423 ok2 = fmpz_mpoly_divrem_array(k, g, f, g, ctx);
424 fmpz_mpoly_assert_canonical(k, ctx);
425 fmpz_mpoly_assert_canonical(g, ctx);
426
427 result = (ok1 == 0 || ok2 == 0) ||
428 (ok1 == 1 && ok2 == 1 && fmpz_mpoly_equal(h, k, ctx)
429 && fmpz_mpoly_equal(r1, g, ctx));
430
431 if (!result)
432 {
433 printf("FAIL\n");
434 flint_printf("Check aliasing of remainder with second argument\ni = %wd, j = %wd\n", i, j);
435 flint_abort();
436 }
437 }
438
439 fmpz_mpoly_clear(f, ctx);
440 fmpz_mpoly_clear(g, ctx);
441 fmpz_mpoly_clear(h, ctx);
442 fmpz_mpoly_clear(k, ctx);
443 fmpz_mpoly_clear(r1, ctx);
444 }
445
446 FLINT_TEST_CLEANUP(state);
447
448 flint_printf("PASS\n");
449 return 0;
450 }
451
452