1 /* Copyright (C) 2010 LinBox 2 * 3 * 4 * 5 * ========LICENCE======== 6 * This file is part of the library LinBox. 7 * 8 * LinBox is free software: you can redistribute it and/or modify 9 * it under the terms of the GNU Lesser General Public 10 * License as published by the Free Software Foundation; either 11 * version 2.1 of the License, or (at your option) any later version. 12 * 13 * This library is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 * Lesser General Public License for more details. 17 * 18 * You should have received a copy of the GNU Lesser General Public 19 * License along with this library; if not, write to the Free Software 20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 21 * ========LICENCE======== 22 */ 23 24 /*! @file field/modular/modular-byte.h 25 * @ingroup field 26 * @brief representation of <code>Z/mZ</code> over \c byte . 27 */ 28 #ifndef __LINBOX_modular_bit_H 29 #define __LINBOX_modular_bit_H 30 31 32 #include "linbox/linbox-config.h" 33 #include "linbox/integer.h" 34 #include "linbox/vector/vector-domain.h" 35 #include "linbox/ring/modular.h" 36 #include "linbox/field/field-traits.h" 37 #include "linbox/util/debug.h" 38 #include "linbox/field/field-traits.h" 39 40 #ifndef LINBOX_MAX_INT8 /* 127 */ 41 #define LINBOX_MAX_INT8 INT8_MAX 42 #endif 43 44 #ifdef __ICC 45 #pragma warning(disable:2259) 46 #endif 47 48 // Namespace in which all LinBox code resides 49 namespace LinBox 50 { 51 52 template<class Field> 53 class FieldAXPY; 54 55 template<class Field> 56 class DotProductDomain; 57 58 template<class Field> 59 class MVProductDomain; 60 61 template <> 62 class FieldAXPY<Givaro::Modular<int8_t> > { 63 public: 64 65 typedef int8_t Element; 66 typedef int64_t Abnormal; 67 typedef Givaro::Modular<int8_t> Field; 68 FieldAXPY(const Field & F)69 FieldAXPY (const Field &F) : 70 _field (&F),_y(0) 71 { 72 } 73 FieldAXPY(const FieldAXPY & faxpy)74 FieldAXPY (const FieldAXPY &faxpy) : 75 _field (faxpy._field), _y (0) 76 {} 77 78 FieldAXPY<Givaro::Modular<int8_t> > &operator = (const FieldAXPY &faxpy) 79 { 80 _field = faxpy._field; 81 _y = faxpy._y; 82 83 return *this; 84 } 85 mulacc(const Element & a,const Element & x)86 inline uint64_t& mulacc (const Element &a, const Element &x) 87 { 88 uint64_t t = ( (uint16_t) a ) * ( (uint16_t) x ); 89 return _y +=t; 90 } 91 accumulate(const Element & t)92 inline uint64_t& accumulate (const Element &t) 93 { 94 return _y += (uint64_t)t; 95 } 96 get(Element & y)97 inline Element& get (Element &y) 98 { 99 y = Element(_y % (uint64_t) field().characteristic()); 100 return y; 101 } 102 assign(const Element y)103 inline FieldAXPY &assign (const Element y) 104 { 105 _y = (uint64_t) y; 106 return *this; 107 } 108 reset()109 inline void reset() 110 { 111 _y = 0; 112 } 113 field()114 inline const Field & field() const { return *_field; } 115 116 private: 117 118 const Field *_field; 119 uint64_t _y; 120 // uint8_t _two_64; // BB : not used 121 }; 122 123 124 template <> 125 class DotProductDomain<Givaro::Modular<int8_t> > : public VectorDomainBase<Givaro::Modular<int8_t> > { 126 127 public: 128 typedef int8_t Element; DotProductDomain()129 DotProductDomain(){} DotProductDomain(const Givaro::Modular<int8_t> & F)130 DotProductDomain (const Givaro::Modular<int8_t> &F) : 131 VectorDomainBase<Givaro::Modular<int8_t> > (F) 132 { } 133 134 using VectorDomainBase<Givaro::Modular<int8_t> >::field; 135 protected: 136 template <class Vector1, class Vector2> dotSpecializedDD(Element & res,const Vector1 & v1,const Vector2 & v2)137 inline Element &dotSpecializedDD (Element &res, const Vector1 &v1, const Vector2 &v2) const 138 { 139 140 typename Vector1::const_iterator i; 141 typename Vector2::const_iterator j; 142 143 uint64_t y = 0; 144 // uint64_t t; 145 146 for (i = v1.begin (), j = v2.begin (); i < v1.end (); ++i, ++j) { 147 y += ( (uint16_t) *i ) * ( (uint16_t) *j ); 148 } 149 150 151 y %= (uint64_t) field().characteristic(); 152 153 return res = (Element) y; 154 155 } 156 157 template <class Vector1, class Vector2> dotSpecializedDSP(Element & res,const Vector1 & v1,const Vector2 & v2)158 inline Element &dotSpecializedDSP (Element &res, const Vector1 &v1, const Vector2 &v2) const 159 { 160 typename Vector1::first_type::const_iterator i_idx; 161 typename Vector1::second_type::const_iterator i_elt; 162 163 uint64_t y = 0; 164 165 for (i_idx = v1.first.begin (), i_elt = v1.second.begin (); i_idx != v1.first.end (); ++i_idx, ++i_elt) { 166 y += ( (uint16_t) *i_elt ) * ( (uint16_t) v2[*i_idx] ); 167 } 168 169 y %= (uint64_t) field().characteristic(); 170 171 return res = (Element)y; 172 173 } 174 175 }; 176 177 178 template <> 179 class MVProductDomain<Givaro::Modular<int8_t> > 180 { 181 public: 182 183 typedef int8_t Element; 184 185 protected: 186 template <class Vector1, class Matrix, class Vector2> mulColDense(const VectorDomain<Givaro::Modular<int8_t>> & VD,Vector1 & w,const Matrix & A,const Vector2 & v)187 inline Vector1 &mulColDense 188 (const VectorDomain<Givaro::Modular<int8_t> > &VD, Vector1 &w, const Matrix &A, const Vector2 &v) const 189 { 190 return mulColDenseSpecialized 191 (VD, w, A, v, VectorTraits<typename Matrix::Column>::VectorCategory ()); 192 } 193 194 private: 195 template <class Vector1, class Matrix, class Vector2> 196 Vector1 &mulColDenseSpecialized 197 (const VectorDomain<Givaro::Modular<int8_t> > &VD, Vector1 &w, const Matrix &A, const Vector2 &v, 198 VectorCategories::DenseVectorTag) const; 199 template <class Vector1, class Matrix, class Vector2> 200 Vector1 &mulColDenseSpecialized 201 (const VectorDomain<Givaro::Modular<int8_t> > &VD, Vector1 &w, const Matrix &A, const Vector2 &v, 202 VectorCategories::SparseSequenceVectorTag) const; 203 template <class Vector1, class Matrix, class Vector2> 204 Vector1 &mulColDenseSpecialized 205 (const VectorDomain<Givaro::Modular<int8_t> > &VD, Vector1 &w, const Matrix &A, const Vector2 &v, 206 VectorCategories::SparseAssociativeVectorTag) const; 207 template <class Vector1, class Matrix, class Vector2> 208 Vector1 &mulColDenseSpecialized 209 (const VectorDomain<Givaro::Modular<int8_t> > &VD, Vector1 &w, const Matrix &A, const Vector2 &v, 210 VectorCategories::SparseParallelVectorTag) const; 211 212 mutable std::vector<uint64_t> _tmp; 213 }; 214 215 template <class Vector1, class Matrix, class Vector2> mulColDenseSpecialized(const VectorDomain<Givaro::Modular<int8_t>> & VD,Vector1 & w,const Matrix & A,const Vector2 & v,VectorCategories::DenseVectorTag)216 Vector1 &MVProductDomain<Givaro::Modular<int8_t> >::mulColDenseSpecialized 217 (const VectorDomain<Givaro::Modular<int8_t> > &VD, Vector1 &w, const Matrix &A, const Vector2 &v, 218 VectorCategories::DenseVectorTag) const 219 { 220 221 linbox_check (A.coldim () == v.size ()); 222 linbox_check (A.rowdim () == w.size ()); 223 224 typename Matrix::ConstColIterator i = A.colBegin (); 225 typename Vector2::const_iterator j; 226 typename Matrix::Column::const_iterator k; 227 std::vector<uint64_t>::iterator l; 228 229 uint64_t t; 230 231 if (_tmp.size () < w.size ()) 232 _tmp.resize (w.size ()); 233 234 std::fill (_tmp.begin (), _tmp.begin () + w.size (), 0); 235 236 for (j = v.begin (); j != v.end (); ++j, ++i) { 237 for (k = i->begin (), l = _tmp.begin (); k != i->end (); ++k, ++l) { 238 t = ((uint16_t) *k) * ((uint16_t) *j); 239 240 *l += t; 241 242 } 243 } 244 245 typename Vector1::iterator w_j; 246 247 for (w_j = w.begin (), l = _tmp.begin (); w_j != w.end (); ++w_j, ++l) 248 *w_j = *l % VD.field().characteristic(); 249 250 return w; 251 } 252 253 template <class Vector1, class Matrix, class Vector2> mulColDenseSpecialized(const VectorDomain<Givaro::Modular<int8_t>> & VD,Vector1 & w,const Matrix & A,const Vector2 & v,VectorCategories::SparseSequenceVectorTag)254 Vector1 &MVProductDomain<Givaro::Modular<int8_t> >::mulColDenseSpecialized 255 (const VectorDomain<Givaro::Modular<int8_t> > &VD, Vector1 &w, const Matrix &A, const Vector2 &v, 256 VectorCategories::SparseSequenceVectorTag) const 257 { 258 linbox_check (A.coldim () == v.size ()); 259 linbox_check (A.rowdim () == w.size ()); 260 261 typename Matrix::ConstColIterator i = A.colBegin (); 262 typename Vector2::const_iterator j; 263 typename Matrix::Column::const_iterator k; 264 std::vector<uint64_t>::iterator l; 265 266 uint64_t t; 267 268 if (_tmp.size () < w.size ()) 269 _tmp.resize (w.size ()); 270 271 std::fill (_tmp.begin (), _tmp.begin () + w.size (), 0); 272 273 for (j = v.begin (); j != v.end (); ++j, ++i) { 274 for (k = i->begin (), l = _tmp.begin (); k != i->end (); ++k, ++l) { 275 t = ((uint16_t) k->second) * ((uint16_t) *j); 276 277 _tmp[k->first] += t; 278 279 } 280 } 281 282 typename Vector1::iterator w_j; 283 284 for (w_j = w.begin (), l = _tmp.begin (); w_j != w.end (); ++w_j, ++l) 285 *w_j = *l % VD.field().characteristic(); 286 287 return w; 288 } 289 290 template <class Vector1, class Matrix, class Vector2> mulColDenseSpecialized(const VectorDomain<Givaro::Modular<int8_t>> & VD,Vector1 & w,const Matrix & A,const Vector2 & v,VectorCategories::SparseAssociativeVectorTag)291 Vector1 &MVProductDomain<Givaro::Modular<int8_t> >::mulColDenseSpecialized 292 (const VectorDomain<Givaro::Modular<int8_t> > &VD, Vector1 &w, const Matrix &A, const Vector2 &v, 293 VectorCategories::SparseAssociativeVectorTag) const 294 { 295 296 linbox_check (A.coldim () == v.size ()); 297 linbox_check (A.rowdim () == w.size ()); 298 299 typename Matrix::ConstColIterator i = A.colBegin (); 300 typename Vector2::const_iterator j; 301 typename Matrix::Column::const_iterator k; 302 std::vector<uint64_t>::iterator l; 303 304 uint64_t t; 305 306 if (_tmp.size () < w.size ()) 307 _tmp.resize (w.size ()); 308 309 std::fill (_tmp.begin (), _tmp.begin () + w.size (), 0); 310 311 for (j = v.begin (); j != v.end (); ++j, ++i) { 312 for (k = i->begin (), l = _tmp.begin (); k != i->end (); ++k, ++l) { 313 t = ((uint16_t) k->second) * ((uint16_t) *j); 314 315 _tmp[k->first] += t; 316 317 } 318 } 319 320 typename Vector1::iterator w_j; 321 322 for (w_j = w.begin (), l = _tmp.begin (); w_j != w.end (); ++w_j, ++l) 323 *w_j = *l % VD.field().characteristic(); 324 325 return w; 326 } 327 328 template <class Vector1, class Matrix, class Vector2> mulColDenseSpecialized(const VectorDomain<Givaro::Modular<int8_t>> & VD,Vector1 & w,const Matrix & A,const Vector2 & v,VectorCategories::SparseParallelVectorTag)329 Vector1 &MVProductDomain<Givaro::Modular<int8_t> >::mulColDenseSpecialized 330 (const VectorDomain<Givaro::Modular<int8_t> > &VD, Vector1 &w, const Matrix &A, const Vector2 &v, 331 VectorCategories::SparseParallelVectorTag) const 332 { 333 334 linbox_check (A.coldim () == v.size ()); 335 linbox_check (A.rowdim () == w.size ()); 336 337 typename Matrix::ConstColIterator i = A.colBegin (); 338 typename Vector2::const_iterator j; 339 typename Matrix::Column::first_type::const_iterator k_idx; 340 typename Matrix::Column::second_type::const_iterator k_elt; 341 std::vector<uint64_t>::iterator l; 342 343 uint64_t t; 344 345 if (_tmp.size () < w.size ()) 346 _tmp.resize (w.size ()); 347 348 std::fill (_tmp.begin (), _tmp.begin () + w.size (), 0); 349 350 for (j = v.begin (); j != v.end (); ++j, ++i) { 351 for (k_idx = i->first.begin (), k_elt = i->second.begin (), l = _tmp.begin (); 352 k_idx != i->first.end (); 353 ++k_idx, ++k_elt, ++l) 354 { 355 t = ((uint16_t) *k_elt) * ((uint16_t) *j); 356 357 _tmp[*k_idx] += t; 358 359 } 360 } 361 362 typename Vector1::iterator w_j; 363 364 for (w_j = w.begin (), l = _tmp.begin (); w_j != w.end (); ++w_j, ++l) 365 *w_j = *l % VD.field().characteristic(); 366 367 return w; 368 } 369 370 } 371 372 #ifdef __ICC 373 #pragma warning(enable:2259) 374 #endif 375 376 377 #endif //__LINBOX_modular_bit_H 378 379 // Local Variables: 380 // mode: C++ 381 // tab-width: 4 382 // indent-tabs-mode: nil 383 // c-basic-offset: 4 384 // End: 385 // vim:sts=4:sw=4:ts=4:et:sr:cino=>s,f0,{0,g0,(0,\:0,t0,+0,=s 386