1 /*=============================================================================
2
3 This file is part of Antic.
4
5 Antic is free software: you can redistribute it and/or modify it under
6 the terms of the GNU Lesser General Public License (LGPL) as published
7 by the Free Software Foundation; either version 2.1 of the License, or
8 (at your option) any later version. See <http://www.gnu.org/licenses/>.
9
10 =============================================================================*/
11 /******************************************************************************
12
13 Copyright (C) 2013 William Hart
14
15 ******************************************************************************/
16
17 #include "nf_elem.h"
18
_nf_elem_equal(const nf_elem_t a,const nf_elem_t b,const nf_t nf)19 int _nf_elem_equal(const nf_elem_t a, const nf_elem_t b, const nf_t nf)
20 {
21 if (nf->flag & NF_LINEAR)
22 {
23 slong d, bits1, bits2;
24 int res = 1;
25
26 const fmpz * const anum = LNF_ELEM_NUMREF(a);
27 const fmpz * const bnum = LNF_ELEM_NUMREF(b);
28 const fmpz * const aden = LNF_ELEM_DENREF(a);
29 const fmpz * const bden = LNF_ELEM_DENREF(b);
30
31 fmpz_t t1, t2;
32
33 if (fmpz_equal(aden, bden))
34 return fmpz_equal(anum, bnum);
35
36 d = fmpz_bits(aden) - fmpz_bits(bden) + 1;
37
38 bits1 = fmpz_bits(anum);
39 bits2 = fmpz_bits(bnum);
40 if (!(bits1 == 0 && bits2 == 0) && (ulong) (bits1 - bits2 + d) > 2)
41 return 0;
42
43 fmpz_init(t1);
44 fmpz_init(t2);
45
46 fmpz_mul(t1, anum, bden);
47 fmpz_mul(t2, bnum, aden);
48
49 if (!fmpz_equal(t1, t2))
50 res = 0;
51
52 fmpz_clear(t1);
53 fmpz_clear(t2);
54
55 return res;
56 } else if (nf->flag & NF_QUADRATIC)
57 {
58 slong d, bits1, bits2;
59 int res = 1;
60
61 const fmpz * const anum = QNF_ELEM_NUMREF(a);
62 const fmpz * const bnum = QNF_ELEM_NUMREF(b);
63 const fmpz * const aden = QNF_ELEM_DENREF(a);
64 const fmpz * const bden = QNF_ELEM_DENREF(b);
65
66 fmpz_t t1, t2;
67
68 if (fmpz_equal(aden, bden))
69 return fmpz_equal(anum, bnum) && fmpz_equal(anum + 1, bnum + 1);
70
71 d = fmpz_bits(aden) - fmpz_bits(bden) + 1;
72
73 bits1 = fmpz_bits(anum + 1);
74 bits2 = fmpz_bits(bnum + 1);
75 if (!(bits1 == 0 && bits2 == 0) && (ulong) (bits1 - bits2 + d) > 2)
76 return 0;
77
78 bits1 = fmpz_bits(anum);
79 bits2 = fmpz_bits(bnum);
80 if (!(bits1 == 0 && bits2 == 0) && (ulong) (bits1 - bits2 + d) > 2)
81 return 0;
82
83 fmpz_init(t1);
84 fmpz_init(t2);
85
86 fmpz_mul(t1, anum, bden);
87 fmpz_mul(t2, bnum, aden);
88
89 if (!fmpz_equal(t1, t2))
90 {
91 res = 0;
92 goto cleanup;
93 }
94
95 fmpz_mul(t1, anum + 1, bden);
96 fmpz_mul(t2, bnum + 1, aden);
97
98 if (!fmpz_equal(t1, t2))
99 {
100 res = 0;
101 goto cleanup;
102 }
103
104 cleanup:
105
106 fmpz_clear(t1);
107 fmpz_clear(t2);
108
109 return res;
110 } else
111 {
112 const slong len1 = NF_ELEM(a)->length;
113 const slong len2 = NF_ELEM(b)->length;
114
115 if (len1 != len2)
116 return 0;
117
118 if (fmpz_equal(fmpq_poly_denref(NF_ELEM(a)), fmpq_poly_denref(NF_ELEM(b))))
119 return _fmpz_vec_equal(NF_ELEM_NUMREF(a), NF_ELEM_NUMREF(b), len1);
120 else
121 {
122 slong i;
123 slong d = fmpz_bits(fmpq_poly_denref(NF_ELEM(b)))
124 - fmpz_bits(fmpq_poly_denref(NF_ELEM(a))) + 1;
125 fmpz * p1 = NF_ELEM_NUMREF(a);
126 fmpz * p2 = NF_ELEM_NUMREF(b);
127 fmpz_t gcd, den1, den2;
128 fmpz * t1, * t2;
129 int equal;
130
131 for (i = 0; i < len1; i++)
132 {
133 slong b1 = fmpz_bits(p1 + i);
134 slong b2 = fmpz_bits(p2 + i);
135 if (!(b1 == 0 && b2 == 0) && (ulong) (b1 - b2 + d) > 2)
136 return 0;
137 }
138
139 fmpz_init(gcd);
140 fmpz_init(den1);
141 fmpz_init(den2);
142
143 /* TODO: possibly only compute GCD if it will save time */
144 fmpz_gcd(gcd, fmpq_poly_denref(NF_ELEM(a)), fmpq_poly_denref(NF_ELEM(b)));
145 fmpz_divexact(den1, fmpq_poly_denref(NF_ELEM(a)), gcd);
146 fmpz_divexact(den2, fmpq_poly_denref(NF_ELEM(b)), gcd);
147
148 t1 = _fmpz_vec_init(len1);
149 t2 = _fmpz_vec_init(len1);
150
151 _fmpz_vec_scalar_mul_fmpz(t1, p1, len1, den2);
152 _fmpz_vec_scalar_mul_fmpz(t2, p2, len2, den1);
153
154 equal = _fmpz_vec_equal(t1, t2, len1);
155
156 fmpz_clear(gcd);
157 fmpz_clear(den1);
158 fmpz_clear(den2);
159
160 _fmpz_vec_clear(t1, len1);
161 _fmpz_vec_clear(t2, len1);
162
163 return equal;
164 }
165 }
166 }
167
nf_elem_equal(const nf_elem_t a,const nf_elem_t b,const nf_t nf)168 int nf_elem_equal(const nf_elem_t a, const nf_elem_t b, const nf_t nf)
169 {
170 if (nf->flag & NF_LINEAR)
171 {
172 if (!fmpz_equal(LNF_ELEM_DENREF(a), LNF_ELEM_DENREF(b)))
173 return 0;
174
175 if (!fmpz_equal(LNF_ELEM_NUMREF(a), LNF_ELEM_NUMREF(b)))
176 return 0;
177
178 return 1;
179 } else if (nf->flag & NF_QUADRATIC)
180 {
181 if (!fmpz_equal(QNF_ELEM_DENREF(a), QNF_ELEM_DENREF(b)))
182 return 0;
183
184 if (!fmpz_equal(QNF_ELEM_NUMREF(a), QNF_ELEM_NUMREF(b)))
185 return 0;
186
187 if (!fmpz_equal(QNF_ELEM_NUMREF(a) + 1, QNF_ELEM_NUMREF(b) + 1))
188 return 0;
189
190 return 1;
191 } else
192 {
193 const slong len1 = NF_ELEM(a)->length;
194 const slong len2 = NF_ELEM(b)->length;
195
196 if (len1 != len2)
197 return 0;
198
199 if (fmpz_equal(fmpq_poly_denref(NF_ELEM(a)), fmpq_poly_denref(NF_ELEM(b))))
200 return _fmpz_vec_equal(NF_ELEM_NUMREF(a), NF_ELEM_NUMREF(b), len1);
201 else
202 return 0;
203 }
204 }
205