1 /*
2 Copyright (C) 2013 Tom Bachmann
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 #ifndef FMPZ_MOD_POLYXX_H
13 #define FMPZ_MOD_POLYXX_H
14
15 #include "fmpz_mod_poly.h"
16
17 #include "fmpzxx.h"
18 #include "fmpz_polyxx.h"
19 #include "nmod_polyxx.h"
20
21 #include "flintxx/expression.h"
22 #include "flintxx/flint_classes.h"
23 #include "flintxx/flint_exception.h"
24 #include "flintxx/frandxx.h"
25 #include "flintxx/ltuple.h"
26 #include "flintxx/stdmath.h"
27 #include "flintxx/vector.h"
28
29 // TODO create/use fmpz_modxx class?
30
31 namespace flint {
32 FLINT_DEFINE_BINOP(divrem_f)
FLINT_DEFINE_BINOP(gcd_euclidean_f)33 FLINT_DEFINE_BINOP(gcd_euclidean_f)
34 FLINT_DEFINE_BINOP(gcd_f)
35 FLINT_DEFINE_BINOP(radix)
36
37 FLINT_DEFINE_UNOP(fmpz_mod_polyxx_lead) // TODO standardise?
38 FLINT_DEFINE_BINOP(fmpz_mod_polyxx_get_coeff) // TODO standardise?
39
40 namespace detail {
41 template<class Poly>
42 struct fmpz_mod_poly_traits
43 {
44 typedef FLINT_UNOP_BUILD_RETTYPE(
45 fmpz_mod_polyxx_lead, fmpzxx, Poly) lead_ref_t;
46 typedef lead_ref_t lead_srcref_t;
47 static lead_ref_t lead(const Poly& p) {return fmpz_mod_polyxx_lead(p);}
48 };
49 }
50
51 template<class Operation, class Data>
52 class fmpz_mod_polyxx_expression
53 : public expression<derived_wrapper<fmpz_mod_polyxx_expression>,
54 Operation, Data>
55 {
56 typedef expression<derived_wrapper< ::flint::fmpz_mod_polyxx_expression>,
57 Operation, Data> base_t;
58 typedef detail::fmpz_mod_poly_traits<fmpz_mod_polyxx_expression>
59 poly_traits_t;
60
61 FLINTXX_DEFINE_BASICS(fmpz_mod_polyxx_expression)
FLINTXX_DEFINE_CTORS(fmpz_mod_polyxx_expression)62 FLINTXX_DEFINE_CTORS(fmpz_mod_polyxx_expression)
63 FLINTXX_DEFINE_C_REF(fmpz_mod_polyxx_expression, fmpz_mod_poly_struct, _poly)
64
65 template<class Fmpz>
66 static fmpz_mod_polyxx_expression randtest(const Fmpz& m,
67 frandxx& state, slong len)
68 {
69 fmpz_mod_polyxx_expression res(m);
70 res.set_randtest(state, len);
71 return res;
72 }
73 template<class Fmpz>
randtest_irreducible(const Fmpz & m,frandxx & state,slong len)74 static fmpz_mod_polyxx_expression randtest_irreducible(const Fmpz& m,
75 frandxx& state, slong len)
76 {
77 fmpz_mod_polyxx_expression res(m);
78 res.set_randtest_irreducible(state, len);
79 return res;
80 }
81 template<class Fmpz>
randtest_not_zero(const Fmpz & m,frandxx & state,slong len)82 static fmpz_mod_polyxx_expression randtest_not_zero(const Fmpz& m,
83 frandxx& state, slong len)
84 {
85 fmpz_mod_polyxx_expression res(m);
86 res.set_randtest_not_zero(state, len);
87 return res;
88 }
89
90 template<class Fmpz>
zero(const Fmpz & m)91 static fmpz_mod_polyxx_expression zero(const Fmpz& m)
92 {return fmpz_mod_polyxx_expression(m);}
93
94 // these only make sense with immediates
_mod()95 fmpzxx_srcref _mod() const
96 {return fmpzxx_srcref::make(fmpz_mod_poly_modulus(_poly()));}
97
98 // These only make sense with target immediates
realloc(slong alloc)99 void realloc(slong alloc) {fmpz_mod_poly_realloc(_poly(), alloc);}
fit_length(slong len)100 void fit_length(slong len) {fmpz_mod_poly_fit_length(_poly(), len);}
_normalise()101 void _normalise() {_fmpz_mod_poly_normalise(_poly());}
set_coeff(slong n,ulong c)102 void set_coeff(slong n, ulong c) {fmpz_mod_poly_set_coeff_ui(_poly(), n, c);}
103 template<class Fmpz>
104 typename mp::enable_if<traits::is_fmpzxx<Fmpz> >::type
set_coeff(slong j,const Fmpz & c)105 set_coeff(slong j, const Fmpz& c)
106 {
107 fmpz_mod_poly_set_coeff_fmpz(_poly(), j, c.evaluate()._fmpz());
108 }
truncate(slong n)109 void truncate(slong n) {fmpz_mod_poly_truncate(_poly(), n);}
zero_coeffs(slong i,slong j)110 void zero_coeffs(slong i, slong j) {fmpz_mod_poly_zero_coeffs(_poly(), i, j);}
111
set_randtest(frandxx & state,slong len)112 void set_randtest(frandxx& state, slong len)
113 {fmpz_mod_poly_randtest(_poly(), state._data(), len);}
set_randtest_irreducible(frandxx & state,slong len)114 void set_randtest_irreducible(frandxx& state, slong len)
115 {fmpz_mod_poly_randtest_irreducible(_poly(), state._data(), len);}
set_randtest_not_zero(frandxx & state,slong len)116 void set_randtest_not_zero(frandxx& state, slong len)
117 {fmpz_mod_poly_randtest_not_zero(_poly(), state._data(), len);}
118
119 template<class Poly>
remove(const Poly & p)120 slong remove(const Poly& p)
121 {
122 return fmpz_mod_poly_remove(_poly(), p.evaluate()._poly());
123 }
124
set_zero()125 void set_zero() {fmpz_mod_poly_zero(_poly());}
126
127 // unified coefficient access
lead()128 typename poly_traits_t::lead_ref_t lead()
129 {
130 return poly_traits_t::lead(*this);
131 }
lead()132 typename poly_traits_t::lead_srcref_t lead() const
133 {
134 return poly_traits_t::lead(*this);
135 }
136
137 // this works without evaluation
138 fmpzxx_srcref modulus() const;
139
create_temporary()140 evaluated_t create_temporary() const
141 {
142 return evaluated_t(modulus());
143 }
144
145 // These cause evaluation
length()146 slong length() const {return fmpz_mod_poly_length(this->evaluate()._poly());}
degree()147 slong degree() const {return fmpz_mod_poly_degree(this->evaluate()._poly());}
is_zero()148 bool is_zero() const {return fmpz_mod_poly_is_zero(this->evaluate()._poly());}
is_squarefree()149 bool is_squarefree() const
150 {return fmpz_mod_poly_is_squarefree(this->evaluate()._poly());}
is_irreducible()151 bool is_irreducible() const
152 {return fmpz_mod_poly_is_irreducible(this->evaluate()._poly());}
is_irreducible_ddf()153 bool is_irreducible_ddf() const
154 {return fmpz_mod_poly_is_irreducible_ddf(this->evaluate()._poly());}
is_irreducible_rabin()155 bool is_irreducible_rabin() const
156 {return fmpz_mod_poly_is_irreducible_rabin(this->evaluate()._poly());}
157
158 // Lazy members
159 FLINTXX_DEFINE_MEMBER_BINOP_(get_coeff, fmpz_mod_polyxx_get_coeff)
160 FLINTXX_DEFINE_MEMBER_BINOP_(operator(), compeval)
161
162 FLINTXX_DEFINE_MEMBER_UNOP(derivative)
163 FLINTXX_DEFINE_MEMBER_UNOP(invmod)
164 FLINTXX_DEFINE_MEMBER_UNOP(make_monic)
165 FLINTXX_DEFINE_MEMBER_UNOP(sqr)
166
167 FLINTXX_DEFINE_MEMBER_BINOP(compose_divconquer)
168 FLINTXX_DEFINE_MEMBER_BINOP(compose_horner)
169 FLINTXX_DEFINE_MEMBER_BINOP(div_basecase)
170 FLINTXX_DEFINE_MEMBER_BINOP(divrem)
171 FLINTXX_DEFINE_MEMBER_BINOP(divrem_basecase)
172 FLINTXX_DEFINE_MEMBER_BINOP(divrem_divconquer)
173 FLINTXX_DEFINE_MEMBER_BINOP(divrem_f)
174 FLINTXX_DEFINE_MEMBER_BINOP(gcd)
175 FLINTXX_DEFINE_MEMBER_BINOP(gcd_euclidean)
176 FLINTXX_DEFINE_MEMBER_BINOP(gcd_euclidean_f)
177 FLINTXX_DEFINE_MEMBER_BINOP(gcd_f)
178 FLINTXX_DEFINE_MEMBER_BINOP(gcdinv)
179 FLINTXX_DEFINE_MEMBER_BINOP(invmod)
180 FLINTXX_DEFINE_MEMBER_BINOP(inv_series_newton)
181 FLINTXX_DEFINE_MEMBER_BINOP(shift_left)
182 FLINTXX_DEFINE_MEMBER_BINOP(shift_right)
183 FLINTXX_DEFINE_MEMBER_BINOP(pow)
184 FLINTXX_DEFINE_MEMBER_BINOP(radix)
185 FLINTXX_DEFINE_MEMBER_BINOP(rem_basecase)
186 FLINTXX_DEFINE_MEMBER_BINOP(xgcd)
187 FLINTXX_DEFINE_MEMBER_BINOP(xgcd_euclidean)
188
189 FLINTXX_DEFINE_MEMBER_3OP(compose_mod)
190 FLINTXX_DEFINE_MEMBER_3OP(compose_mod_brent_kung)
191 FLINTXX_DEFINE_MEMBER_3OP(compose_mod_horner)
192 FLINTXX_DEFINE_MEMBER_3OP(mullow)
193 FLINTXX_DEFINE_MEMBER_3OP(mulmod)
194 FLINTXX_DEFINE_MEMBER_3OP(powmod_binexp)
195 FLINTXX_DEFINE_MEMBER_3OP(pow_trunc)
196 FLINTXX_DEFINE_MEMBER_3OP(pow_trunc_binexp)
197 };
198
199 namespace detail {
200 struct fmpz_mod_poly_data;
201 }
202
203 typedef fmpz_mod_polyxx_expression<operations::immediate, detail::fmpz_mod_poly_data>
204 fmpz_mod_polyxx;
205 typedef fmpz_mod_polyxx_expression<operations::immediate,
206 flint_classes::ref_data<fmpz_mod_polyxx, fmpz_mod_poly_struct> >
207 fmpz_mod_polyxx_ref;
208 typedef fmpz_mod_polyxx_expression<operations::immediate,
209 flint_classes::srcref_data<
210 fmpz_mod_polyxx, fmpz_mod_polyxx_ref, fmpz_mod_poly_struct> >
211 fmpz_mod_polyxx_srcref;
212
213 #define FMPZ_MOD_POLYXX_COND_S FLINTXX_COND_S(fmpz_mod_polyxx)
214 #define FMPZ_MOD_POLYXX_COND_T FLINTXX_COND_T(fmpz_mod_polyxx)
215
216 namespace detail {
217 template<>
218 struct fmpz_mod_poly_traits<fmpz_mod_polyxx_srcref>
219 {
220 typedef fmpzxx_srcref lead_srcref_t;
221 typedef fmpzxx_srcref lead_ref_t;
222
223 template<class P>
224 static lead_srcref_t lead(P p)
225 {return lead_srcref_t::make(fmpz_mod_poly_lead(p._poly()));}
226 };
227 template<>
228 struct fmpz_mod_poly_traits<fmpz_mod_polyxx_ref>
229 {
230 typedef fmpzxx_ref lead_ref_t;
231 typedef fmpzxx_ref lead_srcref_t;
232
233 template<class P>
234 static lead_ref_t lead(P p)
235 {return lead_ref_t::make(fmpz_mod_poly_lead(p._poly()));}
236 };
237 template<>
238 struct fmpz_mod_poly_traits<fmpz_mod_polyxx>
239 {
240 typedef fmpzxx_ref lead_ref_t;
241 typedef fmpzxx_srcref lead_srcref_t;
242
243 template<class P>
244 static lead_ref_t lead(P& p)
245 {return lead_ref_t::make(fmpz_mod_poly_lead(p._poly()));}
246 template<class P>
247 static lead_srcref_t lead(const P& p)
248 {return lead_srcref_t::make(fmpz_mod_poly_lead(p._poly()));}
249 };
250
251 struct fmpz_mod_poly_data
252 {
253 fmpz_mod_poly_t inner;
254 typedef fmpz_mod_poly_t& data_ref_t;
255 typedef const fmpz_mod_poly_t& data_srcref_t;
256
257 template<class Fmpz>
258 fmpz_mod_poly_data(const Fmpz& n,
259 typename mp::enable_if<traits::is_fmpzxx<Fmpz> >::type* = 0)
260 {
261 fmpz_mod_poly_init(inner, n.evaluate()._fmpz());
262 }
263 template<class Fmpz>
264 fmpz_mod_poly_data(const Fmpz& n, slong alloc,
265 typename mp::enable_if<traits::is_fmpzxx<Fmpz> >::type* = 0)
266 {
267 fmpz_mod_poly_init2(inner, n.evaluate()._fmpz(), alloc);
268 }
269 ~fmpz_mod_poly_data() {fmpz_mod_poly_clear(inner);}
270
271 fmpz_mod_poly_data(const fmpz_mod_poly_data& o)
272 {
273 fmpz_mod_poly_init(inner, fmpz_mod_poly_modulus(o.inner));
274 fmpz_mod_poly_set(inner, o.inner);
275 }
276
277 fmpz_mod_poly_data(fmpz_mod_polyxx_srcref r)
278 {
279 fmpz_mod_poly_init(inner, r.modulus()._fmpz());
280 fmpz_mod_poly_set(inner, r._poly());
281 }
282 };
283
284 struct is_fmpz_mod_polyxx_predicate
285 {
286 template<class T> struct type : FMPZ_MOD_POLYXX_COND_S<T> { };
287 };
288 }
289 template<class Operation, class Data>
290 inline fmpzxx_srcref
291 fmpz_mod_polyxx_expression<Operation, Data>::modulus() const
292 {
293 return tools::find_subexpr<detail::is_fmpz_mod_polyxx_predicate>(
294 *this)._mod();
295 }
296
297 namespace traits {
298 template<class T> struct is_fmpz_mod_polyxx : mp::or_<
299 traits::is_T_expr<T, fmpz_mod_polyxx>,
300 flint_classes::is_source<fmpz_mod_polyxx, T> > { };
301 }
302
303 namespace rules {
304 FLINT_DEFINE_DOIT_COND2(assignment, FMPZ_MOD_POLYXX_COND_T,
305 FMPZ_MOD_POLYXX_COND_S, fmpz_mod_poly_set(to._poly(), from._poly()))
306 FLINT_DEFINE_DOIT_COND2(assignment, FMPZ_MOD_POLYXX_COND_T,
307 traits::is_unsigned_integer, fmpz_mod_poly_set_ui(to._poly(), from))
308 FLINT_DEFINE_DOIT_COND2(assignment, FMPZ_MOD_POLYXX_COND_T,
309 FMPZXX_COND_S, fmpz_mod_poly_set_fmpz(to._poly(), from._fmpz()))
310 FLINT_DEFINE_DOIT_COND2(assignment, FMPZ_MOD_POLYXX_COND_T, FMPZ_POLYXX_COND_S,
311 fmpz_mod_poly_set_fmpz_poly(to._poly(), from._poly()))
312 FLINTXX_DEFINE_CONVERSION_TMP(fmpz_polyxx, fmpz_mod_polyxx,
313 fmpz_mod_poly_get_fmpz_poly(to._poly(), from._poly()))
314
315 FLINTXX_DEFINE_SWAP(fmpz_mod_polyxx, fmpz_mod_poly_swap(e1._poly(), e2._poly()))
316
317 FLINTXX_DEFINE_EQUALS(fmpz_mod_polyxx, fmpz_mod_poly_equal(e1._poly(), e2._poly()))
318
319 FLINT_DEFINE_BINARY_EXPR_COND2(fmpz_mod_polyxx_get_coeff_op, fmpzxx,
320 FMPZ_MOD_POLYXX_COND_S, traits::fits_into_slong,
321 fmpz_mod_poly_get_coeff_fmpz(to._fmpz(), e1._poly(), e2))
322
323 FLINT_DEFINE_PRINT_COND(FMPZ_MOD_POLYXX_COND_S, fmpz_mod_poly_fprint(to, from._poly()))
324 FLINT_DEFINE_PRINT_PRETTY_COND_2(FMPZ_MOD_POLYXX_COND_S, const char*,
325 fmpz_mod_poly_fprint_pretty(to, from._poly(), extra))
326 FLINT_DEFINE_READ_COND(FMPZ_MOD_POLYXX_COND_T, fmpz_mod_poly_fread(from, to._poly()))
327
328 FLINT_DEFINE_BINARY_EXPR_COND2(plus, fmpz_mod_polyxx,
329 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
330 fmpz_mod_poly_add(to._poly(), e1._poly(), e2._poly()))
331 FLINT_DEFINE_BINARY_EXPR_COND2(minus, fmpz_mod_polyxx,
332 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
333 fmpz_mod_poly_sub(to._poly(), e1._poly(), e2._poly()))
334
335 FLINT_DEFINE_CBINARY_EXPR_COND2(times, fmpz_mod_polyxx,
336 FMPZ_MOD_POLYXX_COND_S, FMPZXX_COND_S,
337 fmpz_mod_poly_scalar_mul_fmpz(to._poly(), e1._poly(), e2._fmpz()))
338 FLINT_DEFINE_BINARY_EXPR_COND2(times, fmpz_mod_polyxx,
339 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
340 fmpz_mod_poly_mul(to._poly(), e1._poly(), e2._poly()))
341
342 // TODO expose the temporary
343 FLINT_DEFINE_BINARY_EXPR_COND2(divided_by, fmpz_mod_polyxx,
344 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
345 fmpz_mod_polyxx tmp(to.modulus());
346 fmpz_mod_poly_divrem(to._poly(), tmp._poly(), e1._poly(), e2._poly()))
347
348 FLINT_DEFINE_UNARY_EXPR_COND(negate, fmpz_mod_polyxx, FMPZ_MOD_POLYXX_COND_S,
349 fmpz_mod_poly_neg(to._poly(), from._poly()))
350
351 FLINT_DEFINE_UNARY_EXPR_COND(fmpz_mod_polyxx_lead_op, fmpzxx,
352 FMPZ_MOD_POLYXX_COND_S,
353 fmpz_set(to._fmpz(), fmpz_mod_poly_lead(from._poly())))
354
355 FLINT_DEFINE_BINARY_EXPR_COND2(shift_left_op, fmpz_mod_polyxx,
356 FMPZ_MOD_POLYXX_COND_S, traits::fits_into_slong,
357 fmpz_mod_poly_shift_left(to._poly(), e1._poly(), e2))
358 FLINT_DEFINE_BINARY_EXPR_COND2(shift_right_op, fmpz_mod_polyxx,
359 FMPZ_MOD_POLYXX_COND_S, traits::fits_into_slong,
360 fmpz_mod_poly_shift_right(to._poly(), e1._poly(), e2))
361
362 FLINT_DEFINE_UNARY_EXPR_COND(make_monic_op, fmpz_mod_polyxx, FMPZ_MOD_POLYXX_COND_S,
363 fmpz_mod_poly_make_monic(to._poly(), from._poly()))
364
365 FLINT_DEFINE_THREEARY_EXPR_COND3(mullow_op, fmpz_mod_polyxx,
366 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S, traits::fits_into_slong,
367 fmpz_mod_poly_mullow(to._poly(), e1._poly(), e2._poly(), e3))
368 FLINT_DEFINE_THREEARY_EXPR_COND3(mulmod_op, fmpz_mod_polyxx,
369 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
370 fmpz_mod_poly_mulmod(to._poly(), e1._poly(), e2._poly(), e3._poly()))
371 FLINT_DEFINE_UNARY_EXPR_COND(sqr_op, fmpz_mod_polyxx, FMPZ_MOD_POLYXX_COND_S,
372 fmpz_mod_poly_sqr(to._poly(), from._poly()))
373
374 FLINT_DEFINE_BINARY_EXPR_COND2(modulo, fmpz_mod_polyxx,
375 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
376 fmpz_mod_poly_rem(to._poly(), e1._poly(), e2._poly()))
377
378 FLINT_DEFINE_THREEARY_EXPR_COND3(powmod_binexp_op, fmpz_mod_polyxx,
379 FMPZ_MOD_POLYXX_COND_S, traits::is_unsigned_integer, FMPZ_MOD_POLYXX_COND_S,
380 fmpz_mod_poly_powmod_ui_binexp(to._poly(), e1._poly(), e2, e3._poly()))
381 FLINT_DEFINE_THREEARY_EXPR_COND3(powmod_binexp_op, fmpz_mod_polyxx,
382 FMPZ_MOD_POLYXX_COND_S, FMPZXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
383 fmpz_mod_poly_powmod_fmpz_binexp(
384 to._poly(), e1._poly(), e2._fmpz(), e3._poly()))
385
386 FLINT_DEFINE_THREEARY_EXPR_COND3(pow_trunc_op, fmpz_mod_polyxx,
387 FMPZ_MOD_POLYXX_COND_S, traits::is_unsigned_integer, traits::fits_into_slong,
388 fmpz_mod_poly_pow_trunc(to._poly(), e1._poly(), e2, e3))
389 FLINT_DEFINE_THREEARY_EXPR_COND3(pow_trunc_binexp_op, fmpz_mod_polyxx,
390 FMPZ_MOD_POLYXX_COND_S, traits::is_unsigned_integer, traits::fits_into_slong,
391 fmpz_mod_poly_pow_trunc_binexp(to._poly(), e1._poly(), e2, e3))
392
393 FLINT_DEFINE_BINARY_EXPR_COND2(pow_op, fmpz_mod_polyxx,
394 FMPZ_MOD_POLYXX_COND_S, traits::is_unsigned_integer,
395 fmpz_mod_poly_pow(to._poly(), e1._poly(), e2))
396
397 namespace rdetail {
398 typedef make_ltuple<mp::make_tuple<fmpz_mod_polyxx, fmpz_mod_polyxx>::type>::type
399 fmpz_mod_polyxx_pair;
400 typedef make_ltuple<mp::make_tuple<
401 fmpzxx, fmpz_mod_polyxx, fmpz_mod_polyxx>::type>::type
402 fmpz_mod_poly_divrem_f_rt;
403 } // rdetail
404 FLINT_DEFINE_BINARY_EXPR_COND2(divrem_basecase_op, rdetail::fmpz_mod_polyxx_pair,
405 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
406 fmpz_mod_poly_divrem_basecase(
407 to.template get<0>()._poly(), to.template get<1>()._poly(),
408 e1._poly(), e2._poly()))
409 FLINT_DEFINE_BINARY_EXPR_COND2(divrem_divconquer_op, rdetail::fmpz_mod_polyxx_pair,
410 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
411 fmpz_mod_poly_divrem_divconquer(
412 to.template get<0>()._poly(), to.template get<1>()._poly(),
413 e1._poly(), e2._poly()))
414 FLINT_DEFINE_BINARY_EXPR_COND2(divrem_op, rdetail::fmpz_mod_polyxx_pair,
415 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
416 fmpz_mod_poly_divrem_divconquer(
417 to.template get<0>()._poly(), to.template get<1>()._poly(),
418 e1._poly(), e2._poly()))
419 FLINT_DEFINE_BINARY_EXPR_COND2(divrem_f_op, rdetail::fmpz_mod_poly_divrem_f_rt,
420 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
421 fmpz_mod_poly_divrem_f(
422 to.template get<0>()._fmpz(), to.template get<1>()._poly(),
423 to.template get<2>()._poly(), e1._poly(), e2._poly()))
424
425 FLINT_DEFINE_BINARY_EXPR_COND2(div_basecase_op, fmpz_mod_polyxx,
426 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
427 fmpz_mod_poly_div_basecase(to._poly(), e1._poly(), e2._poly()))
428 FLINT_DEFINE_BINARY_EXPR_COND2(rem_basecase_op, fmpz_mod_polyxx,
429 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
430 fmpz_mod_poly_rem_basecase(to._poly(), e1._poly(), e2._poly()))
431
432 FLINT_DEFINE_BINARY_EXPR_COND2(inv_series_newton_op, fmpz_mod_polyxx,
433 FMPZ_MOD_POLYXX_COND_S, traits::fits_into_slong,
434 fmpz_mod_poly_inv_series_newton(to._poly(), e1._poly(), e2))
435
436 FLINT_DEFINE_BINARY_EXPR_COND2(gcd_op, fmpz_mod_polyxx,
437 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
438 fmpz_mod_poly_gcd(to._poly(), e1._poly(), e2._poly()))
439 FLINT_DEFINE_BINARY_EXPR_COND2(gcd_euclidean_op, fmpz_mod_polyxx,
440 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
441 fmpz_mod_poly_gcd_euclidean(to._poly(), e1._poly(), e2._poly()))
442
443 namespace rdetail {
444 typedef make_ltuple<mp::make_tuple<
445 fmpz_mod_polyxx, fmpz_mod_polyxx, fmpz_mod_polyxx>::type>::type
446 fmpz_mod_polyxx_triple;
447 } // rdetail
448 FLINT_DEFINE_BINARY_EXPR_COND2(xgcd_op, rdetail::fmpz_mod_polyxx_triple,
449 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
450 fmpz_mod_poly_xgcd(to.template get<0>()._poly(), to.template get<1>()._poly(),
451 to.template get<2>()._poly(), e1._poly(), e2._poly()))
452 FLINT_DEFINE_BINARY_EXPR_COND2(xgcd_euclidean_op, rdetail::fmpz_mod_polyxx_triple,
453 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
454 fmpz_mod_poly_xgcd_euclidean(to.template get<0>()._poly(),
455 to.template get<1>()._poly(),
456 to.template get<2>()._poly(), e1._poly(), e2._poly()))
457
458 namespace rdetail {
459 typedef make_ltuple<mp::make_tuple<fmpzxx, fmpz_mod_polyxx>::type>::type
460 fmpz_mod_gcd_f_rt;
461 } // rdetail
462 FLINT_DEFINE_BINARY_EXPR_COND2(gcd_f_op, rdetail::fmpz_mod_gcd_f_rt,
463 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
464 fmpz_mod_poly_gcd_f(to.template get<0>()._fmpz(),
465 to.template get<1>()._poly(), e1._poly(), e2._poly()))
466 FLINT_DEFINE_BINARY_EXPR_COND2(gcd_euclidean_f_op, rdetail::fmpz_mod_gcd_f_rt,
467 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
468 fmpz_mod_poly_gcd_euclidean_f(to.template get<0>()._fmpz(),
469 to.template get<1>()._poly(), e1._poly(), e2._poly()))
470
471 FLINT_DEFINE_BINARY_EXPR_COND2(gcdinv_op, rdetail::fmpz_mod_polyxx_pair,
472 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
473 fmpz_mod_poly_gcdinv(
474 to.template get<0>()._poly(), to.template get<1>()._poly(),
475 e1._poly(), e2._poly()))
476
477 FLINT_DEFINE_BINARY_EXPR_COND2(invmod_op, fmpz_mod_polyxx,
478 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
479 execution_check(fmpz_mod_poly_invmod(to._poly(), e1._poly(), e2._poly()),
480 "invmod", "fmpz_mod_polyxx"))
481
482 FLINT_DEFINE_UNARY_EXPR_COND(derivative_op, fmpz_mod_polyxx, FMPZ_MOD_POLYXX_COND_S,
483 fmpz_mod_poly_derivative(to._poly(), from._poly()))
484
485 FLINT_DEFINE_BINARY_EXPR_COND2(evaluate_op, fmpzxx,
486 FMPZ_MOD_POLYXX_COND_S, FMPZXX_COND_S,
487 fmpz_mod_poly_evaluate_fmpz(to._fmpz(), e1._poly(), e2._fmpz()))
488
489 FLINT_DEFINE_BINARY_EXPR_COND2(compose_op, fmpz_mod_polyxx,
490 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
491 fmpz_mod_poly_compose(to._poly(), e1._poly(), e2._poly()))
492 FLINT_DEFINE_BINARY_EXPR_COND2(compose_divconquer_op, fmpz_mod_polyxx,
493 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
494 fmpz_mod_poly_compose_divconquer(to._poly(), e1._poly(), e2._poly()))
495 FLINT_DEFINE_BINARY_EXPR_COND2(compose_horner_op, fmpz_mod_polyxx,
496 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
497 fmpz_mod_poly_compose_horner(to._poly(), e1._poly(), e2._poly()))
498
499 FLINT_DEFINE_THREEARY_EXPR_COND3(compose_mod_op, fmpz_mod_polyxx,
500 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
501 fmpz_mod_poly_compose_mod(to._poly(), e1._poly(), e2._poly(), e3._poly()))
502 FLINT_DEFINE_THREEARY_EXPR_COND3(compose_mod_horner_op, fmpz_mod_polyxx,
503 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
504 fmpz_mod_poly_compose_mod_horner(
505 to._poly(), e1._poly(), e2._poly(), e3._poly()))
506 FLINT_DEFINE_THREEARY_EXPR_COND3(compose_mod_brent_kung_op, fmpz_mod_polyxx,
507 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
508 fmpz_mod_poly_compose_mod_brent_kung(
509 to._poly(), e1._poly(), e2._poly(), e3._poly()))
510 } // rules
511
512
513 ///////////////////////////////////////////////////////////////////////////////
514 // fmpz_mod_poly_vecxx (for radix conversion)
515 ///////////////////////////////////////////////////////////////////////////////
516 namespace detail {
517 struct fmpz_mod_poly_vector_data
518 {
519 slong size;
520 fmpz_mod_poly_struct** array;
521
522 template<class Fmpz>
523 void init(slong n, const Fmpz& f)
524 {
525 size = n;
526 array = new fmpz_mod_poly_struct*[n];
527 for(slong i = 0;i < n;++i)
528 {
529 array[i] = new fmpz_mod_poly_struct();
530 fmpz_mod_poly_init(array[i], f._fmpz());
531 }
532 }
533
534 template<class Fmpz>
535 fmpz_mod_poly_vector_data(slong n, const Fmpz& f,
536 typename mp::enable_if<traits::is_fmpzxx<Fmpz> >::type* = 0)
537 {
538 init(n, f.evaluate());
539 }
540
541 ~fmpz_mod_poly_vector_data()
542 {
543 for(slong i = 0;i < size;++i)
544 {
545 fmpz_mod_poly_clear(array[i]);
546 delete array[i];
547 }
548 delete[] array;
549 }
550
551 fmpz_mod_poly_vector_data(const fmpz_mod_poly_vector_data& o)
552 : size(o.size)
553 {
554 array = new fmpz_mod_poly_struct*[size];
555 for(slong i = 0;i < size;++i)
556 {
557 array[i] = new fmpz_mod_poly_struct();
558 fmpz_mod_poly_init(array[i], &o.array[0]->p);
559 fmpz_mod_poly_set(array[i], o.array[i]);
560 }
561 }
562
563 fmpz_mod_polyxx_ref at(slong i)
564 {return fmpz_mod_polyxx_ref::make(array[i]);}
565 fmpz_mod_polyxx_srcref at(slong i) const
566 {return fmpz_mod_polyxx_srcref::make(array[i]);}
567
568 bool equals(const fmpz_mod_poly_vector_data& o) const
569 {
570 if(size != o.size)
571 return false;
572 for(slong i = 0;i < size;++i)
573 if(!fmpz_mod_poly_equal(array[i], o.array[i]))
574 return false;
575 return true;
576 }
577 };
578
579 // TODO extend this somewhat similarly to the nmod* setup
580 template<class T>
581 fmpzxx_srcref find_fmpz_mod_polyxx_mod(const T& t)
582 {
583 // this works because there are not actually any functions operating on
584 // fmpz_mod_poly_vecxx
585 return tools::find_subexpr<detail::is_fmpz_mod_polyxx_predicate>(
586 t)._mod();
587 }
588
589 struct fmpz_mod_poly_vector_traits
590 : wrapped_vector_traits<fmpz_mod_polyxx, slong, fmpz_mod_polyxx_ref,
591 fmpz_mod_polyxx_srcref, fmpz_mod_poly_struct*>
592 {
593 template<class Expr>
594 static typename Expr::evaluated_t create_temporary(const Expr& e)
595 {
596 return typename Expr::evaluated_t(
597 e.size(), find_fmpz_mod_polyxx_mod(e));
598 }
599 };
600 } // detail
601
602 // TODO would it make more sense to have this have its own class?
603 typedef vector_expression<
604 detail::fmpz_mod_poly_vector_traits, operations::immediate,
605 detail::fmpz_mod_poly_vector_data> fmpz_mod_poly_vecxx;
606 // TODO references
607
608 template<>
609 struct enable_vector_rules<fmpz_mod_poly_vecxx> : mp::false_ { };
610
611 namespace rules {
612 // TODO hack to make code look like references are implemented
613 template<class T> struct FMPZ_MOD_POLY_VECXX_COND_S
614 : mp::equal_types<T, fmpz_mod_poly_vecxx> { };
615 #define FMPZ_MOD_POLY_VECXX_COND_T FMPZ_MOD_POLY_VECXX_COND_S
616
617 // TODO references
618 FLINT_DEFINE_GET(equals, bool, fmpz_mod_poly_vecxx, e1._data().equals(e2._data()))
619 } // rules
620
621
622 ///////////////////////////////////////////////////////////////////////////////
623 // radix conversion
624 ///////////////////////////////////////////////////////////////////////////////
625
626 class fmpz_mod_poly_radixxx
627 {
628 private:
629 fmpz_mod_poly_radix_t inner;
630
631 // not copyable
632 fmpz_mod_poly_radixxx(const fmpz_mod_poly_radixxx&);
633
634 public:
635 template<class Fmpz_mod_poly>
636 fmpz_mod_poly_radixxx(const Fmpz_mod_poly& r, slong deg,
637 typename mp::enable_if<
638 traits::is_fmpz_mod_polyxx<Fmpz_mod_poly> >::type* = 0)
639 {fmpz_mod_poly_radix_init(inner, r.evaluate()._poly(), deg);}
640 ~fmpz_mod_poly_radixxx() {fmpz_mod_poly_radix_clear(inner);}
641
642 fmpz_mod_poly_radix_t& _data() {return inner;}
643 const fmpz_mod_poly_radix_t& _data() const {return inner;}
644
645 slong degR() const {return inner->degR;}
646 };
647
648 namespace traits {
649 template<class T> struct is_fmpz_mod_poly_radixxx
650 : mp::equal_types<T, fmpz_mod_poly_radixxx> { };
651 } // traits
652
653 namespace vectors {
654 template<>
655 struct outsize<operations::radix_op>
656 {
657 template<class Expr>
658 static unsigned get(const Expr& e)
659 {
660 return e._data().first().degree() / e._data().second().degR() + 1;
661 }
662 };
663 }
664
665 namespace rules {
666 FLINT_DEFINE_BINARY_EXPR_COND2(radix_op, fmpz_mod_poly_vecxx,
667 FMPZ_MOD_POLYXX_COND_S, traits::is_fmpz_mod_poly_radixxx,
668 fmpz_mod_poly_radix(to._array(), e1._poly(), e2._data()))
669 }
670 } // flint
671
672 #include "fmpz_mod_poly_factorxx.h"
673
674 #endif
675