1 /*
2 Copyright (C) 2012 Sebastian Pancratz
3 Copyright (C) 2013 Mike Hansen
4
5 This file is part of FLINT.
6
7 FLINT is free software: you can redistribute it and/or modify it under
8 the terms of the GNU Lesser General Public License (LGPL) as published
9 by the Free Software Foundation; either version 2.1 of the License, or
10 (at your option) any later version. See <https://www.gnu.org/licenses/>.
11 */
12
13 #ifdef T
14
15 #include "templates.h"
16
17 int
main(void)18 main(void)
19 {
20 int i, result;
21 FLINT_TEST_INIT(state);
22
23 flint_printf("xgcd_euclidean....");
24 fflush(stdout);
25
26 /* Generic case, most likely co-prime arguments ***************************** */
27
28 /* Compare with result from GCD and check correctness */
29 for (i = 0; i < 5 * flint_test_multiplier(); i++)
30 {
31 TEMPLATE(T, ctx_t) ctx;
32 TEMPLATE(T, poly_t) a, b, d, g, s, t, v, w;
33
34 TEMPLATE(T, ctx_randtest) (ctx, state);
35
36 TEMPLATE(T, poly_init) (a, ctx);
37 TEMPLATE(T, poly_init) (b, ctx);
38 TEMPLATE(T, poly_init) (d, ctx);
39 TEMPLATE(T, poly_init) (g, ctx);
40 TEMPLATE(T, poly_init) (s, ctx);
41 TEMPLATE(T, poly_init) (t, ctx);
42 TEMPLATE(T, poly_init) (v, ctx);
43 TEMPLATE(T, poly_init) (w, ctx);
44 TEMPLATE(T, poly_randtest) (a, state, n_randint(state, 100), ctx);
45 TEMPLATE(T, poly_randtest) (b, state, n_randint(state, 100), ctx);
46
47 TEMPLATE(T, poly_gcd_euclidean) (d, a, b, ctx);
48 TEMPLATE(T, poly_xgcd_euclidean) (g, s, t, a, b, ctx);
49
50 TEMPLATE(T, poly_mul) (v, s, a, ctx);
51 TEMPLATE(T, poly_mul) (w, t, b, ctx);
52 TEMPLATE(T, poly_add) (w, v, w, ctx);
53
54 result = (TEMPLATE(T, poly_equal) (d, g, ctx) &&
55 TEMPLATE(T, poly_equal) (g, w, ctx));
56
57 if (!result)
58 {
59 flint_printf("FAIL:\n");
60 TEMPLATE(T, poly_print_pretty) (a, "x", ctx), flint_printf("\n\n");
61 TEMPLATE(T, poly_print_pretty) (b, "x", ctx), flint_printf("\n\n");
62 TEMPLATE(T, poly_print_pretty) (d, "x", ctx), flint_printf("\n\n");
63 TEMPLATE(T, poly_print_pretty) (g, "x", ctx), flint_printf("\n\n");
64 TEMPLATE(T, poly_print_pretty) (s, "x", ctx), flint_printf("\n\n");
65 TEMPLATE(T, poly_print_pretty) (t, "x", ctx), flint_printf("\n\n");
66 TEMPLATE(T, poly_print_pretty) (v, "x", ctx), flint_printf("\n\n");
67 TEMPLATE(T, poly_print_pretty) (w, "x", ctx), flint_printf("\n\n");
68 abort();
69 }
70
71 TEMPLATE(T, poly_clear) (a, ctx);
72 TEMPLATE(T, poly_clear) (b, ctx);
73 TEMPLATE(T, poly_clear) (d, ctx);
74 TEMPLATE(T, poly_clear) (g, ctx);
75 TEMPLATE(T, poly_clear) (s, ctx);
76 TEMPLATE(T, poly_clear) (t, ctx);
77 TEMPLATE(T, poly_clear) (v, ctx);
78 TEMPLATE(T, poly_clear) (w, ctx);
79 TEMPLATE(T, ctx_clear) (ctx);
80 }
81
82 /* Special case, arguments share a factor ******************************* */
83
84 /* Compare with result from GCD and check correctness */
85 for (i = 0; i < 50 * flint_test_multiplier(); i++)
86 {
87 TEMPLATE(T, ctx_t) ctx;
88 TEMPLATE(T, poly_t) a, b, d, f, g, s, t, v, w;
89
90 TEMPLATE(T, ctx_randtest) (ctx, state);
91
92 TEMPLATE(T, poly_init) (a, ctx);
93 TEMPLATE(T, poly_init) (b, ctx);
94 TEMPLATE(T, poly_init) (d, ctx);
95 TEMPLATE(T, poly_init) (f, ctx);
96 TEMPLATE(T, poly_init) (g, ctx);
97 TEMPLATE(T, poly_init) (s, ctx);
98 TEMPLATE(T, poly_init) (t, ctx);
99 TEMPLATE(T, poly_init) (v, ctx);
100 TEMPLATE(T, poly_init) (w, ctx);
101 TEMPLATE(T, poly_randtest) (s, state, n_randint(state, 10), ctx);
102 TEMPLATE(T, poly_randtest) (t, state, n_randint(state, 10), ctx);
103 TEMPLATE(T, poly_randtest) (a, state, n_randint(state, 10), ctx);
104 TEMPLATE(T, poly_randtest) (b, state, n_randint(state, 10), ctx);
105 TEMPLATE(T, poly_randtest) (f, state, n_randint(state, 5), ctx);
106 TEMPLATE(T, poly_mul) (a, a, f, ctx);
107 TEMPLATE(T, poly_mul) (b, b, f, ctx);
108
109 TEMPLATE(T, poly_gcd_euclidean) (d, a, b, ctx);
110 TEMPLATE(T, poly_xgcd_euclidean) (g, s, t, a, b, ctx);
111
112 TEMPLATE(T, poly_mul) (v, s, a, ctx);
113 TEMPLATE(T, poly_mul) (w, t, b, ctx);
114 TEMPLATE(T, poly_add) (w, v, w, ctx);
115
116 result = (TEMPLATE(T, poly_equal) (d, g, ctx) &&
117 TEMPLATE(T, poly_equal) (g, w, ctx));
118 if (!result)
119 {
120 flint_printf("FAIL:\n");
121 TEMPLATE(T, poly_print_pretty) (a, "x", ctx);
122 flint_printf("\n\n");
123 TEMPLATE(T, poly_print_pretty) (b, "x", ctx);
124 flint_printf("\n\n");
125 TEMPLATE(T, poly_print_pretty) (d, "x", ctx);
126 flint_printf("\n\n");
127 TEMPLATE(T, poly_print_pretty) (f, "x", ctx);
128 flint_printf("\n\n");
129 TEMPLATE(T, poly_print_pretty) (g, "x", ctx);
130 flint_printf("\n\n");
131 TEMPLATE(T, poly_print_pretty) (s, "x", ctx);
132 flint_printf("\n\n");
133 TEMPLATE(T, poly_print_pretty) (t, "x", ctx);
134 flint_printf("\n\n");
135 TEMPLATE(T, poly_print_pretty) (v, "x", ctx);
136 flint_printf("\n\n");
137 TEMPLATE(T, poly_print_pretty) (w, "x", ctx);
138 flint_printf("\n\n");
139 abort();
140 }
141
142 TEMPLATE(T, poly_clear) (a, ctx);
143 TEMPLATE(T, poly_clear) (b, ctx);
144 TEMPLATE(T, poly_clear) (d, ctx);
145 TEMPLATE(T, poly_clear) (f, ctx);
146 TEMPLATE(T, poly_clear) (g, ctx);
147 TEMPLATE(T, poly_clear) (s, ctx);
148 TEMPLATE(T, poly_clear) (t, ctx);
149 TEMPLATE(T, poly_clear) (v, ctx);
150 TEMPLATE(T, poly_clear) (w, ctx);
151 TEMPLATE(T, ctx_clear) (ctx);
152 }
153
154 /* test aliasing of g and a */
155 for (i = 0; i < 5 * flint_test_multiplier(); i++)
156 {
157 TEMPLATE(T, ctx_t) ctx;
158 TEMPLATE(T, poly_t) a, b, g, s, t, v, w;
159
160 TEMPLATE(T, ctx_randtest) (ctx, state);
161
162 TEMPLATE(T, poly_init) (a, ctx);
163 TEMPLATE(T, poly_init) (b, ctx);
164 TEMPLATE(T, poly_init) (g, ctx);
165 TEMPLATE(T, poly_init) (s, ctx);
166 TEMPLATE(T, poly_init) (t, ctx);
167 TEMPLATE(T, poly_init) (v, ctx);
168 TEMPLATE(T, poly_init) (w, ctx);
169 TEMPLATE(T, poly_randtest) (a, state, n_randint(state, 100), ctx);
170 TEMPLATE(T, poly_randtest) (b, state, n_randint(state, 100), ctx);
171
172 TEMPLATE(T, poly_xgcd_euclidean) (g, s, t, a, b, ctx);
173 TEMPLATE(T, poly_xgcd_euclidean) (a, v, w, a, b, ctx);
174
175 result = (TEMPLATE(T, poly_equal) (s, v, ctx) &&
176 TEMPLATE(T, poly_equal) (t, w, ctx) &&
177 TEMPLATE(T, poly_equal) (g, a, ctx));
178
179 if (!result)
180 {
181 flint_printf("FAIL:\n");
182 TEMPLATE(T, poly_print_pretty) (a, "x", ctx), flint_printf("\n\n");
183 TEMPLATE(T, poly_print_pretty) (b, "x", ctx), flint_printf("\n\n");
184 TEMPLATE(T, poly_print_pretty) (g, "x", ctx), flint_printf("\n\n");
185 TEMPLATE(T, poly_print_pretty) (s, "x", ctx), flint_printf("\n\n");
186 TEMPLATE(T, poly_print_pretty) (t, "x", ctx), flint_printf("\n\n");
187 TEMPLATE(T, poly_print_pretty) (v, "x", ctx), flint_printf("\n\n");
188 TEMPLATE(T, poly_print_pretty) (w, "x", ctx), flint_printf("\n\n");
189 abort();
190 }
191
192 TEMPLATE(T, poly_clear) (a, ctx);
193 TEMPLATE(T, poly_clear) (b, ctx);
194 TEMPLATE(T, poly_clear) (g, ctx);
195 TEMPLATE(T, poly_clear) (s, ctx);
196 TEMPLATE(T, poly_clear) (t, ctx);
197 TEMPLATE(T, poly_clear) (v, ctx);
198 TEMPLATE(T, poly_clear) (w, ctx);
199 TEMPLATE(T, ctx_clear) (ctx);
200 }
201
202 /* test aliasing of g and b */
203 for (i = 0; i < 5 * flint_test_multiplier(); i++)
204 {
205 TEMPLATE(T, ctx_t) ctx;
206 TEMPLATE(T, poly_t) a, b, g, s, t, v, w;
207
208 TEMPLATE(T, ctx_randtest) (ctx, state);
209
210 TEMPLATE(T, poly_init) (a, ctx);
211 TEMPLATE(T, poly_init) (b, ctx);
212 TEMPLATE(T, poly_init) (g, ctx);
213 TEMPLATE(T, poly_init) (s, ctx);
214 TEMPLATE(T, poly_init) (t, ctx);
215 TEMPLATE(T, poly_init) (v, ctx);
216 TEMPLATE(T, poly_init) (w, ctx);
217 TEMPLATE(T, poly_randtest) (a, state, n_randint(state, 100), ctx);
218 TEMPLATE(T, poly_randtest) (b, state, n_randint(state, 100), ctx);
219
220 TEMPLATE(T, poly_xgcd_euclidean) (g, s, t, a, b, ctx);
221 TEMPLATE(T, poly_xgcd_euclidean) (b, v, w, a, b, ctx);
222
223 result = (TEMPLATE(T, poly_equal) (s, v, ctx) &&
224 TEMPLATE(T, poly_equal) (t, w, ctx) &&
225 TEMPLATE(T, poly_equal) (g, b, ctx));
226
227 if (!result)
228 {
229 flint_printf("FAIL:\n");
230 TEMPLATE(T, poly_print_pretty) (a, "x", ctx), flint_printf("\n\n");
231 TEMPLATE(T, poly_print_pretty) (b, "x", ctx), flint_printf("\n\n");
232 TEMPLATE(T, poly_print_pretty) (g, "x", ctx), flint_printf("\n\n");
233 TEMPLATE(T, poly_print_pretty) (s, "x", ctx), flint_printf("\n\n");
234 TEMPLATE(T, poly_print_pretty) (t, "x", ctx), flint_printf("\n\n");
235 TEMPLATE(T, poly_print_pretty) (v, "x", ctx), flint_printf("\n\n");
236 TEMPLATE(T, poly_print_pretty) (w, "x", ctx), flint_printf("\n\n");
237 abort();
238 }
239
240 TEMPLATE(T, poly_clear) (a, ctx);
241 TEMPLATE(T, poly_clear) (b, ctx);
242 TEMPLATE(T, poly_clear) (g, ctx);
243 TEMPLATE(T, poly_clear) (s, ctx);
244 TEMPLATE(T, poly_clear) (t, ctx);
245 TEMPLATE(T, poly_clear) (v, ctx);
246 TEMPLATE(T, poly_clear) (w, ctx);
247 TEMPLATE(T, ctx_clear) (ctx);
248 }
249
250 /* test aliasing of s and a */
251 for (i = 0; i < 5 * flint_test_multiplier(); i++)
252 {
253 TEMPLATE(T, ctx_t) ctx;
254 TEMPLATE(T, poly_t) a, b, d, g, s, t, w;
255
256 TEMPLATE(T, ctx_randtest) (ctx, state);
257
258 TEMPLATE(T, poly_init) (a, ctx);
259 TEMPLATE(T, poly_init) (b, ctx);
260 TEMPLATE(T, poly_init) (g, ctx);
261 TEMPLATE(T, poly_init) (s, ctx);
262 TEMPLATE(T, poly_init) (t, ctx);
263 TEMPLATE(T, poly_init) (d, ctx);
264 TEMPLATE(T, poly_init) (w, ctx);
265 TEMPLATE(T, poly_randtest) (a, state, n_randint(state, 100), ctx);
266 TEMPLATE(T, poly_randtest) (b, state, n_randint(state, 100), ctx);
267
268 TEMPLATE(T, poly_xgcd_euclidean) (g, s, t, a, b, ctx);
269 TEMPLATE(T, poly_xgcd_euclidean) (d, a, w, a, b, ctx);
270
271 result = (TEMPLATE(T, poly_equal) (s, a, ctx) &&
272 TEMPLATE(T, poly_equal) (t, w, ctx) &&
273 TEMPLATE(T, poly_equal) (g, d, ctx));
274
275 if (!result)
276 {
277 flint_printf("FAIL:\n");
278 TEMPLATE(T, poly_print_pretty) (a, "x", ctx), flint_printf("\n\n");
279 TEMPLATE(T, poly_print_pretty) (b, "x", ctx), flint_printf("\n\n");
280 TEMPLATE(T, poly_print_pretty) (g, "x", ctx), flint_printf("\n\n");
281 TEMPLATE(T, poly_print_pretty) (s, "x", ctx), flint_printf("\n\n");
282 TEMPLATE(T, poly_print_pretty) (t, "x", ctx), flint_printf("\n\n");
283 TEMPLATE(T, poly_print_pretty) (d, "x", ctx), flint_printf("\n\n");
284 TEMPLATE(T, poly_print_pretty) (w, "x", ctx), flint_printf("\n\n");
285 abort();
286 }
287
288 TEMPLATE(T, poly_clear) (a, ctx);
289 TEMPLATE(T, poly_clear) (b, ctx);
290 TEMPLATE(T, poly_clear) (g, ctx);
291 TEMPLATE(T, poly_clear) (s, ctx);
292 TEMPLATE(T, poly_clear) (t, ctx);
293 TEMPLATE(T, poly_clear) (d, ctx);
294 TEMPLATE(T, poly_clear) (w, ctx);
295 TEMPLATE(T, ctx_clear) (ctx);
296 }
297
298 /* test aliasing of s and b */
299 for (i = 0; i < 5 * flint_test_multiplier(); i++)
300 {
301 TEMPLATE(T, ctx_t) ctx;
302 TEMPLATE(T, poly_t) a, b, d, g, s, t, w;
303
304 TEMPLATE(T, ctx_randtest) (ctx, state);
305
306 TEMPLATE(T, poly_init) (a, ctx);
307 TEMPLATE(T, poly_init) (b, ctx);
308 TEMPLATE(T, poly_init) (g, ctx);
309 TEMPLATE(T, poly_init) (s, ctx);
310 TEMPLATE(T, poly_init) (t, ctx);
311 TEMPLATE(T, poly_init) (d, ctx);
312 TEMPLATE(T, poly_init) (w, ctx);
313 TEMPLATE(T, poly_randtest) (a, state, n_randint(state, 100), ctx);
314 TEMPLATE(T, poly_randtest) (b, state, n_randint(state, 100), ctx);
315
316 TEMPLATE(T, poly_xgcd_euclidean) (g, s, t, a, b, ctx);
317 TEMPLATE(T, poly_xgcd_euclidean) (d, b, w, a, b, ctx);
318
319 result = (TEMPLATE(T, poly_equal) (s, b, ctx) &&
320 TEMPLATE(T, poly_equal) (t, w, ctx) &&
321 TEMPLATE(T, poly_equal) (g, d, ctx));
322
323 if (!result)
324 {
325 flint_printf("FAIL:\n");
326 TEMPLATE(T, poly_print_pretty) (a, "x", ctx), flint_printf("\n\n");
327 TEMPLATE(T, poly_print_pretty) (b, "x", ctx), flint_printf("\n\n");
328 TEMPLATE(T, poly_print_pretty) (g, "x", ctx), flint_printf("\n\n");
329 TEMPLATE(T, poly_print_pretty) (s, "x", ctx), flint_printf("\n\n");
330 TEMPLATE(T, poly_print_pretty) (t, "x", ctx), flint_printf("\n\n");
331 TEMPLATE(T, poly_print_pretty) (d, "x", ctx), flint_printf("\n\n");
332 TEMPLATE(T, poly_print_pretty) (w, "x", ctx), flint_printf("\n\n");
333 abort();
334 }
335
336 TEMPLATE(T, poly_clear) (a, ctx);
337 TEMPLATE(T, poly_clear) (b, ctx);
338 TEMPLATE(T, poly_clear) (g, ctx);
339 TEMPLATE(T, poly_clear) (s, ctx);
340 TEMPLATE(T, poly_clear) (t, ctx);
341 TEMPLATE(T, poly_clear) (d, ctx);
342 TEMPLATE(T, poly_clear) (w, ctx);
343 TEMPLATE(T, ctx_clear) (ctx);
344 }
345
346 /* test aliasing of s and a */
347 for (i = 0; i < 5 * flint_test_multiplier(); i++)
348 {
349 TEMPLATE(T, ctx_t) ctx;
350 TEMPLATE(T, poly_t) a, b, d, g, s, t, w;
351
352 TEMPLATE(T, ctx_randtest) (ctx, state);
353
354 TEMPLATE(T, poly_init) (a, ctx);
355 TEMPLATE(T, poly_init) (b, ctx);
356 TEMPLATE(T, poly_init) (g, ctx);
357 TEMPLATE(T, poly_init) (s, ctx);
358 TEMPLATE(T, poly_init) (t, ctx);
359 TEMPLATE(T, poly_init) (d, ctx);
360 TEMPLATE(T, poly_init) (w, ctx);
361 TEMPLATE(T, poly_randtest) (a, state, n_randint(state, 100), ctx);
362 TEMPLATE(T, poly_randtest) (b, state, n_randint(state, 100), ctx);
363
364 TEMPLATE(T, poly_xgcd_euclidean) (g, s, t, a, b, ctx);
365 TEMPLATE(T, poly_xgcd_euclidean) (d, w, a, a, b, ctx);
366
367 result = (TEMPLATE(T, poly_equal) (s, w, ctx) &&
368 TEMPLATE(T, poly_equal) (t, a, ctx) &&
369 TEMPLATE(T, poly_equal) (g, d, ctx));
370
371 if (!result)
372 {
373 flint_printf("FAIL:\n");
374 TEMPLATE(T, poly_print_pretty) (a, "x", ctx), flint_printf("\n\n");
375 TEMPLATE(T, poly_print_pretty) (b, "x", ctx), flint_printf("\n\n");
376 TEMPLATE(T, poly_print_pretty) (g, "x", ctx), flint_printf("\n\n");
377 TEMPLATE(T, poly_print_pretty) (s, "x", ctx), flint_printf("\n\n");
378 TEMPLATE(T, poly_print_pretty) (t, "x", ctx), flint_printf("\n\n");
379 TEMPLATE(T, poly_print_pretty) (d, "x", ctx), flint_printf("\n\n");
380 TEMPLATE(T, poly_print_pretty) (w, "x", ctx), flint_printf("\n\n");
381 abort();
382 }
383
384 TEMPLATE(T, poly_clear) (a, ctx);
385 TEMPLATE(T, poly_clear) (b, ctx);
386 TEMPLATE(T, poly_clear) (g, ctx);
387 TEMPLATE(T, poly_clear) (s, ctx);
388 TEMPLATE(T, poly_clear) (t, ctx);
389 TEMPLATE(T, poly_clear) (d, ctx);
390 TEMPLATE(T, poly_clear) (w, ctx);
391 TEMPLATE(T, ctx_clear) (ctx);
392 }
393
394 /* test aliasing of t and b */
395 for (i = 0; i < 5 * flint_test_multiplier(); i++)
396 {
397 TEMPLATE(T, ctx_t) ctx;
398 TEMPLATE(T, poly_t) a, b, d, g, s, t, w;
399
400 TEMPLATE(T, ctx_randtest) (ctx, state);
401
402 TEMPLATE(T, poly_init) (a, ctx);
403 TEMPLATE(T, poly_init) (b, ctx);
404 TEMPLATE(T, poly_init) (g, ctx);
405 TEMPLATE(T, poly_init) (s, ctx);
406 TEMPLATE(T, poly_init) (t, ctx);
407 TEMPLATE(T, poly_init) (d, ctx);
408 TEMPLATE(T, poly_init) (w, ctx);
409 TEMPLATE(T, poly_randtest) (a, state, n_randint(state, 100), ctx);
410 TEMPLATE(T, poly_randtest) (b, state, n_randint(state, 100), ctx);
411
412 TEMPLATE(T, poly_xgcd_euclidean) (g, s, t, a, b, ctx);
413 TEMPLATE(T, poly_xgcd_euclidean) (d, w, b, a, b, ctx);
414
415 result = (TEMPLATE(T, poly_equal) (s, w, ctx) &&
416 TEMPLATE(T, poly_equal) (t, b, ctx) &&
417 TEMPLATE(T, poly_equal) (g, d, ctx));
418
419 if (!result)
420 {
421 flint_printf("FAIL:\n");
422 TEMPLATE(T, poly_print_pretty) (a, "x", ctx), flint_printf("\n\n");
423 TEMPLATE(T, poly_print_pretty) (b, "x", ctx), flint_printf("\n\n");
424 TEMPLATE(T, poly_print_pretty) (g, "x", ctx), flint_printf("\n\n");
425 TEMPLATE(T, poly_print_pretty) (s, "x", ctx), flint_printf("\n\n");
426 TEMPLATE(T, poly_print_pretty) (t, "x", ctx), flint_printf("\n\n");
427 TEMPLATE(T, poly_print_pretty) (d, "x", ctx), flint_printf("\n\n");
428 TEMPLATE(T, poly_print_pretty) (w, "x", ctx), flint_printf("\n\n");
429 abort();
430 }
431
432 TEMPLATE(T, poly_clear) (a, ctx);
433 TEMPLATE(T, poly_clear) (b, ctx);
434 TEMPLATE(T, poly_clear) (g, ctx);
435 TEMPLATE(T, poly_clear) (s, ctx);
436 TEMPLATE(T, poly_clear) (t, ctx);
437 TEMPLATE(T, poly_clear) (d, ctx);
438 TEMPLATE(T, poly_clear) (w, ctx);
439 TEMPLATE(T, ctx_clear) (ctx);
440 }
441
442
443 FLINT_TEST_CLEANUP(state);
444
445 flint_printf("PASS\n");
446 return 0;
447 }
448
449 #endif
450