1 /*
2 Copyright (C) 2012 Fredrik Johansson
3 Copyright (C) 2018 William Hart
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 #include <stdio.h>
14 #include <stdlib.h>
15 #include <gmp.h>
16 #include "flint.h"
17 #include "fmpz.h"
18 #include "fmpz_poly.h"
19 #include "ulong_extras.h"
20
21 int
main(void)22 main(void)
23 {
24 int i;
25 FLINT_TEST_INIT(state);
26
27 flint_printf("sqrt_classical... ");
28 fflush(stdout);
29
30 /* Test aliasing */
31 for (i = 0; i < 200 * flint_test_multiplier(); i++)
32 {
33 fmpz_poly_t a, b;
34 int square1, square2;
35
36 fmpz_poly_init(a);
37 fmpz_poly_init(b);
38
39 fmpz_poly_randtest(a, state, 1 + n_randint(state, 20),
40 1 + n_randint(state, 200));
41
42 if (n_randint(state, 2))
43 fmpz_poly_sqr(a, a);
44
45 square1 = fmpz_poly_sqrt_classical(b, a);
46 square2 = fmpz_poly_sqrt_classical(a, a);
47
48 if ((square1 != square2) || (square1 && !fmpz_poly_equal(a, b)))
49 {
50 flint_printf("FAIL: aliasing:\n");
51 flint_printf("square1 = %d, square2 = %d\n\n", square1, square2);
52 flint_printf("a: "); fmpz_poly_print(a); flint_printf("\n\n");
53 flint_printf("b: "); fmpz_poly_print(b); flint_printf("\n\n");
54 abort();
55 }
56
57 fmpz_poly_clear(a);
58 fmpz_poly_clear(b);
59 }
60
61 /* Test random squares */
62 for (i = 0; i < 200 * flint_test_multiplier(); i++)
63 {
64 fmpz_poly_t a, b, c;
65 int square;
66
67 fmpz_poly_init(a);
68 fmpz_poly_init(b);
69 fmpz_poly_init(c);
70
71 fmpz_poly_randtest(a, state, 1 + n_randint(state, 20),
72 1 + n_randint(state, 200));
73 fmpz_poly_sqr(b, a);
74 square = fmpz_poly_sqrt_classical(c, b);
75
76 if (!square)
77 {
78 flint_printf("FAIL: square reported nonsquare:\n");
79 flint_printf("a: "); fmpz_poly_print(a); flint_printf("\n\n");
80 flint_printf("b: "); fmpz_poly_print(b); flint_printf("\n\n");
81 flint_printf("c: "); fmpz_poly_print(c); flint_printf("\n\n");
82 abort();
83 }
84
85 if (!fmpz_poly_is_zero(c) &&
86 fmpz_sgn(fmpz_poly_get_coeff_ptr(c, fmpz_poly_degree(c))) < 0)
87 {
88 flint_printf("FAIL: leading coefficient not positive:\n");
89 flint_printf("a: "); fmpz_poly_print(a); flint_printf("\n\n");
90 flint_printf("b: "); fmpz_poly_print(b); flint_printf("\n\n");
91 flint_printf("c: "); fmpz_poly_print(c); flint_printf("\n\n");
92 abort();
93 }
94
95 fmpz_poly_sqr(c, c);
96 if (!fmpz_poly_equal(c, b))
97 {
98 flint_printf("FAIL: sqrt(b)^2 != b:\n");
99 flint_printf("a: "); fmpz_poly_print(a); flint_printf("\n\n");
100 flint_printf("b: "); fmpz_poly_print(b); flint_printf("\n\n");
101 flint_printf("c: "); fmpz_poly_print(c); flint_printf("\n\n");
102 abort();
103 }
104
105 fmpz_poly_clear(a);
106 fmpz_poly_clear(b);
107 fmpz_poly_clear(c);
108 }
109
110 /* Test "almost" squares */
111 for (i = 0; i < 200 * flint_test_multiplier(); i++)
112 {
113 fmpz_poly_t a, b, c;
114 fmpz_t t;
115 slong j;
116 int square;
117
118 fmpz_poly_init(a);
119 fmpz_poly_init(b);
120 fmpz_poly_init(c);
121 fmpz_init(t);
122
123 fmpz_poly_randtest_not_zero(a, state, 1 + n_randint(state, 20),
124 1 + n_randint(state, 200));
125 fmpz_poly_sqr(b, a);
126
127 j = n_randint(state, fmpz_poly_length(b));
128 fmpz_randtest_not_zero(t, state, 1 + n_randint(state, 100));
129 fmpz_add(b->coeffs + j, b->coeffs + j, t);
130 _fmpz_poly_normalise(b);
131
132 square = fmpz_poly_sqrt_classical(c, b);
133
134 if (square)
135 {
136 fmpz_poly_sqr(c, c);
137 if (!fmpz_poly_equal(c, b))
138 {
139 flint_printf("FAIL: sqrt(b)^2 != b:\n");
140 flint_printf("a: "); fmpz_poly_print(a); flint_printf("\n\n");
141 flint_printf("b: "); fmpz_poly_print(b); flint_printf("\n\n");
142 flint_printf("c: "); fmpz_poly_print(c); flint_printf("\n\n");
143 abort();
144 }
145 }
146
147 fmpz_clear(t);
148 fmpz_poly_clear(a);
149 fmpz_poly_clear(b);
150 fmpz_poly_clear(c);
151 }
152
153
154 flint_printf("PASS\n");
155 FLINT_TEST_CLEANUP(state);
156 return 0;
157 }
158