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 // TODO reference types 13 // TODO addmul 14 15 // TODO document nmod_vecxx 16 17 #ifndef NMOD_VECXX_H 18 #define NMOD_VECXX_H 19 20 #include <sstream> 21 22 #include "nmod_vec.h" 23 24 // TODO reduce dependencies? 25 #include "fmpzxx.h" 26 #include "fmpqxx.h" 27 28 #include "flintxx/expression.h" 29 #include "flintxx/evaluation_tools.h" 30 #include "flintxx/flint_classes.h" 31 #include "flintxx/stdmath.h" 32 #include "flintxx/vector.h" 33 34 namespace flint { 35 ////////////////////////////////////////////////////////////////////////////// 36 // NMOD CLASS AND RULES 37 ////////////////////////////////////////////////////////////////////////////// 38 class nmodxx_ctx 39 { 40 private: 41 nmod_t nmod; 42 43 public: _nmod()44 const nmod_t& _nmod() const {return nmod;} nmodxx_ctx(mp_limb_t n)45 explicit nmodxx_ctx(mp_limb_t n) {nmod_init(&nmod, n);} 46 // no destruction necessary 47 48 bool operator==(const nmodxx_ctx& o) const {return nmod.n == o.nmod.n;} n()49 mp_limb_t n() const {return nmod.n;} 50 }; 51 52 class nmodxx_ctx_srcref 53 { 54 private: 55 const nmod_t& nmod; 56 nmodxx_ctx_srcref(const nmod_t & nm)57 nmodxx_ctx_srcref(const nmod_t& nm) : nmod(nm) {} 58 59 public: _nmod()60 const nmod_t& _nmod() const {return nmod;} nmodxx_ctx_srcref(const nmodxx_ctx & c)61 nmodxx_ctx_srcref(const nmodxx_ctx& c) : nmod(c._nmod()) {} 62 make(const nmod_t & nm)63 static nmodxx_ctx_srcref make(const nmod_t& nm) 64 {return nmodxx_ctx_srcref(nm);} 65 66 bool operator==(const nmodxx_ctx_srcref& o) const {return nmod.n == o.nmod.n;} n()67 mp_limb_t n() const {return nmod.n;} 68 }; 69 70 namespace detail { 71 struct nmodxx_fake_c_type { }; 72 } // detail 73 template<class Operation, class Data> 74 class nmodxx_expression 75 : public expression<derived_wrapper<nmodxx_expression>, Operation, Data> 76 { 77 public: 78 typedef expression<derived_wrapper< ::flint::nmodxx_expression>, 79 Operation, Data> base_t; 80 81 FLINTXX_DEFINE_BASICS(nmodxx_expression) FLINTXX_DEFINE_CTORS(nmodxx_expression)82 FLINTXX_DEFINE_CTORS(nmodxx_expression) 83 FLINTXX_DEFINE_C_REF(nmodxx_expression, detail::nmodxx_fake_c_type, _limb) 84 85 // static functions for nmodxx 86 static nmodxx_expression make_nored(mp_limb_t n, nmodxx_ctx_srcref c) 87 { 88 return nmodxx_expression(Data::make_nored(n, c)); 89 } red(mp_limb_t n,nmodxx_ctx_srcref c)90 static nmodxx_expression red(mp_limb_t n, nmodxx_ctx_srcref c) 91 { 92 nmodxx_expression res = make_nored(n, c); 93 res.reduce(); 94 return res; 95 } 96 template<class Fmpz> 97 static typename mp::enable_if< red(const Fmpz & n,nmodxx_ctx_srcref c)98 traits::is_fmpzxx<Fmpz>, nmodxx_expression>::type red( 99 const Fmpz& n, nmodxx_ctx_srcref c) 100 { 101 return make_nored((n % c.n()).template to<mp_limb_t>(), c); 102 } 103 template<class Fmpq> 104 static typename mp::enable_if< red(const Fmpq & n,nmodxx_ctx_srcref c)105 traits::is_fmpqxx<Fmpq>, nmodxx_expression>::type red( 106 const Fmpq& n, nmodxx_ctx_srcref c) 107 { 108 return make_nored((n % fmpzxx(c.n())).template to<mp_limb_t>(), c); 109 } 110 // TODO more 111 112 // only makes sense on immediates _ctx()113 nmodxx_ctx_srcref _ctx() const {return this->_data().ctx;} _nmod()114 const nmod_t& _nmod() const {return this->_data().ctx._nmod();} reduce()115 void reduce() {NMOD_RED(_limb(), _limb(), _nmod());} set_nored(mp_limb_t n)116 void set_nored(mp_limb_t n) {this->_data().inner = n;} 117 118 nmodxx_ctx_srcref estimate_ctx() const; 119 create_temporary()120 evaluated_t create_temporary() const 121 { 122 return evaluated_t(estimate_ctx()); 123 } 124 125 FLINTXX_DEFINE_MEMBER_BINOP(pow) 126 FLINTXX_DEFINE_MEMBER_UNOP(inv) 127 }; 128 129 namespace detail { 130 struct nmodxx_data; 131 } // detail 132 133 typedef nmodxx_expression<operations::immediate, detail::nmodxx_data> nmodxx; 134 typedef nmodxx_expression<operations::immediate, 135 flint_classes::ref_data<nmodxx, detail::nmodxx_fake_c_type> > nmodxx_ref; 136 typedef nmodxx_expression<operations::immediate, flint_classes::srcref_data< 137 nmodxx, nmodxx_ref, detail::nmodxx_fake_c_type> > nmodxx_srcref; 138 139 namespace flint_classes { 140 template<class Nmod> 141 struct ref_data<Nmod, detail::nmodxx_fake_c_type> 142 { 143 typedef void IS_REF_OR_CREF; 144 typedef Nmod wrapped_t; 145 146 typedef mp_limb_t& data_ref_t; 147 typedef const mp_limb_t& data_srcref_t; 148 149 mp_limb_t& inner; 150 nmodxx_ctx_srcref ctx; 151 152 ref_data(Nmod& o) : inner(o._data().inner), ctx(o._data().ctx) {} 153 154 static ref_data make(mp_limb_t& f, nmodxx_ctx_srcref ctx) 155 { 156 return ref_data(f, ctx); 157 } 158 159 private: 160 ref_data(mp_limb_t& fp, nmodxx_ctx_srcref c) : inner(fp), ctx(c) {} 161 }; 162 163 template<class Nmod, class Ref> 164 struct srcref_data<Nmod, Ref, detail::nmodxx_fake_c_type> 165 { 166 typedef void IS_REF_OR_CREF; 167 typedef Nmod wrapped_t; 168 169 typedef const mp_limb_t& data_ref_t; 170 typedef const mp_limb_t& data_srcref_t; 171 172 const mp_limb_t& inner; 173 nmodxx_ctx_srcref ctx; 174 175 srcref_data(const Nmod& o) : inner(o._data().inner), ctx(o._data().ctx) {} 176 srcref_data(Ref o) : inner(o._data().inner) {} 177 178 static srcref_data make(const mp_limb_t& f, nmodxx_ctx_srcref ctx) 179 { 180 return srcref_data(f, ctx); 181 } 182 183 private: 184 srcref_data(const mp_limb_t& fp, nmodxx_ctx_srcref c) : inner(fp), ctx(c) {} 185 }; 186 } // flint_classes 187 namespace detail { 188 struct nmodxx_data 189 { 190 nmodxx_ctx_srcref ctx; 191 mp_limb_t inner; 192 typedef mp_limb_t& data_ref_t; 193 typedef const mp_limb_t& data_srcref_t; 194 195 nmodxx_data(nmodxx_ctx_srcref c) : ctx(c), inner(0) {} 196 197 private: 198 nmodxx_data(mp_limb_t n, nmodxx_ctx_srcref c) 199 : ctx(c), inner(n) {} 200 201 public: 202 static nmodxx_data make_nored(mp_limb_t n, nmodxx_ctx_srcref c) 203 { 204 return nmodxx_data(n, c); 205 } 206 207 nmodxx_data(const nmodxx_srcref& r) 208 : ctx(r.estimate_ctx()), inner(r._limb()) {} 209 }; 210 } // detail 211 212 // Temporary merging isn't really any use here. On the other hand, it does 213 // not seem to hurt. Let's leave this for now. -- Tom Bachmann (15/10/2013) 214 #if 0 215 namespace traits { 216 template<> struct use_temporary_merging<nmodxx> : mp::false_ { }; 217 } // traits 218 #endif 219 220 namespace traits { 221 template<class T> struct has_nmodxx_ctx : mp::false_ { }; 222 223 template<> struct has_nmodxx_ctx<nmodxx> : mp::true_ { }; 224 template<> struct has_nmodxx_ctx<nmodxx_ref> : mp::true_ { }; 225 template<> struct has_nmodxx_ctx<nmodxx_srcref> : mp::true_ { }; 226 } // traits 227 228 namespace detail { 229 struct has_nmodxx_ctx_predicate 230 { 231 template<class T> struct type : traits::has_nmodxx_ctx<T> { }; 232 }; 233 234 // XXX this is needed for vectors ... 235 template<class T> 236 struct get_nmodxx_ctx 237 { 238 static nmodxx_ctx_srcref get(const T& t) {return t._ctx();} 239 }; 240 template<class T> 241 nmodxx_ctx_srcref get_nmodxx_ctx_func(const T& t) 242 { 243 return get_nmodxx_ctx<T>::get(t); 244 } 245 } // detail 246 namespace tools { 247 template<class Expr> 248 nmodxx_ctx_srcref find_nmodxx_ctx(const Expr& e) 249 { 250 return detail::get_nmodxx_ctx_func( 251 tools::find_subexpr<detail::has_nmodxx_ctx_predicate>(e)); 252 } 253 } // tools 254 template<class Operation, class Data> 255 inline nmodxx_ctx_srcref 256 nmodxx_expression<Operation, Data>::estimate_ctx() const 257 { 258 return tools::find_nmodxx_ctx(*this); 259 } 260 261 namespace traits { 262 template<class T> struct is_nmodxx : mp::or_< 263 traits::is_T_expr<T, nmodxx>, 264 flint_classes::is_source<nmodxx, T> > { }; 265 } // traits 266 267 namespace rules { 268 #define NMODXX_COND_S FLINTXX_COND_S(nmodxx) 269 #define NMODXX_COND_T FLINTXX_COND_T(nmodxx) 270 271 #define NMODXX_DEFINE_INSTANTIATE_TEMPORARIES(Classname) \ 272 template<class Expr> \ 273 struct use_default_temporary_instantiation<Expr, Classname> : mp::false_ { }; \ 274 template<class Expr> \ 275 struct instantiate_temporaries<Expr, Classname> \ 276 { \ 277 static Classname get(const Expr& e) \ 278 { \ 279 return Classname(tools::find_nmodxx_ctx(e)); \ 280 } \ 281 }; 282 283 // This is in order to make temporary allocation work even if there is no 284 // immediate subexpression - c/f test_temporaries 285 NMODXX_DEFINE_INSTANTIATE_TEMPORARIES(nmodxx) 286 287 FLINTXX_DEFINE_EQUALS(nmodxx, e1._limb() == e2._limb()) 288 289 FLINT_DEFINE_GET_COND(conversion, mp_limb_t, NMODXX_COND_S, from._limb()) 290 291 template<class Nmod> 292 struct to_string<Nmod, typename mp::enable_if< NMODXX_COND_S<Nmod> >::type> 293 { 294 static std::string get(const Nmod& i, int base /* ignored */) 295 { 296 std::ostringstream oss; 297 oss << i._limb() << " mod " << i._nmod().n; 298 return oss.str(); 299 } 300 }; 301 302 FLINT_DEFINE_DOIT_COND2(assignment, NMODXX_COND_T, NMODXX_COND_S, 303 to._limb() = from._limb()) 304 305 FLINT_DEFINE_CBINARY_EXPR_COND2(plus, nmodxx, NMODXX_COND_S, NMODXX_COND_S, 306 to.set_nored(nmod_add(e1._limb(), e2._limb(), to._nmod()))) 307 FLINT_DEFINE_CBINARY_EXPR_COND2(times, nmodxx, NMODXX_COND_S, NMODXX_COND_S, 308 to.set_nored(nmod_mul(e1._limb(), e2._limb(), to._nmod()))) 309 FLINT_DEFINE_BINARY_EXPR_COND2(minus, nmodxx, NMODXX_COND_S, NMODXX_COND_S, 310 to.set_nored(nmod_sub(e1._limb(), e2._limb(), to._nmod()))) 311 FLINT_DEFINE_BINARY_EXPR_COND2(divided_by, nmodxx, NMODXX_COND_S, NMODXX_COND_S, 312 to.set_nored(nmod_div(e1._limb(), e2._limb(), to._nmod()))) 313 314 FLINT_DEFINE_UNARY_EXPR_COND(negate, nmodxx, NMODXX_COND_S, 315 to.set_nored(nmod_neg(from._limb(), to._nmod()))) 316 317 FLINT_DEFINE_UNARY_EXPR_COND(inv_op, nmodxx, NMODXX_COND_S, 318 to.set_nored(nmod_inv(from._limb(), to._nmod()))) 319 320 FLINT_DEFINE_BINARY_EXPR_COND2(pow_op, nmodxx, NMODXX_COND_S, 321 traits::is_unsigned_integer, 322 to.set_nored(nmod_pow_ui(e1._limb(), e2, to._nmod()))) 323 } 324 325 ////////////////////////////////////////////////////////////////////////////// 326 // NMOD_VEC CLASS AND RULES 327 ////////////////////////////////////////////////////////////////////////////// 328 namespace detail { 329 struct nmod_vector_data 330 { 331 slong size; 332 mp_limb_t* array; 333 nmodxx_ctx_srcref ctx; 334 335 nmod_vector_data(slong n, nmodxx_ctx_srcref c) 336 : size(n), array(_nmod_vec_init(n)), ctx(c) {} 337 338 ~nmod_vector_data() {_nmod_vec_clear(array);} 339 340 nmod_vector_data(const nmod_vector_data& o) 341 : size(o.size), array(_nmod_vec_init(o.size)), ctx(o.ctx) 342 { 343 _nmod_vec_set(array, o.array, size); 344 } 345 346 nmodxx_ref at(slong i) {return nmodxx_ref::make(array[i], ctx);} 347 nmodxx_srcref at(slong i) const {return nmodxx_srcref::make(array[i], ctx);} 348 }; 349 350 struct nmod_vector_traits 351 : wrapped_vector_traits<nmodxx, slong, nmodxx_ref, nmodxx_srcref, mp_limb_t> 352 { 353 template<class Expr> 354 static typename Expr::evaluated_t create_temporary(const Expr& e) 355 { 356 return typename Expr::evaluated_t(e.size(), tools::find_nmodxx_ctx(e)); 357 } 358 }; 359 } // detail 360 361 // TODO would it make more sense to have this have its own class? 362 typedef vector_expression< 363 detail::nmod_vector_traits, operations::immediate, 364 detail::nmod_vector_data> nmod_vecxx; 365 // TODO references 366 367 namespace traits { 368 template<> struct has_nmodxx_ctx<nmod_vecxx> : mp::true_ { }; 369 } // traits 370 namespace detail { 371 template<> 372 struct get_nmodxx_ctx<nmod_vecxx> 373 { 374 static nmodxx_ctx_srcref get(const nmod_vecxx& v) 375 { 376 return v._data().ctx; 377 } 378 }; 379 } // detail 380 381 template<> 382 struct enable_vector_rules<nmod_vecxx> : mp::false_ { }; 383 384 namespace rules { 385 // TODO hack to make code look like references are implemented 386 template<class T> struct NMOD_VECXX_COND_S : mp::equal_types<T, nmod_vecxx> { }; 387 #define NMOD_VECXX_COND_T NMOD_VECXX_COND_S 388 389 // TODO references 390 FLINT_DEFINE_GET(equals, bool, nmod_vecxx, 391 e1.size() == e2.size() 392 && _nmod_vec_equal(e1._data().array, e2._data().array, e1.size())) 393 394 FLINT_DEFINE_BINARY_EXPR_COND2(plus, nmod_vecxx, 395 NMOD_VECXX_COND_S, NMOD_VECXX_COND_S, 396 _nmod_vec_add(to._data().array, e1._data().array, e2._data().array, 397 to.size(), to._data().ctx._nmod())) 398 399 // TODO more 400 } // rules 401 } // flint 402 403 #endif 404