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 CXX_FMPZXX_H
13 #define CXX_FMPZXX_H
14
15 #include <cstdlib>
16 #include <vector>
17
18 #include "flintxx/evaluation_tools.h"
19 #include "flintxx/expression.h"
20 #include "flintxx/expression_traits.h"
21 #include "flintxx/flint_classes.h"
22 #include "flintxx/frandxx.h"
23 #include "flintxx/ltuple.h"
24 #include "flintxx/stdmath.h"
25
26 #include "fmpz.h"
27
28 #undef clrbit /* no idea where these are coming from */
29 #undef setbit
30
31 // TODO functions for addmul? inhomogeneous addmul?
32 // TODO use evaluate_n in immediate functions?
33 // TODO fmpz_abs_ubound_ui_2exp, lbound
34 // TODO cmpabs
35 // TODO xgcd_partial
36
37 namespace flint {
38 FLINT_DEFINE_BINOP(cdiv_q)
FLINT_DEFINE_BINOP(fdiv_r)39 FLINT_DEFINE_BINOP(fdiv_r)
40 FLINT_DEFINE_BINOP(tdiv_q)
41 FLINT_DEFINE_BINOP(fdiv_r_2exp)
42 FLINT_DEFINE_BINOP(tdiv_q_2exp)
43 FLINT_DEFINE_UNOP(fac)
44 FLINT_DEFINE_UNOP(fib)
45 FLINT_DEFINE_BINOP(rfac)
46 FLINT_DEFINE_BINOP(bin)
47 FLINT_DEFINE_BINOP(gcd)
48 FLINT_DEFINE_BINOP(lcm)
49 FLINT_DEFINE_BINOP(invmod)
50 FLINT_DEFINE_BINOP(negmod)
51 FLINT_DEFINE_THREEARY(mul2)
52 FLINT_DEFINE_THREEARY(divexact2)
53 FLINT_DEFINE_THREEARY(powm)
54 FLINT_DEFINE_THREEARY(mul_tdiv_q_2exp)
55 FLINT_DEFINE_BINOP(fdiv_qr)
56 FLINT_DEFINE_BINOP(tdiv_qr)
57 FLINT_DEFINE_BINOP(sqrtmod)
58 FLINT_DEFINE_UNOP(sqrtrem)
59 FLINT_DEFINE_BINOP(gcdinv)
60 FLINT_DEFINE_BINOP(xgcd)
61 FLINT_DEFINE_BINOP(remove)
62
63 FLINT_DEFINE_FIVEARY(fmpzxx_bit_unpack)
64 FLINT_DEFINE_THREEARY(fmpzxx_bit_unpack_unsigned)
65
66 namespace mp {
67 template<class Out, class T1, class T2 = void, class T3 = void, class T4 = void>
68 struct enable_all_fmpzxx;
69 }
70
71 template<class Operation, class Data>
72 class fmpzxx_expression
73 : public expression<derived_wrapper<fmpzxx_expression>, Operation, Data>
74 {
75 public:
76 typedef expression<derived_wrapper< ::flint::fmpzxx_expression>,
77 Operation, Data> base_t;
78
79 FLINTXX_DEFINE_BASICS(fmpzxx_expression)
FLINTXX_DEFINE_CTORS(fmpzxx_expression)80 FLINTXX_DEFINE_CTORS(fmpzxx_expression)
81 FLINTXX_DEFINE_C_REF(fmpzxx_expression, fmpz, _fmpz)
82
83 // these only make sense with fmpzxx
84 FLINTXX_DEFINE_RANDFUNC(fmpz, randbits)
85 FLINTXX_DEFINE_RANDFUNC(fmpz, randtest)
86 FLINTXX_DEFINE_RANDFUNC(fmpz, randtest_unsigned)
87 FLINTXX_DEFINE_RANDFUNC(fmpz, randtest_not_zero)
88
89 template<class Fmpz>
90 static fmpzxx_expression randm(frandxx& state, const Fmpz& m)
91 {
92 fmpzxx_expression res;
93 fmpz_randm(res._fmpz(), state._data(), m.evaluate()._fmpz());
94 return res;
95 }
96 template<class Fmpz>
randtest_mod(frandxx & state,const Fmpz & m)97 static fmpzxx_expression randtest_mod(frandxx& state, const Fmpz& m)
98 {
99 fmpzxx_expression res;
100 fmpz_randtest_mod(res._fmpz(), state._data(), m.evaluate()._fmpz());
101 return res;
102 }
103 template<class Fmpz>
randtest_mod_signed(frandxx & state,const Fmpz & m)104 static fmpzxx_expression randtest_mod_signed(frandxx& state, const Fmpz& m)
105 {
106 fmpzxx_expression res;
107 fmpz_randtest_mod_signed(res._fmpz(), state._data(), m.evaluate()._fmpz());
108 return res;
109 }
110
111 // TODO would these make more sense static?
set_ui_smod(mp_limb_t x,mp_limb_t m)112 void set_ui_smod(mp_limb_t x, mp_limb_t m)
113 {
114 fmpz_set_ui_smod(this->_fmpz(), x, m);
115 }
set_uiui(mp_limb_t hi,mp_limb_t lo)116 void set_uiui(mp_limb_t hi, mp_limb_t lo)
117 {
118 fmpz_set_uiui(this->_fmpz(), hi, lo);
119 }
neg_uiui(mp_limb_t hi,mp_limb_t lo)120 void neg_uiui(mp_limb_t hi, mp_limb_t lo)
121 {
122 fmpz_neg_uiui(this->_fmpz(), hi, lo);
123 }
124 // these only make sense with fmpzxx/fmpzxx_ref
clrbit(ulong i)125 void clrbit(ulong i) {fmpz_clrbit(_fmpz(), i);}
combit(ulong i)126 void combit(ulong i) {fmpz_combit(_fmpz(), i);}
setbit(ulong i)127 void setbit(ulong i) {fmpz_setbit(_fmpz(), i);}
set_zero()128 void set_zero() {fmpz_zero(_fmpz());}
set_one()129 void set_one() {fmpz_one(_fmpz());}
130
131 // These make sense with all expressions, but cause evaluation
get_d_2exp(slong & exp)132 double get_d_2exp(slong& exp) const
133 {
134 return fmpz_get_d_2exp(&exp, this->evaluate()._fmpz());
135 }
is_zero()136 bool is_zero() const
137 {
138 return fmpz_is_zero(this->evaluate()._fmpz());
139 }
is_one()140 bool is_one() const
141 {
142 return fmpz_is_one(this->evaluate()._fmpz());
143 }
is_pm1()144 bool is_pm1() const
145 {
146 return fmpz_is_pm1(this->evaluate()._fmpz());
147 }
is_even()148 bool is_even() const
149 {
150 return fmpz_is_even(this->evaluate()._fmpz());
151 }
is_odd()152 bool is_odd() const
153 {
154 return fmpz_is_odd(this->evaluate()._fmpz());
155 }
is_square()156 bool is_square() const
157 {
158 return fmpz_is_square(this->evaluate()._fmpz());
159 }
popcnt()160 int popcnt() const
161 {
162 return fmpz_popcnt(this->evaluate()._fmpz());
163 }
is_probabprime()164 bool is_probabprime() const
165 {
166 return fmpz_is_probabprime(this->evaluate()._fmpz());
167 }
is_prime_pseudosquare()168 bool is_prime_pseudosquare() const
169 {
170 return fmpz_is_prime_pseudosquare(this->evaluate()._fmpz());
171 }
abs_fits_ui()172 bool abs_fits_ui() const
173 {
174 return fmpz_abs_fits_ui(this->evaluate()._fmpz());
175 }
fits_si()176 bool fits_si() const
177 {
178 return fmpz_fits_si(this->evaluate()._fmpz());
179 }
tstbit(ulong i)180 bool tstbit(ulong i) const
181 {
182 return fmpz_tstbit(this->evaluate()._fmpz(), i);
183 }
184
185 template<class T2>
186 typename mp::enable_all_fmpzxx<bool, T2>::type
divisible(const T2 & t2)187 divisible(const T2& t2) const
188 {
189 return fmpz_divisible(this->evaluate()._fmpz(), t2.evaluate()._fmpz());
190 }
191 template<class T2>
192 typename mp::enable_if<traits::fits_into_slong<T2>, bool>::type
divisible(const T2 & t2)193 divisible(const T2& t2) const
194 {
195 return fmpz_divisible_si(this->evaluate()._fmpz(), t2);
196 }
197 template<class Fmpz2>
198 typename mp::enable_all_fmpzxx<slong, Fmpz2>::type
clog(const Fmpz2 & b)199 clog(const Fmpz2& b) const
200 {
201 return fmpz_clog(this->evaluate()._fmpz(), b.evaluate()._fmpz());
202 }
203 template<class Int>
204 typename mp::enable_if<traits::is_unsigned_integer<Int>, slong>::type
clog(Int b)205 clog(Int b) const
206 {
207 return fmpz_clog_ui(this->evaluate()._fmpz(), b);
208 }
209 template<class Fmpz2>
210 typename mp::enable_all_fmpzxx<slong, Fmpz2>::type
flog(const Fmpz2 & b)211 flog(const Fmpz2& b) const
212 {
213 return fmpz_flog(this->evaluate()._fmpz(), b.evaluate()._fmpz());
214 }
215 template<class Int>
216 typename mp::enable_if<traits::is_unsigned_integer<Int>, slong>::type
flog(Int b)217 flog(Int b) const
218 {
219 return fmpz_flog_ui(this->evaluate()._fmpz(), b);
220 }
dlog()221 double dlog() const
222 {
223 return fmpz_dlog(this->evaluate()._fmpz());
224 }
225 template<class Fmpz2>
226 typename mp::enable_all_fmpzxx<int, Fmpz2>::type
jacobi(const Fmpz2 & p)227 jacobi(const Fmpz2& p) const
228 {
229 return fmpz_jacobi(this->evaluate()._fmpz(), p.evaluate()._fmpz());
230 }
231
sizeinbase(int b)232 size_t sizeinbase(int b) const
233 {return fmpz_sizeinbase(this->evaluate()._fmpz(), b);}
bits()234 flint_bitcnt_t bits() const
235 {return fmpz_bits(this->evaluate()._fmpz());}
size()236 flint_bitcnt_t size() const
237 {return fmpz_size(this->evaluate()._fmpz());}
val2()238 flint_bitcnt_t val2() const
239 {return fmpz_val2(this->evaluate()._fmpz());}
sgn()240 int sgn() const
241 {return fmpz_sgn(this->evaluate()._fmpz());}
242
243 // lazy function forwarding
244 FLINTXX_DEFINE_MEMBER_3OP(divexact2)
FLINTXX_DEFINE_MEMBER_3OP(mul2)245 FLINTXX_DEFINE_MEMBER_3OP(mul2)
246 FLINTXX_DEFINE_MEMBER_3OP(mul_tdiv_q_2exp)
247 FLINTXX_DEFINE_MEMBER_3OP(powm)
248 FLINTXX_DEFINE_MEMBER_BINOP(cdiv_q)
249 FLINTXX_DEFINE_MEMBER_BINOP(divexact)
250 FLINTXX_DEFINE_MEMBER_BINOP(fdiv_qr)
251 FLINTXX_DEFINE_MEMBER_BINOP(fdiv_r)
252 FLINTXX_DEFINE_MEMBER_BINOP(fdiv_r_2exp)
253 FLINTXX_DEFINE_MEMBER_BINOP(gcd)
254 FLINTXX_DEFINE_MEMBER_BINOP(gcdinv)
255 FLINTXX_DEFINE_MEMBER_BINOP(invmod)
256 FLINTXX_DEFINE_MEMBER_BINOP(lcm)
257 FLINTXX_DEFINE_MEMBER_BINOP(negmod)
258 FLINTXX_DEFINE_MEMBER_BINOP(pow)
259 FLINTXX_DEFINE_MEMBER_BINOP(remove)
260 FLINTXX_DEFINE_MEMBER_BINOP(rfac)
261 FLINTXX_DEFINE_MEMBER_BINOP(root)
262 FLINTXX_DEFINE_MEMBER_BINOP(sqrtmod)
263 FLINTXX_DEFINE_MEMBER_BINOP(tdiv_q)
264 FLINTXX_DEFINE_MEMBER_BINOP(tdiv_q_2exp)
265 FLINTXX_DEFINE_MEMBER_BINOP(tdiv_qr)
266 FLINTXX_DEFINE_MEMBER_BINOP(xgcd)
267 FLINTXX_DEFINE_MEMBER_UNOP(abs)
268 FLINTXX_DEFINE_MEMBER_UNOP(sqrt)
269 // FLINTXX_DEFINE_MEMBER_UNOP(sqrtrem) // TODO
270
271 FLINTXX_DEFINE_MEMBER_5OP(CRT)
272
273 template<class Arg1, class Arg2>
274 static FLINT_FIVEARY_ENABLE_RETTYPE(fmpzxx_bit_unpack,
275 Arg1, Arg2, flint_bitcnt_t, int, bool)
276 bit_unpack(const Arg1& arr, const Arg2& bits,
277 flint_bitcnt_t shift = 0, int negate = 0, bool borrow = false)
278 {
279 return fmpzxx_bit_unpack(arr, bits, shift, negate, borrow);
280 }
281 template<class Arg1, class Arg2>
FLINT_THREEARY_ENABLE_RETTYPE(fmpzxx_bit_unpack_unsigned,Arg1,Arg2,flint_bitcnt_t)282 static FLINT_THREEARY_ENABLE_RETTYPE(fmpzxx_bit_unpack_unsigned,
283 Arg1, Arg2, flint_bitcnt_t)
284 bit_unpack_unsigned(const Arg1& arr, const Arg2& bits, flint_bitcnt_t shift = 0)
285 {
286 return fmpzxx_bit_unpack_unsigned(arr, bits, shift);
287 }
288 };
289
290 namespace detail {
291 struct fmpz_data;
292 }
293
294 typedef fmpzxx_expression<operations::immediate, detail::fmpz_data> fmpzxx;
295 typedef fmpzxx_expression<operations::immediate,
296 flint_classes::ref_data<fmpzxx, fmpz> > fmpzxx_ref;
297 typedef fmpzxx_expression<operations::immediate,
298 flint_classes::srcref_data<fmpzxx, fmpzxx_ref, fmpz> > fmpzxx_srcref;
299
300 namespace detail {
301 struct fmpz_data
302 {
303 typedef fmpz_t& data_ref_t;
304 typedef const fmpz_t& data_srcref_t;
305
306 fmpz_t inner;
307
fmpz_datafmpz_data308 fmpz_data() {fmpz_init(inner);}
~fmpz_datafmpz_data309 ~fmpz_data() {fmpz_clear(inner);}
fmpz_datafmpz_data310 fmpz_data(const fmpz_data& o) {fmpz_init_set(inner, o.inner);}
311
312 template<class T>
fmpz_datafmpz_data313 fmpz_data(const T& t)
314 {
315 init(t);
316 }
317
318 template<class T>
initfmpz_data319 typename mp::enable_if<traits::is_unsigned_integer<T> >::type init(T t)
320 {
321 fmpz_init_set_ui(inner, t);
322 }
323 template<class T>
initfmpz_data324 typename mp::enable_if<traits::is_signed_integer<T> >::type init(T t)
325 {
326 fmpz_init(inner);
327 fmpz_set_si(inner, t);
328 }
329
initfmpz_data330 void init(double d)
331 {
332 fmpz_init(inner);
333 fmpz_set_d(inner, d);
334 }
335
initfmpz_data336 void init(const char* str)
337 {
338 fmpz_init(inner);
339 fmpz_set_str(inner, str, 10);
340 }
341
initfmpz_data342 void init(const fmpzxx_srcref& r)
343 {
344 fmpz_init_set(inner, r._fmpz());
345 }
346 };
347
348 } // detail
349
350 ///////////////////////////////////////////////////////////////////
351 // HELPERS
352 ///////////////////////////////////////////////////////////////////
353 namespace traits {
354 template<class T> struct is_fmpzxx : mp::or_<
355 traits::is_T_expr<T, fmpzxx>,
356 flint_classes::is_source<fmpzxx, T> > { };
357 } // traits
358 namespace mp {
359 template<class T1, class T2 = void, class T3 = void, class T4 = void>
360 struct all_fmpzxx : mp::and_<all_fmpzxx<T1>, all_fmpzxx<T2, T3, T4> > { };
361 template<class T>
362 struct all_fmpzxx<T, void, void, void> : traits::is_fmpzxx<T> { };
363
364 template<class Out, class T1, class T2, class T3, class T4>
365 struct enable_all_fmpzxx
366 : mp::enable_if<all_fmpzxx<T1, T2, T3, T4>, Out> { };
367 } // mp
368
369 ///////////////////////////////////////////////////////////////////
370 // RULES
371 ///////////////////////////////////////////////////////////////////
372 namespace rules {
373
374 #define FMPZXX_COND_S FLINTXX_COND_S(fmpzxx)
375 #define FMPZXX_COND_T FLINTXX_COND_T(fmpzxx)
376
377 FLINT_DEFINE_DOIT_COND2(assignment, FMPZXX_COND_T, FMPZXX_COND_S,
378 fmpz_set(to._fmpz(), from._fmpz()))
379
380 FLINT_DEFINE_DOIT_COND2(assignment,
381 FMPZXX_COND_T, traits::is_unsigned_integer,
382 fmpz_set_ui(to._fmpz(), from))
383
384 FLINT_DEFINE_DOIT_COND2(assignment,
385 FMPZXX_COND_T, traits::is_signed_integer,
386 fmpz_set_si(to._fmpz(), from))
387
388 FLINTXX_DEFINE_CMP(fmpzxx, fmpz_cmp(e1._fmpz(), e2._fmpz()))
389
390 template<class T, class U>
391 struct cmp<T, U,
392 typename mp::enable_if<mp::and_<
393 FMPZXX_COND_S<T>, traits::is_signed_integer<U> > >::type>
394 {
395 static int get(const T& v, const U& t)
396 {
397 return fmpz_cmp_si(v._fmpz(), t);
398 }
399 };
400
401 template<class T>
402 struct cmp<fmpzxx, T,
403 typename mp::enable_if<traits::is_unsigned_integer<T> >::type>
404 {
405 static int get(const fmpzxx& v, const T& t)
406 {
407 return fmpz_cmp_ui(v._fmpz(), t);
408 }
409 };
410
411 FLINTXX_DEFINE_ASSIGN_STR(fmpzxx, fmpz_set_str(to._fmpz(), from, 10))
412 FLINTXX_DEFINE_TO_STR(fmpzxx, fmpz_get_str(0, base, from._fmpz()))
413
414 FLINTXX_DEFINE_SWAP(fmpzxx, fmpz_swap(e1._fmpz(), e2._fmpz()))
415
416 FLINT_DEFINE_PRINT_COND(FMPZXX_COND_S, fmpz_fprint(to, from._fmpz()))
417 FLINT_DEFINE_READ_COND(FMPZXX_COND_T, fmpz_fread(from, to._fmpz()))
418
419 FLINT_DEFINE_GET_COND(conversion, slong, FMPZXX_COND_S,
420 fmpz_get_si(from._fmpz()))
421 FLINT_DEFINE_GET_COND(conversion, ulong, FMPZXX_COND_S,
422 fmpz_get_ui(from._fmpz()))
423 FLINT_DEFINE_GET_COND(conversion, double, FMPZXX_COND_S,
424 fmpz_get_d(from._fmpz()))
425
426 FLINT_DEFINE_BINARY_EXPR_COND2(plus, fmpzxx, FMPZXX_COND_S, FMPZXX_COND_S,
427 fmpz_add(to._fmpz(), e1._fmpz(), e2._fmpz()))
428
429 FLINT_DEFINE_CBINARY_EXPR_COND2(plus, fmpzxx,
430 FMPZXX_COND_S, traits::is_unsigned_integer,
431 fmpz_add_ui(to._fmpz(), e1._fmpz(), e2))
432
433 FLINT_DEFINE_CBINARY_EXPR_COND2(plus, fmpzxx,
434 FMPZXX_COND_S, traits::is_signed_integer,
435 fmpz_add_si(to._fmpz(), e1._fmpz(), e2))
436
437 FLINT_DEFINE_CBINARY_EXPR_COND2(times, fmpzxx, FMPZXX_COND_S, FMPZXX_COND_S,
438 fmpz_mul(to._fmpz(), e1._fmpz(), e2._fmpz()))
439
440 FLINT_DEFINE_CBINARY_EXPR_COND2(times, fmpzxx,
441 FMPZXX_COND_S, traits::is_unsigned_integer,
442 fmpz_mul_ui(to._fmpz(), e1._fmpz(), e2))
443
444 FLINT_DEFINE_CBINARY_EXPR_COND2(times, fmpzxx,
445 FMPZXX_COND_S, traits::is_signed_integer,
446 fmpz_mul_si(to._fmpz(), e1._fmpz(), e2))
447
448 FLINT_DEFINE_BINARY_EXPR_COND2(minus, fmpzxx, FMPZXX_COND_S, FMPZXX_COND_S,
449 fmpz_sub(to._fmpz(), e1._fmpz(), e2._fmpz()))
450
451 FLINT_DEFINE_BINARY_EXPR_COND2(minus, fmpzxx,
452 FMPZXX_COND_S, traits::is_unsigned_integer,
453 fmpz_sub_ui(to._fmpz(), e1._fmpz(), e2))
454
455 FLINT_DEFINE_BINARY_EXPR_COND2(minus, fmpzxx,
456 FMPZXX_COND_S, traits::is_signed_integer,
457 fmpz_sub_si(to._fmpz(), e1._fmpz(), e2))
458
459 FLINT_DEFINE_BINARY_EXPR_COND2(divided_by, fmpzxx, FMPZXX_COND_S, FMPZXX_COND_S,
460 fmpz_fdiv_q(to._fmpz(), e1._fmpz(), e2._fmpz()))
461
462 FLINT_DEFINE_BINARY_EXPR_COND2(divided_by, fmpzxx,
463 FMPZXX_COND_S, traits::is_unsigned_integer,
464 fmpz_fdiv_q_ui(to._fmpz(), e1._fmpz(), e2))
465
466 FLINT_DEFINE_BINARY_EXPR_COND2(divided_by, fmpzxx,
467 FMPZXX_COND_S, traits::is_signed_integer,
468 fmpz_fdiv_q_si(to._fmpz(), e1._fmpz(), e2))
469
470 // TODO this interpretation of mod is not the same as for builtin types!
471 FLINT_DEFINE_BINARY_EXPR_COND2(modulo, fmpzxx, FMPZXX_COND_S, FMPZXX_COND_S,
472 fmpz_mod(to._fmpz(), e1._fmpz(), e2._fmpz()))
473
474 FLINT_DEFINE_BINARY_EXPR_COND2(modulo, fmpzxx,
475 FMPZXX_COND_S, traits::is_unsigned_integer,
476 fmpz_mod_ui(to._fmpz(), e1._fmpz(), e2))
477
478 FLINT_DEFINE_BINARY_EXPR_COND2(binary_and, fmpzxx, FMPZXX_COND_S, FMPZXX_COND_S,
479 fmpz_and(to._fmpz(), e1._fmpz(), e2._fmpz()))
480
481 FLINT_DEFINE_BINARY_EXPR_COND2(binary_or, fmpzxx, FMPZXX_COND_S, FMPZXX_COND_S,
482 fmpz_or(to._fmpz(), e1._fmpz(), e2._fmpz()))
483
484 FLINT_DEFINE_BINARY_EXPR_COND2(binary_xor, fmpzxx, FMPZXX_COND_S, FMPZXX_COND_S,
485 fmpz_xor(to._fmpz(), e1._fmpz(), e2._fmpz()))
486
487 FLINT_DEFINE_UNARY_EXPR_COND(negate, fmpzxx, FMPZXX_COND_S,
488 fmpz_neg(to._fmpz(), from._fmpz()))
489
490 FLINT_DEFINE_UNARY_EXPR_COND(complement, fmpzxx, FMPZXX_COND_S,
491 fmpz_complement(to._fmpz(), from._fmpz()))
492
493 namespace rdetail {
494 template<class Fmpz1, class Fmpz2, class T>
495 void fmpzxx_shift(Fmpz1& to, const Fmpz2& from, T howmuch)
496 {
497 if(howmuch < 0)
498 fmpz_fdiv_q_2exp(to._fmpz(), from._fmpz(), -howmuch);
499 else
500 fmpz_mul_2exp(to._fmpz(), from._fmpz(), howmuch);
501 }
502 } // rdetail
503 FLINT_DEFINE_BINARY_EXPR_COND2(shift, fmpzxx,
504 FMPZXX_COND_S, traits::is_integer,
505 rdetail::fmpzxx_shift(to, e1, e2))
506 } // rules
507
508 FLINTXX_DEFINE_TERNARY(fmpzxx,
509 fmpz_addmul(to._fmpz(), e1._fmpz(), e2._fmpz()),
510 fmpz_submul(to._fmpz(), e1._fmpz(), e2._fmpz()),
511 FLINTXX_UNADORNED_MAKETYPES)
512
513 ///////////////////////////////////////////////////////////////////////////
514 // FUNCTIONS
515 ///////////////////////////////////////////////////////////////////////////
516
517 // These functions evaluate immediately, and (often) do not yield fmpzxxs
518
519 template<class T1, class T2>
520 inline typename mp::enable_all_fmpzxx<bool, T1>::type
521 divisible(const T1& t1, const T2& t2)
522 {
523 return t1.divisible(t2);
524 }
525
526 template<class Fmpz1, class Fmpz2>
527 inline typename mp::enable_all_fmpzxx<slong, Fmpz1>::type
528 clog(const Fmpz1& x, const Fmpz2& b)
529 {
530 return x.clog(b);
531 }
532
533 template<class Fmpz1, class Fmpz2>
534 inline typename mp::enable_all_fmpzxx<slong, Fmpz1>::type
535 flog(const Fmpz1& x, const Fmpz2& b)
536 {
537 return x.flog(b);
538 }
539
540 template<class Fmpz>
541 inline typename mp::enable_if<traits::is_fmpzxx<Fmpz>, double>::type
542 dlog(const Fmpz& x)
543 {
544 return x.dlog();
545 }
546
547 template<class Fmpz1, class Fmpz2>
548 inline typename mp::enable_all_fmpzxx<int, Fmpz1>::type
549 jacobi(const Fmpz1& a, const Fmpz2& p)
550 {
551 return a.jacobi(p);
552 }
553
554 template<class Fmpz>
555 inline typename mp::enable_if<traits::is_fmpzxx<Fmpz>, size_t>::type
556 sizeinbase(const Fmpz& a, int b)
557 {
558 return a.sizeinbase(b);
559 }
560 template<class Fmpz>
561 inline typename mp::enable_if<traits::is_fmpzxx<Fmpz>, flint_bitcnt_t>::type
562 bits(const Fmpz& a)
563 {
564 return a.bits();
565 }
566 template<class Fmpz>
567 inline typename mp::enable_if<traits::is_fmpzxx<Fmpz>, flint_bitcnt_t>::type
568 val2(const Fmpz& a)
569 {
570 return a.val2();
571 }
572 template<class Fmpz>
573 inline typename mp::enable_if<traits::is_fmpzxx<Fmpz>, flint_bitcnt_t>::type
574 size(const Fmpz& a)
575 {
576 return a.size();
577 }
578 template<class Fmpz>
579 inline typename mp::enable_if<traits::is_fmpzxx<Fmpz>, int>::type
580 sgn(const Fmpz& a)
581 {
582 return a.sgn();
583 }
584
585 template<class Fmpz>
586 inline bool bit_pack(std::vector<mp_limb_t>& arr, flint_bitcnt_t bits,
587 const Fmpz& coeff, flint_bitcnt_t shift = 0, int negate = 0,
588 bool borrow = false,
589 typename mp::enable_if<traits::is_fmpzxx<Fmpz> >::type* = 0)
590 {
591 return fmpz_bit_pack(&arr.front(), shift, bits,
592 coeff.evaluate()._fmpz(), negate, borrow);
593 }
594
595 // These functions are evaluated lazily
596 namespace rules {
597 FLINT_DEFINE_BINARY_EXPR_COND2(rfac_op, fmpzxx,
598 FMPZXX_COND_S, traits::is_unsigned_integer,
599 fmpz_rfac_ui(to._fmpz(), e1._fmpz(), e2))
600 FLINT_DEFINE_UNARY_EXPR_COND(fac_op, fmpzxx, traits::is_unsigned_integer,
601 fmpz_fac_ui(to._fmpz(), from))
602 FLINT_DEFINE_UNARY_EXPR_COND(fib_op, fmpzxx, traits::is_unsigned_integer,
603 fmpz_fib_ui(to._fmpz(), from))
604 FLINT_DEFINE_BINARY_EXPR_COND2(gcd_op, fmpzxx, FMPZXX_COND_S, FMPZXX_COND_S,
605 fmpz_gcd(to._fmpz(), e1._fmpz(), e2._fmpz()))
606 FLINT_DEFINE_BINARY_EXPR_COND2(lcm_op, fmpzxx, FMPZXX_COND_S, FMPZXX_COND_S,
607 fmpz_lcm(to._fmpz(), e1._fmpz(), e2._fmpz()))
608
609 template<class T1, class T2>
610 struct binary_expression<
611 T1,
612 typename mp::enable_if<
613 mp::and_<
614 traits::is_unsigned_integer<T1>,
615 traits::is_unsigned_integer<T2> >,
616 operations::bin_op>::type,
617 T2>
618 {
619 typedef fmpzxx return_t;
620 template<class V>
621 static void doit(V& to, const T1& t1, const T2& t2)
622 {
623 fmpz_bin_uiui(to._fmpz(), t1, t2);
624 }
625 };
626
627 #define FMPZXX_DEFINE_DIVFUNCS(name) \
628 FLINT_DEFINE_BINARY_EXPR_COND2(name##_op, fmpzxx, FMPZXX_COND_S, FMPZXX_COND_S, \
629 fmpz_##name(to._fmpz(), e1._fmpz(), e2._fmpz())) \
630 FLINT_DEFINE_BINARY_EXPR_COND2(name##_op, fmpzxx, FMPZXX_COND_S, \
631 traits::is_signed_integer, \
632 fmpz_##name##_si(to._fmpz(), e1._fmpz(), e2)) \
633 FLINT_DEFINE_BINARY_EXPR_COND2(name##_op, fmpzxx, FMPZXX_COND_S, \
634 traits::is_unsigned_integer, \
635 fmpz_##name##_ui(to._fmpz(), e1._fmpz(), e2))
636
637 FMPZXX_DEFINE_DIVFUNCS(cdiv_q)
638 FMPZXX_DEFINE_DIVFUNCS(tdiv_q)
639 FMPZXX_DEFINE_DIVFUNCS(divexact)
640 FLINT_DEFINE_BINARY_EXPR_COND2(fdiv_r_op, fmpzxx, FMPZXX_COND_S, FMPZXX_COND_S,
641 fmpz_fdiv_r(to._fmpz(), e1._fmpz(), e2._fmpz()))
642
643 FLINT_DEFINE_BINARY_EXPR_COND2(tdiv_q_2exp_op, fmpzxx,
644 FMPZXX_COND_S, traits::is_unsigned_integer,
645 fmpz_tdiv_q_2exp(to._fmpz(), e1._fmpz(), e2))
646 FLINT_DEFINE_BINARY_EXPR_COND2(fdiv_r_2exp_op, fmpzxx,
647 FMPZXX_COND_S, traits::is_unsigned_integer,
648 fmpz_fdiv_r_2exp(to._fmpz(), e1._fmpz(), e2))
649
650 FLINT_DEFINE_BINARY_EXPR_COND2(invmod_op, fmpzxx,
651 FMPZXX_COND_S, FMPZXX_COND_S,
652 fmpz_invmod(to._fmpz(), e1._fmpz(), e2._fmpz()))
653 FLINT_DEFINE_BINARY_EXPR_COND2(negmod_op, fmpzxx,
654 FMPZXX_COND_S, FMPZXX_COND_S,
655 fmpz_negmod(to._fmpz(), e1._fmpz(), e2._fmpz()))
656
657 FLINT_DEFINE_THREEARY_EXPR_COND3(mul2_op, fmpzxx,
658 FMPZXX_COND_S, traits::is_unsigned_integer, traits::is_unsigned_integer,
659 fmpz_mul2_uiui(to._fmpz(), e1._fmpz(), e2, e3))
660 FLINT_DEFINE_THREEARY_EXPR_COND3(divexact2_op, fmpzxx,
661 FMPZXX_COND_S, traits::is_unsigned_integer, traits::is_unsigned_integer,
662 fmpz_divexact2_uiui(to._fmpz(), e1._fmpz(), e2, e3))
663
664 FLINT_DEFINE_THREEARY_EXPR_COND3(powm_op, fmpzxx,
665 FMPZXX_COND_S, traits::is_unsigned_integer, FMPZXX_COND_S,
666 fmpz_powm_ui(to._fmpz(), e1._fmpz(), e2, e3._fmpz()))
667 FLINT_DEFINE_THREEARY_EXPR_COND3(powm_op, fmpzxx,
668 FMPZXX_COND_S, FMPZXX_COND_S, FMPZXX_COND_S,
669 fmpz_powm(to._fmpz(), e1._fmpz(), e2._fmpz(), e3._fmpz()))
670
671 FLINT_DEFINE_THREEARY_EXPR_COND3(mul_tdiv_q_2exp_op, fmpzxx,
672 FMPZXX_COND_S, FMPZXX_COND_S, traits::is_unsigned_integer,
673 fmpz_mul_tdiv_q_2exp(to._fmpz(), e1._fmpz(), e2._fmpz(), e3))
674 FLINT_DEFINE_THREEARY_EXPR_COND3(mul_tdiv_q_2exp_op, fmpzxx,
675 FMPZXX_COND_S, traits::fits_into_slong, traits::is_unsigned_integer,
676 fmpz_mul_si_tdiv_q_2exp(to._fmpz(), e1._fmpz(), e2, e3))
677 // TODO addmul, submul?
678
679 namespace rdetail {
680 typedef make_ltuple<mp::make_tuple<fmpzxx, fmpzxx>::type>::type fmpzxx_pair;
681 typedef make_ltuple<mp::make_tuple<fmpzxx, fmpzxx, fmpzxx>::type>::type fmpzxx_triple;
682 typedef make_ltuple<mp::make_tuple<bool, fmpzxx>::type>::type
683 bool_fmpzxx_pair;
684 } // rdetail
685
686 FLINT_DEFINE_BINARY_EXPR_COND2(fdiv_qr_op, rdetail::fmpzxx_pair,
687 FMPZXX_COND_S, FMPZXX_COND_S,
688 fmpz_fdiv_qr(to.template get<0>()._fmpz(), to.template get<1>()._fmpz(),
689 e1._fmpz(), e2._fmpz()))
690 FLINT_DEFINE_BINARY_EXPR_COND2(tdiv_qr_op, rdetail::fmpzxx_pair,
691 FMPZXX_COND_S, FMPZXX_COND_S,
692 fmpz_tdiv_qr(to.template get<0>()._fmpz(), to.template get<1>()._fmpz(),
693 e1._fmpz(), e2._fmpz()))
694
695 FLINT_DEFINE_BINARY_EXPR_COND2(sqrtmod_op, rdetail::bool_fmpzxx_pair,
696 FMPZXX_COND_S, FMPZXX_COND_S,
697 to.template get<0>() = fmpz_sqrtmod(
698 to.template get<1>()._fmpz(), e1._fmpz(), e2._fmpz()))
699
700 FLINT_DEFINE_UNARY_EXPR_COND(sqrtrem_op, rdetail::fmpzxx_pair,
701 FMPZXX_COND_S,
702 fmpz_sqrtrem(to.template get<0>()._fmpz(), to.template get<1>()._fmpz(),
703 from._fmpz()))
704
705 FLINT_DEFINE_BINARY_EXPR_COND2(gcdinv_op, rdetail::fmpzxx_pair,
706 FMPZXX_COND_S, FMPZXX_COND_S,
707 fmpz_gcdinv(to.template get<0>()._fmpz(), to.template get<1>()._fmpz(),
708 e1._fmpz(), e2._fmpz()))
709 FLINT_DEFINE_BINARY_EXPR_COND2(xgcd_op, rdetail::fmpzxx_triple,
710 FMPZXX_COND_S, FMPZXX_COND_S, fmpz_xgcd(
711 to.template get<0>()._fmpz(), to.template get<1>()._fmpz(),
712 to.template get<2>()._fmpz(), e1._fmpz(), e2._fmpz()))
713
714 namespace rdetail {
715 template<class T> struct is_mplimb_t_vec
716 : mp::equal_types<T, std::vector<mp_limb_t> > { };
717 }
718 FLINT_DEFINE_FIVEARY_EXPR_COND5(fmpzxx_bit_unpack_op, rdetail::bool_fmpzxx_pair,
719 rdetail::is_mplimb_t_vec, traits::fits_into_flint_bitcnt_t,
720 traits::fits_into_flint_bitcnt_t, traits::is_integer, tools::is_bool,
721 to.template get<0>() = fmpz_bit_unpack(to.template get<1>()._fmpz(),
722 &e1.front(), e3, e2, e4, e5))
723 FLINT_DEFINE_THREEARY_EXPR_COND3(fmpzxx_bit_unpack_unsigned_op, fmpzxx,
724 rdetail::is_mplimb_t_vec, traits::fits_into_flint_bitcnt_t,
725 traits::fits_into_flint_bitcnt_t,
726 fmpz_bit_unpack_unsigned(to._fmpz(), &e1.front(), e3, e2))
727
728 // standard math functions (c/f stdmath.h)
729 FLINT_DEFINE_BINARY_EXPR_COND2(pow_op, fmpzxx,
730 FMPZXX_COND_S, traits::is_unsigned_integer,
731 fmpz_pow_ui(to._fmpz(), e1._fmpz(), e2))
732 FLINT_DEFINE_BINARY_EXPR_COND2(root_op, fmpzxx,
733 FMPZXX_COND_S, traits::fits_into_slong,
734 fmpz_root(to._fmpz(), e1._fmpz(), e2))
735 FLINT_DEFINE_UNARY_EXPR_COND(sqrt_op, fmpzxx, FMPZXX_COND_S,
736 fmpz_sqrt(to._fmpz(), from._fmpz()))
737 FLINT_DEFINE_UNARY_EXPR_COND(abs_op, fmpzxx, FMPZXX_COND_S,
738 fmpz_abs(to._fmpz(), from._fmpz()))
739
740 namespace rdetail {
741 typedef make_ltuple<mp::make_tuple<slong, fmpzxx>::type>::type slong_fmpzxx_pair;
742 } // rdetail
743 FLINT_DEFINE_BINARY_EXPR_COND2(remove_op, rdetail::slong_fmpzxx_pair,
744 FMPZXX_COND_S, FMPZXX_COND_S,
745 to.template get<0>() = fmpz_remove(to.template get<1>()._fmpz(),
746 e1._fmpz(), e2._fmpz()))
747 } // rules
748
749 // chinese remaindering
750 // TODO should this use nmod?
751 class fmpz_combxx
752 {
753 private:
754 fmpz_comb_t comb;
755 mutable fmpz_comb_temp_t tmp;
756
757 // not copyable
758 fmpz_combxx(const fmpz_combxx&);
759
760 public:
761 fmpz_combxx(const std::vector<mp_limb_t>& v)
762 {
763 fmpz_comb_init(comb, &v.front(), v.size());
764 fmpz_comb_temp_init(tmp, comb);
765 }
766
767 ~fmpz_combxx()
768 {
769 fmpz_comb_temp_clear(tmp);
770 fmpz_comb_clear(comb);
771 }
772
773 const fmpz_comb_t& _comb() const {return comb;}
774 fmpz_comb_temp_t& _temp() const {return tmp;}
775 };
776
777 // TODO make lazy somehow?
778 template<class Fmpz>
779 inline typename mp::enable_if<traits::is_fmpzxx<Fmpz> >::type
780 multi_mod(std::vector<mp_limb_t>& out, const Fmpz& in, const fmpz_combxx& comb)
781 {
782 fmpz_multi_mod_ui(&out.front(), in.evaluate()._fmpz(),
783 comb._comb(), comb._temp());
784 }
785
786 namespace rules {
787 FLINT_DEFINE_FIVEARY_EXPR_COND5(CRT_op, fmpzxx, FMPZXX_COND_S, FMPZXX_COND_S,
788 traits::is_unsigned_integer, traits::is_unsigned_integer, tools::is_bool,
789 fmpz_CRT_ui(to._fmpz(), e1._fmpz(), e2._fmpz(), e3, e4, e5))
790
791 FLINT_DEFINE_THREEARY_EXPR(multi_CRT_op, fmpzxx,
792 std::vector<mp_limb_t>, fmpz_combxx, bool,
793 fmpz_multi_CRT_ui(to._fmpz(), &e1.front(), e2._comb(), e2._temp(), e3))
794 } // rules
795 } // flint
796
797 #include "fmpz_factorxx.h"
798
799 #endif
800