1 /*
2 Copyright (C) 2018 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 <stdio.h>
13 #include <stdlib.h>
14 #include "nmod_mpoly.h"
15
16 int
main(void)17 main(void)
18 {
19 int i, j, result, ret;
20 FLINT_TEST_INIT(state);
21
22 flint_printf("divides_dense....");
23 fflush(stdout);
24
25 /* Check f*g/g = f */
26 for (i = 0; i < 50 * flint_test_multiplier(); i++)
27 {
28 nmod_mpoly_ctx_t ctx;
29 nmod_mpoly_t f, g, h, k;
30 slong len, len1, len2;
31 mp_limb_t max_bound, * exp_bound, * exp_bound1, * exp_bound2;
32 mp_limb_t modulus;
33
34 modulus = n_randint(state, (i % 4 == 0) ? 4: FLINT_BITS - 1) + 1;
35 modulus = n_randbits(state, modulus);
36 modulus = n_nextprime(modulus, 1);
37
38 nmod_mpoly_ctx_init_rand(ctx, state, 6, modulus);
39
40 nmod_mpoly_init(f, ctx);
41 nmod_mpoly_init(g, ctx);
42 nmod_mpoly_init(h, ctx);
43 nmod_mpoly_init(k, ctx);
44
45 len = n_randint(state, 100);
46 len1 = n_randint(state, 100);
47 len2 = n_randint(state, 100);
48
49 max_bound = 1 + 100/ctx->minfo->nvars/ctx->minfo->nvars;
50 exp_bound = (mp_limb_t *) flint_malloc(ctx->minfo->nvars*sizeof(mp_limb_t));
51 exp_bound1 = (mp_limb_t *) flint_malloc(ctx->minfo->nvars*sizeof(mp_limb_t));
52 exp_bound2 = (mp_limb_t *) flint_malloc(ctx->minfo->nvars*sizeof(mp_limb_t));
53 for (j = 0; j < ctx->minfo->nvars; j++)
54 {
55 exp_bound[j] = UWORD(1) << (FLINT_BITS - 1);
56 exp_bound1[j] = n_randint(state, max_bound) + 1;
57 exp_bound2[j] = n_randint(state, max_bound) + 1;
58 }
59
60 for (j = 0; j < 4; j++)
61 {
62 nmod_mpoly_randtest_bounds(f, state, len1, exp_bound1, ctx);
63 do {
64 nmod_mpoly_randtest_bounds(g, state, len2 + 1, exp_bound2, ctx);
65 } while (g->length == 0);
66 nmod_mpoly_randtest_bounds(h, state, len, exp_bound, ctx);
67 nmod_mpoly_randtest_bounds(k, state, len, exp_bound, ctx);
68
69 nmod_mpoly_mul(h, f, g, ctx);
70 nmod_mpoly_assert_canonical(h, ctx);
71 ret = nmod_mpoly_divides_dense(k, h, g, ctx);
72 if (ret == -1)
73 continue;
74 nmod_mpoly_assert_canonical(k, ctx);
75 result = (ret == 1) && nmod_mpoly_equal(k, f, ctx);
76
77 if (!result)
78 {
79 printf("FAIL\n");
80 flint_printf("Check f*g/g = f\ni = %wd, j = %wd\n", i ,j);
81 flint_abort();
82 }
83 }
84
85 flint_free(exp_bound);
86 flint_free(exp_bound1);
87 flint_free(exp_bound2);
88
89 nmod_mpoly_clear(f, ctx);
90 nmod_mpoly_clear(g, ctx);
91 nmod_mpoly_clear(h, ctx);
92 nmod_mpoly_clear(k, ctx);
93 nmod_mpoly_ctx_clear(ctx);
94 }
95
96 /* Check divisibility of random polys */
97 for (i = 0; i < 50 * flint_test_multiplier(); i++)
98 {
99 nmod_mpoly_ctx_t ctx;
100 nmod_mpoly_t f, g, h, k;
101 slong len, len1, len2;
102 mp_limb_t max_bound, * exp_bound, * exp_bound1, * exp_bound2;
103 mp_limb_t modulus;
104
105 modulus = n_randint(state, (i % 4 == 0) ? 4: FLINT_BITS - 1) + 1;
106 modulus = n_randbits(state, modulus);
107 modulus = n_nextprime(modulus, 1);
108
109 nmod_mpoly_ctx_init_rand(ctx, state, 6, modulus);
110
111 nmod_mpoly_init(f, ctx);
112 nmod_mpoly_init(g, ctx);
113 nmod_mpoly_init(h, ctx);
114 nmod_mpoly_init(k, ctx);
115
116 len = n_randint(state, 50);
117 len1 = n_randint(state, 50);
118 len2 = n_randint(state, 50);
119
120 max_bound = 1 + 20/ctx->minfo->nvars;
121 exp_bound = (mp_limb_t *) flint_malloc(ctx->minfo->nvars*sizeof(mp_limb_t));
122 exp_bound1 = (mp_limb_t *) flint_malloc(ctx->minfo->nvars*sizeof(mp_limb_t));
123 exp_bound2 = (mp_limb_t *) flint_malloc(ctx->minfo->nvars*sizeof(mp_limb_t));
124 for (j = 0; j < ctx->minfo->nvars; j++)
125 {
126 exp_bound[j] = UWORD(1) << (FLINT_BITS - 1);
127 exp_bound1[j] = n_randint(state, max_bound) + 1;
128 exp_bound2[j] = n_randint(state, max_bound) + 1;
129 }
130
131 for (j = 0; j < 4; j++)
132 {
133 nmod_mpoly_randtest_bounds(f, state, len1, exp_bound1, ctx);
134 do {
135 nmod_mpoly_randtest_bounds(g, state, len2 + 1, exp_bound2, ctx);
136 } while (g->length == 0);
137 nmod_mpoly_randtest_bounds(h, state, len, exp_bound, ctx);
138 nmod_mpoly_randtest_bounds(k, state, len, exp_bound, ctx);
139
140 ret = nmod_mpoly_divides_dense(h, f, g, ctx);
141 if (ret == -1 || ret == 0)
142 continue;
143 nmod_mpoly_assert_canonical(h, ctx);
144 nmod_mpoly_mul(k, h, g, ctx);
145 nmod_mpoly_assert_canonical(k, ctx);
146 result = nmod_mpoly_equal(k, f, ctx);
147 if (!result)
148 {
149 printf("FAIL\n");
150 flint_printf("Check divisibility of random polys\ni = %wd, j = %wd\n", i ,j);
151 flint_abort();
152 }
153 }
154
155 flint_free(exp_bound);
156 flint_free(exp_bound1);
157 flint_free(exp_bound2);
158
159 nmod_mpoly_clear(f, ctx);
160 nmod_mpoly_clear(g, ctx);
161 nmod_mpoly_clear(h, ctx);
162 nmod_mpoly_clear(k, ctx);
163 nmod_mpoly_ctx_clear(ctx);
164 }
165
166 /* Check f*g/g = f aliasing first argument */
167 for (i = 0; i < 20 * flint_test_multiplier(); i++)
168 {
169 nmod_mpoly_ctx_t ctx;
170 nmod_mpoly_t f, g, h, k;
171 slong len, len1, len2;
172 mp_limb_t max_bound, * exp_bound, * exp_bound1, * exp_bound2;
173 mp_limb_t modulus;
174
175 modulus = n_randint(state, (i % 4 == 0) ? 4: FLINT_BITS - 1) + 1;
176 modulus = n_randbits(state, modulus);
177 modulus = n_nextprime(modulus, 1);
178
179 nmod_mpoly_ctx_init_rand(ctx, state, 6, modulus);
180
181 nmod_mpoly_init(f, ctx);
182 nmod_mpoly_init(g, ctx);
183 nmod_mpoly_init(h, ctx);
184 nmod_mpoly_init(k, ctx);
185
186 len = n_randint(state, 100);
187 len1 = n_randint(state, 100);
188 len2 = n_randint(state, 100);
189
190 max_bound = 1 + 100/ctx->minfo->nvars/ctx->minfo->nvars;
191 exp_bound = (mp_limb_t *) flint_malloc(ctx->minfo->nvars*sizeof(mp_limb_t));
192 exp_bound1 = (mp_limb_t *) flint_malloc(ctx->minfo->nvars*sizeof(mp_limb_t));
193 exp_bound2 = (mp_limb_t *) flint_malloc(ctx->minfo->nvars*sizeof(mp_limb_t));
194 for (j = 0; j < ctx->minfo->nvars; j++)
195 {
196 exp_bound[j] = UWORD(1) << (FLINT_BITS - 1);
197 exp_bound1[j] = n_randint(state, max_bound) + 1;
198 exp_bound2[j] = n_randint(state, max_bound) + 1;
199 }
200
201 for (j = 0; j < 4; j++)
202 {
203 nmod_mpoly_randtest_bounds(f, state, len1, exp_bound1, ctx);
204 do {
205 nmod_mpoly_randtest_bounds(g, state, len2 + 1, exp_bound2, ctx);
206 } while (g->length == 0);
207 nmod_mpoly_randtest_bounds(h, state, len, exp_bound, ctx);
208 nmod_mpoly_randtest_bounds(k, state, len, exp_bound, ctx);
209
210 nmod_mpoly_set(h, f, ctx);
211 nmod_mpoly_mul(h, h, g, ctx);
212 nmod_mpoly_assert_canonical(h, ctx);
213 ret = nmod_mpoly_divides_dense(k, h, g, ctx);
214 if (ret == -1)
215 continue;
216 nmod_mpoly_assert_canonical(k, ctx);
217 result = (ret == 1) && nmod_mpoly_equal(k, f, ctx);
218
219 if (!result)
220 {
221 printf("FAIL\n");
222 flint_printf("Check f*g/g = f\ni = %wd, j = %wd\n", i ,j);
223 flint_abort();
224 }
225 }
226
227 flint_free(exp_bound);
228 flint_free(exp_bound1);
229 flint_free(exp_bound2);
230
231 nmod_mpoly_clear(f, ctx);
232 nmod_mpoly_clear(g, ctx);
233 nmod_mpoly_clear(h, ctx);
234 nmod_mpoly_clear(k, ctx);
235 nmod_mpoly_ctx_clear(ctx);
236 }
237
238 /* Check f*g/g = f aliasing second argument */
239 for (i = 0; i < 20 * flint_test_multiplier(); i++)
240 {
241 nmod_mpoly_ctx_t ctx;
242 nmod_mpoly_t f, g, h, k;
243 slong len, len1, len2;
244 mp_limb_t max_bound, * exp_bound, * exp_bound1, * exp_bound2;
245 mp_limb_t modulus;
246
247 modulus = n_randint(state, (i % 4 == 0) ? 4: FLINT_BITS - 1) + 1;
248 modulus = n_randbits(state, modulus);
249 modulus = n_nextprime(modulus, 1);
250
251 nmod_mpoly_ctx_init_rand(ctx, state, 6, modulus);
252
253 nmod_mpoly_init(f, ctx);
254 nmod_mpoly_init(g, ctx);
255 nmod_mpoly_init(h, ctx);
256 nmod_mpoly_init(k, ctx);
257
258 len = n_randint(state, 100);
259 len1 = n_randint(state, 100);
260 len2 = n_randint(state, 100);
261
262 max_bound = 1 + 100/ctx->minfo->nvars/ctx->minfo->nvars;
263 exp_bound = (mp_limb_t *) flint_malloc(ctx->minfo->nvars*sizeof(mp_limb_t));
264 exp_bound1 = (mp_limb_t *) flint_malloc(ctx->minfo->nvars*sizeof(mp_limb_t));
265 exp_bound2 = (mp_limb_t *) flint_malloc(ctx->minfo->nvars*sizeof(mp_limb_t));
266 for (j = 0; j < ctx->minfo->nvars; j++)
267 {
268 exp_bound[j] = UWORD(1) << (FLINT_BITS - 1);
269 exp_bound1[j] = n_randint(state, max_bound) + 1;
270 exp_bound2[j] = n_randint(state, max_bound) + 1;
271 }
272
273 for (j = 0; j < 4; j++)
274 {
275 nmod_mpoly_randtest_bounds(f, state, len1, exp_bound1, ctx);
276 do {
277 nmod_mpoly_randtest_bounds(g, state, len2 + 1, exp_bound2, ctx);
278 } while (g->length == 0);
279 nmod_mpoly_randtest_bounds(h, state, len, exp_bound, ctx);
280 nmod_mpoly_randtest_bounds(k, state, len, exp_bound, ctx);
281
282 nmod_mpoly_set(h, g, ctx);
283 nmod_mpoly_mul(h, f, h, ctx);
284 nmod_mpoly_assert_canonical(h, ctx);
285 ret = nmod_mpoly_divides_dense(k, h, g, ctx);
286 if (ret == -1)
287 continue;
288 nmod_mpoly_assert_canonical(k, ctx);
289 result = (ret == 1) && nmod_mpoly_equal(k, f, ctx);
290
291 if (!result)
292 {
293 printf("FAIL\n");
294 flint_printf("Check f*g/g = f aliasing second argument\ni = %wd, j = %wd\n", i ,j);
295 flint_abort();
296 }
297 }
298
299 flint_free(exp_bound);
300 flint_free(exp_bound1);
301 flint_free(exp_bound2);
302
303 nmod_mpoly_clear(f, ctx);
304 nmod_mpoly_clear(g, ctx);
305 nmod_mpoly_clear(h, ctx);
306 nmod_mpoly_clear(k, ctx);
307 nmod_mpoly_ctx_clear(ctx);
308 }
309
310 FLINT_TEST_CLEANUP(state);
311
312 flint_printf("PASS\n");
313 return 0;
314 }
315
316