1 #ifndef CoCoA_SmallFpLogImpl_H 2 #define CoCoA_SmallFpLogImpl_H 3 4 // Copyright (c) 2005,2009,2011-2013 John Abbott 5 6 // This file is part of the source of CoCoALib, the CoCoA Library. 7 8 // CoCoALib is free software: you can redistribute it and/or modify 9 // it under the terms of the GNU General Public License as published by 10 // the Free Software Foundation, either version 3 of the License, or 11 // (at your option) any later version. 12 13 // CoCoALib 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 16 // GNU General Public License for more details. 17 18 // You should have received a copy of the GNU General Public License 19 // along with CoCoALib. If not, see <http://www.gnu.org/licenses/>. 20 21 22 // Header file for the class SmallFpLogImpl 23 24 25 #include "CoCoA/assert.H" 26 #include "CoCoA/GlobalManager.H" 27 28 29 #include <vector> 30 // using std::vector 31 32 33 namespace CoCoA 34 { 35 36 class MachineInt; // fwd decl -- defined in MachineInt.H 37 class BigInt; // fwd decl -- defined in BigInt.H 38 class BigRat; // fwd decl -- defined in BigRat.H 39 class SmallPrime; // fwd decl -- defined in NumTheory-prime.H 40 41 class SmallFpLogImpl 42 { 43 public: 44 explicit SmallFpLogImpl(const MachineInt& n, GlobalSettings::ResidueSetting ResidueChoice = DefaultResidueSetting()); 45 explicit SmallFpLogImpl(SmallPrime p, GlobalSettings::ResidueSetting ResidueChoice = DefaultResidueSetting()); 46 static bool IsGoodCtorArg(const MachineInt& n); 47 static bool IsGoodCtorArg(SmallPrime p); 48 static long ourMaxModulus(); 49 private: 50 SmallFpLogImpl(const SmallFpLogImpl&); // NEVER DEFINED -- copy ctor disabled 51 SmallFpLogImpl& operator=(const SmallFpLogImpl&); // NEVER DEFINED -- assignment disabled 52 53 public: 54 typedef unsigned int value_t; // data type for internal repr of mod p values 55 static const int ourDatumSize = sizeof(value_t); 56 57 long myModulus() const; 58 value_t myReduce(const MachineInt& n) const; ///< n % myModulus 59 value_t myReduce(const BigInt& N) const; ///< N % myModulus 60 value_t myReduce(const BigRat& q) const; ///< q % myModulus (error if den(q)%myModulus == 0) 61 long myExport(value_t x) const; ///< exports x into a long (according to myResiduesAreSymm) 62 63 value_t myNegate(value_t x) const; 64 value_t myAdd(value_t x, value_t y) const; 65 value_t mySub(value_t x, value_t y) const; 66 value_t myMul(value_t x, value_t y) const; 67 value_t myDiv(value_t x, value_t y) const; 68 value_t myPower(value_t x, long n) const; 69 70 bool myIsZeroAddMul(value_t& lhs, value_t y, value_t z) const;///< lhs += y*z, result says whether lhs == 0. 71 value_t myNormalize(value_t n) const; 72 value_t myHalfNormalize(value_t n) const; myMaxIters()73 long myMaxIters() const { return myIterLimit; } 74 75 private: // data members 76 const value_t myModulusValue; 77 const bool myResiduesAreSymm; // Used only in myExport 78 const value_t myResidueUPBValue; 79 const value_t myIterLimit; 80 const value_t myRoot; 81 typedef unsigned short FpTableElem; // the log/exp table elements are of this type 82 std::vector<FpTableElem> myLog; 83 std::vector<FpTableElem> myExp; 84 85 private: // impl details 86 static value_t ourCheckCtorArg(const MachineInt& n); 87 static value_t ourCheckCtorArg(SmallPrime p); 88 static value_t ourCalcResidueUPB(value_t p); 89 static long ourCalcIterLimit(value_t p); 90 void myCtorBody(); 91 }; // end of class SmallFpLogImpl 92 93 94 std::ostream& operator<<(std::ostream& out, const SmallFpLogImpl& arith); 95 bool operator==(const SmallFpLogImpl& arith1, const SmallFpLogImpl& arith2); 96 bool operator!=(const SmallFpLogImpl& arith1, const SmallFpLogImpl& arith2); 97 98 99 //------------------------------------------------------------ 100 // SmallFpLogImpl inline functions 101 //------------------------------------------------------------ 102 myModulus()103 inline long SmallFpLogImpl::myModulus() const 104 { 105 return myModulusValue; // implicit cast is safe 106 } 107 108 myExport(value_t x)109 inline long SmallFpLogImpl::myExport(value_t x) const 110 { 111 if (!myResiduesAreSymm || x <= myModulusValue/2) return x; // implicit cast is safe 112 return -static_cast<long>(myModulusValue - x); // cast is safe 113 } 114 115 myNormalize(value_t n)116 inline SmallFpLogImpl::value_t SmallFpLogImpl::myNormalize(value_t n) const 117 { 118 return n%myModulusValue; 119 } 120 121 myNegate(value_t x)122 inline SmallFpLogImpl::value_t SmallFpLogImpl::myNegate(value_t x) const 123 { 124 CoCoA_ASSERT(x == myNormalize(x)); 125 if (x == 0) return x; 126 return myModulusValue - x; 127 } 128 129 myAdd(value_t x,value_t y)130 inline SmallFpLogImpl::value_t SmallFpLogImpl::myAdd(value_t x, value_t y) const 131 { 132 CoCoA_ASSERT(x == myNormalize(x)); 133 CoCoA_ASSERT(y == myNormalize(y)); 134 const value_t ans = x+y; 135 if (ans < myModulusValue) return ans; 136 return ans - myModulusValue; 137 } 138 139 mySub(value_t x,value_t y)140 inline SmallFpLogImpl::value_t SmallFpLogImpl::mySub(value_t x, value_t y) const 141 { 142 CoCoA_ASSERT(x == myNormalize(x)); 143 CoCoA_ASSERT(y == myNormalize(y)); 144 if (x >= y) return x-y; 145 return x + (myModulusValue-y); // avoid trying to create a negative value 146 } 147 148 myMul(value_t x,value_t y)149 inline SmallFpLogImpl::value_t SmallFpLogImpl::myMul(value_t x, value_t y) const 150 { 151 CoCoA_ASSERT(x == myNormalize(x)); 152 CoCoA_ASSERT(y == myNormalize(y)); 153 if (x == 0 || y == 0) return 0; 154 else return myExp[myLog[x] + myLog[y]]; 155 } 156 157 myDiv(value_t x,value_t y)158 inline SmallFpLogImpl::value_t SmallFpLogImpl::myDiv(value_t x, value_t y) const 159 { 160 CoCoA_ASSERT(x == myNormalize(x)); 161 CoCoA_ASSERT(y == myNormalize(y)); 162 CoCoA_ASSERT(y != 0); 163 if (x == 0) return 0; 164 return myExp[myModulusValue-1 + myLog[x] - myLog[y]]; 165 } 166 167 myIsZeroAddMul(value_t & lhs,value_t y,value_t z)168 inline bool SmallFpLogImpl::myIsZeroAddMul(value_t& lhs, value_t y, value_t z) const 169 { 170 CoCoA_ASSERT(y == myNormalize(y)); 171 CoCoA_ASSERT(z == myNormalize(z)); 172 CoCoA_ASSERT(lhs == myNormalize(lhs)); 173 lhs += myMul(y,z); 174 if (lhs >= myModulusValue) lhs -= myModulusValue; 175 return (lhs == 0); 176 } 177 178 myHalfNormalize(value_t n)179 inline SmallFpLogImpl::value_t SmallFpLogImpl::myHalfNormalize(value_t n) const 180 { 181 // if (n < myResidueUPBValue) return n; 182 // return n-myResidueUPBValue; 183 if (n >= myResidueUPBValue) return n-myResidueUPBValue; 184 return n; 185 } 186 187 188 inline bool operator==(const SmallFpLogImpl& arith1, const SmallFpLogImpl& arith2) 189 { 190 return (arith1.myModulus() == arith2.myModulus()); 191 } 192 193 inline bool operator!=(const SmallFpLogImpl& arith1, const SmallFpLogImpl& arith2) 194 { 195 return !(arith1 == arith2); 196 } 197 198 199 } // end of namespace CoCoA 200 201 202 // RCS header/log in the next few lines 203 // $Header: /Volumes/Home_1/cocoa/cvs-repository/CoCoALib-0.99/include/CoCoA/SmallFpLogImpl.H,v 1.18 2020/01/26 14:17:55 abbott Exp $ 204 // $Log: SmallFpLogImpl.H,v $ 205 // Revision 1.18 2020/01/26 14:17:55 abbott 206 // Summary: Changed include of MachineInt into fwd decl 207 // 208 // Revision 1.17 2018/06/25 12:28:20 abbott 209 // Summary: Ctors now accept SmallPrime args (and skip primality tests) 210 // 211 // Revision 1.16 2013/05/27 14:05:44 abbott 212 // Removed typedefs SmallFpElem_t and SmallFpLogElem_t from config.H; 213 // they are now nest typedefs SmallFpImpl::value_t and SmallFpLogImpl::value_t. 214 // 215 // Revision 1.15 2013/05/27 13:10:14 abbott 216 // Correct param type from long to MachineInt. 217 // 218 // Revision 1.14 2013/03/25 17:04:19 abbott 219 // Major clean-up of interface to SmallFpImpl/SmallFpLogImpl/SmallFpDoubleImpl 220 // (underlying impl remains much the same). Removed lots of cruft. 221 // Consequential changes to RingFp* classes; small change to SparsePolyRing. 222 // 223 // Revision 1.13 2012/09/07 15:21:13 abbott 224 // First stage of revision of SmallFpImpl interface (and SmallFpLog, SmallFpDouble). 225 // 226 // Revision 1.12 2012/01/30 11:01:11 abbott 227 // Added naive printing fn (just to help during debugging). 228 // 229 // Revision 1.11 2011/11/09 13:50:01 bigatti 230 // -- renamed MachineInteger --> MachineInt 231 // 232 // Revision 1.10 2011/08/24 10:21:09 bigatti 233 // -- renamed QQ --> BigRat 234 // 235 // Revision 1.9 2011/08/14 15:52:17 abbott 236 // Changed ZZ into BigInt (phase 1: just the library sources). 237 // 238 // Revision 1.8 2011/05/20 19:26:05 abbott 239 // Updated SmallFp*Impl: removed all output-related fns (must use myExport instead). 240 // 241 // Revision 1.7 2011/05/19 14:38:27 abbott 242 // Updated small prime finite field impls to allow user to specify 243 // separately for each whether to use symmetric or non-negative 244 // residues for export operations (myExport and printing). 245 // 246 // Revision 1.6 2011/03/22 20:06:13 abbott 247 // Added static mem fn IsGoodCtorArg (called by RingFp pseudo-ctors). 248 // Commented out ctors which take ZZ arg -- seems useless. 249 // 250 // Revision 1.5 2011/03/14 10:28:15 abbott 251 // Changed unsigned long into long (and unsigned short into short). 252 // 253 // Revision 1.4 2009/05/14 09:39:29 abbott 254 // Added possibility to specify "symmetric" or "non-negative" residues 255 // in quotients of ZZ. Affects printing of elements in quotients of ZZ 256 // (also changed printing of elements in general quotient rings). 257 // Consequent changes in several tests. 258 // 259 // Revision 1.3 2008/12/17 12:11:52 abbott 260 // Changed type from long to MachineInt in operations which use a machine integer 261 // in place of a RingElem. The change is "superficial" but affects many files. 262 // 263 // Revision 1.2 2007/10/30 17:14:11 abbott 264 // Changed licence from GPL-2 only to GPL-3 or later. 265 // New version for such an important change. 266 // 267 // Revision 1.1.1.1 2007/03/09 15:16:11 abbott 268 // Imported files 269 // 270 // Revision 1.7 2007/03/08 18:42:05 cocoa 271 // Cleaned up whitespace. 272 // 273 // Revision 1.6 2007/01/11 14:07:42 cocoa 274 // -- changed names to arguments called "rsh" 275 // 276 // Revision 1.5 2006/12/06 17:30:02 cocoa 277 // -- rearranged #include 278 // 279 // Revision 1.4 2006/11/24 17:22:05 cocoa 280 // -- removed OpenMathFwd.H 281 // 282 // Revision 1.3 2006/11/02 13:25:44 cocoa 283 // Simplification of header files: the OpenMath classes have been renamed. 284 // Many minor consequential changes. 285 // 286 // Revision 1.2 2006/10/06 14:04:15 cocoa 287 // Corrected position of #ifndef in header files. 288 // Separated CoCoA_ASSERT into assert.H from config.H; 289 // many minor consequential changes (have to #include assert.H). 290 // A little tidying of #include directives (esp. in Max's code). 291 // 292 // Revision 1.1.1.1 2006/05/30 11:39:37 cocoa 293 // Imported files 294 // 295 // Revision 1.5 2006/05/12 16:10:58 cocoa 296 // Added OpenMathFwd.H, and tidied OpenMath.H. 297 // Many consequential but trivial changes. 298 // 299 // Revision 1.4 2006/03/27 12:21:26 cocoa 300 // Minor silly changes to reduce number of complaints from some compiler or other. 301 // 302 // Revision 1.3 2006/03/21 09:43:14 cocoa 303 // Changed names of some member fns of ideals (dealing with setting and testing 304 // the flags for primeness and maximality). Hope icc will complain less now. 305 // 306 // Revision 1.2 2006/03/12 21:28:34 cocoa 307 // Major check in after many changes 308 // 309 // Revision 1.1.1.1 2005/10/17 10:46:54 cocoa 310 // Imported files 311 // 312 // Revision 1.5 2005/10/14 15:25:07 cocoa 313 // Major tidying and cleaning to small prime finite fields. 314 // Several consequential changes. Improved their documentation. 315 // 316 // Added Makefile and script to include/CoCoA/ directory to 317 // keep library.H up to date. 318 // 319 // Revision 1.4 2005/10/12 15:52:09 cocoa 320 // Completed test-RingFp1 and corrected/cleaned the SmallFp* 321 // and RingFp* files. 322 // 323 // Some minor tidying elsewhere. 324 // 325 // Revision 1.3 2005/10/11 16:37:30 cocoa 326 // Added new small prime finite field class (see RingFpDouble). 327 // 328 // Cleaned makefiles and configuration script. 329 // 330 // Tidied PPMonoid code (to eliminate compiler warnings). 331 // 332 // Fixed bug in RingFloat::myIsInteger. 333 // 334 // Revision 1.2 2005/09/22 18:04:17 cocoa 335 // It compiles; the tests run OK. The examples compile. 336 // No documentation -- the mindless eurocrats have rendered 337 // me mindless too. 338 // 339 // Revision 1.1.1.1 2005/05/03 15:47:31 cocoa 340 // Imported files 341 // 342 // Revision 1.4 2005/04/19 14:06:04 cocoa 343 // Added GPL and GFDL licence stuff. 344 // 345 // Revision 1.3 2005/02/28 15:58:56 cocoa 346 // Resynch after some minor changes. 347 // 348 // Revision 1.2 2005/02/11 16:45:24 cocoa 349 // Removed the useless and misleading functions myInit and myKill 350 // from the SmallFp*Impl classes; various consequential changes. 351 // 352 // Revision 1.1.1.1 2005/01/27 15:12:13 cocoa 353 // Imported files 354 // 355 // Revision 1.4 2004/11/12 15:49:29 cocoa 356 // Tidying prior to 0.90 release. 357 // (a) documentation improved (or marked as poor) 358 // (b) sundry minor improvements to the code 359 // 360 // Revision 1.3 2004/11/04 18:47:42 cocoa 361 // (1) Ring member functions which previously expected mpz_t args 362 // now expect ZZ args. Numerous minor consequential changes. 363 // (2) Renamed function which gives access to the mpz_t value inside 364 // a ZZ object: previously was raw(...), now is mpzref(...). 365 // Plenty of calls had to be altered. 366 // 367 // Revision 1.2 2004/07/16 15:45:12 cocoa 368 // First stage of new RingElem implementation completed. 369 // 370 // Revision 1.1 2004/07/14 16:40:42 cocoa 371 // Separated RingFpLog from its implementation which now resides in 372 // a new class: SmallFpLogImpl. This is analogous to the change made 373 // to RingFp yesterday. 374 // 375 // Some tidying and other sundry minor changes. 376 // 377 // 378 379 380 #endif 381