CoCoALib-0.9905 date: 23 May 2007


SmallFpImpl.H

Go to the documentation of this file.
00001 #ifndef CoCoA_SmallFpImpl_H
00002 #define CoCoA_SmallFpImpl_H
00003 
00004 //   Copyright (c)  2005  John Abbott
00005 
00006 //   This file is part of the source of CoCoALib, the CoCoA Library.
00007 
00008 //   CoCoALib is free software; you can redistribute it and/or modify
00009 //   it under the terms of the GNU General Public License (version 2)
00010 //   as published by the Free Software Foundation.  A copy of the full
00011 //   licence may be found in the file COPYING in this directory.
00012 
00013 //   CoCoALib is distributed in the hope that it will be useful,
00014 //   but WITHOUT ANY WARRANTY; without even the implied warranty of
00015 //   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00016 //   GNU General Public License for more details.
00017 
00018 //   You should have received a copy of the GNU General Public License
00019 //   along with CoCoA; if not, write to the Free Software
00020 //   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00021 
00022 
00023 // Header file for the class SmallFpImpl
00024 
00025 
00026 #include "CoCoA/assert.H"
00027 #include "CoCoA/config.H"
00028 #include "CoCoA/ZZ.H"
00029 
00030 #include <cstddef>
00031 //using std::size_t;
00032 #include <iosfwd>
00033 // using std::ostream;
00034 
00035 
00036 namespace CoCoA
00037 {
00038 
00039   class OpenMathOutput; // forward declaration -- defined in OpenMath.H
00040 
00041   /*-----------------------------------------------------------------*/
00042   /** \include SmallFpImpl.txt  */
00043   /*-----------------------------------------------------------------*/
00044   class SmallFpImpl
00045   {
00046   public:
00047     SmallFpImpl(unsigned long p);
00048     SmallFpImpl(const ZZ& P);
00049   private:
00050     SmallFpImpl(const SmallFpImpl&);            // NEVER DEFINED -- copy ctor disabled
00051     SmallFpImpl& operator=(const SmallFpImpl&); // NEVER DEFINED -- assignment disabled
00052   public:
00053     typedef SmallFpElem_t value_t;
00054     static const std::size_t DatumSize = sizeof(value_t);
00055 
00056     void myAssignZero(value_t& lhs) const;                        ///< lhs = 0
00057     void myAssign(value_t& lhs, value_t x) const;                 ///< lhs = x
00058     void myAssign(value_t& lhs, long n) const;                    ///< lhs = n
00059     void myAssign(value_t& lhs, const ZZ& N) const;               ///< lhs = N
00060     void myNegate(value_t& lhs, value_t x) const;                 ///< lhs = -x
00061     void myAdd(value_t& lhs, value_t x, value_t y) const;         ///< lhs = x+y
00062     void mySub(value_t& lhs, value_t x, value_t y) const;         ///< lhs = x-y
00063     void myMul(value_t& lhs, value_t x, value_t y) const;         ///< lhs = x*y
00064     void myDiv(value_t& lhs, value_t x, value_t y) const;         ///< lhs = x/y
00065     bool myIsDivisible(value_t& lhs, value_t x, value_t y) const; ///< lhs = x/y, if y is non-zero
00066     void myPower(value_t& lhs, value_t x, unsigned long n) const; ///< lhs = x^n
00067     void myOutput(std::ostream& out, value_t x) const;            ///< out << x
00068     void myOutput(OpenMathOutput& OMOut, value_t x) const;        ///< OMOut << x
00069     bool myIsPrintAtom(value_t x) const;
00070     bool myIsPrintedWithMinus(value_t x) const;
00071 
00072     bool myIsZero(value_t x) const;                        ///< x == 0
00073     bool myIsOne(value_t x) const;                         ///< x == 1
00074     bool myIsMinusOne(value_t x) const;                    ///< x == -1
00075     bool myIsInteger(ZZ& N, value_t x) const;  ///< copy value of x into n, result is always true
00076     bool myIsZeroAddMul(value_t& lhs, value_t y, value_t z) const;// lhs += y*z, result says whether lhs == 0.
00077     bool myIsEqual(value_t x, value_t y) const;  // x == y
00078 
00079   private: // data members
00080     const value_t myModulus;
00081     const value_t myRecip;          // Used only in myMul and myIsZeroAddMul.
00082     const unsigned short myMulShift1;  // (ditto)
00083     const unsigned short myMulShift2;  // (ditto)
00084     const value_t myDrop;     // PUBLIC???
00085     const value_t myIterLimit;// PUBLIC???
00086 
00087     value_t myReduceMod(value_t n) const; // Assumes n >= 0.
00088   private:
00089     static value_t CheckCtorArg(unsigned long p);
00090     static value_t CheckCtorArg(const ZZ& P);
00091     static value_t CalcRecip(value_t p);
00092     static value_t CalcDrop(value_t p);
00093     static value_t CalcIterLimit(value_t p);
00094   };  // end of class SmallFpImpl
00095 
00096 
00097   //------------------------------------------------------------
00098   // SmallFpImpl inline functions
00099   //------------------------------------------------------------
00100 
00101 //   inline std::size_t SmallFpImpl::myDatumSize()
00102 //   {
00103 //     return sizeof(value_t);
00104 //   }
00105 
00106 
00107   inline SmallFpImpl::value_t SmallFpImpl::myReduceMod(value_t n) const
00108   {
00109     return n%myModulus;
00110   }
00111 
00112 
00113   inline void SmallFpImpl::myAssignZero(value_t& lhs) const
00114   {
00115     lhs = 0;
00116   }
00117 
00118 
00119   inline void SmallFpImpl::myAssign(value_t& lhs, value_t x) const
00120   {
00121     CoCoA_ASSERT(x == x%myModulus);
00122     lhs = x;
00123   }
00124 
00125 
00126   inline void SmallFpImpl::myAssign(value_t& lhs, long n) const
00127   {
00128     if (n > 0) { lhs = n%long(myModulus); return; }
00129     lhs = myModulus - ((-n)%long(myModulus));
00130     if (lhs == myModulus) lhs = 0;
00131   }
00132 
00133 
00134   inline void SmallFpImpl::myAssign(value_t& lhs, const ZZ& N) const
00135   {
00136     lhs = mpz_fdiv_ui(mpzref(N), myModulus);
00137   }
00138 
00139 
00140   inline void SmallFpImpl::myNegate(value_t& lhs, value_t x) const
00141   {
00142     CoCoA_ASSERT(lhs == lhs%myModulus);
00143     if (x == 0) lhs = x;
00144     else lhs = myModulus-x;
00145   }
00146 
00147 
00148   inline void SmallFpImpl::myAdd(value_t& lhs, value_t x, value_t y) const
00149   {
00150     CoCoA_ASSERT(x == x%myModulus);
00151     CoCoA_ASSERT(y == y%myModulus);
00152     lhs = x+y;
00153     if (lhs >= myModulus) lhs -= myModulus;
00154   }
00155 
00156 
00157   inline void SmallFpImpl::mySub(value_t& lhs, value_t x, value_t y) const
00158   {
00159     CoCoA_ASSERT(x == x%myModulus);
00160     CoCoA_ASSERT(y == y%myModulus);
00161     if (x < y) lhs = x + (myModulus-y);  // avoid trying to create a negative value
00162     else lhs = x-y;
00163   }
00164 
00165 
00166   inline void SmallFpImpl::myMul(value_t& lhs, value_t x, value_t y) const
00167   {
00168     CoCoA_ASSERT(x == x%myModulus);
00169     CoCoA_ASSERT(y == y%myModulus);
00170     lhs = x*y;
00171     value_t tmp = myRecip*(lhs>>myMulShift1);  // these four lines are faster than doing %myModulus
00172     lhs -= myModulus*(tmp>>myMulShift2);       //
00173     if (lhs >= 2*myModulus) lhs -= 2*myModulus;//
00174     if (lhs >= myModulus) lhs -= myModulus;    //
00175   }
00176 
00177 
00178   inline bool SmallFpImpl::myIsDivisible(value_t& lhs, value_t x, value_t y) const
00179   {
00180     CoCoA_ASSERT(x == x%myModulus);
00181     CoCoA_ASSERT(y == y%myModulus);
00182     if (y == 0) return false;
00183     myDiv(lhs, x, y);
00184     return true;
00185   }
00186 
00187 
00188   inline bool SmallFpImpl::myIsPrintAtom(value_t x) const
00189   {
00190     CoCoA_ASSERT(x == x%myModulus);
00191     return true;
00192   }
00193 
00194 
00195   inline bool SmallFpImpl::myIsPrintedWithMinus(value_t x) const
00196   {
00197     CoCoA_ASSERT(x == x%myModulus);
00198     return false;
00199   }
00200 
00201 
00202   inline bool SmallFpImpl::myIsZero(value_t x) const
00203   {
00204     CoCoA_ASSERT(x == x%myModulus);
00205     return x == 0;
00206   }
00207 
00208 
00209   inline bool SmallFpImpl::myIsOne(value_t x) const
00210   {
00211     CoCoA_ASSERT(x == x%myModulus);
00212     return x == 1;
00213   }
00214 
00215 
00216   inline bool SmallFpImpl::myIsMinusOne(value_t x) const
00217   {
00218     CoCoA_ASSERT(x == x%myModulus);
00219     return x == myModulus-1;
00220   }
00221 
00222 
00223   inline bool SmallFpImpl::myIsInteger(ZZ& N, value_t x) const
00224   {
00225     N = x; // would cause trouble if x were greater than the biggest signed long
00226     return true;
00227   }
00228 
00229 
00230   inline bool SmallFpImpl::myIsZeroAddMul(value_t& lhs, value_t y, value_t z) const
00231   {
00232     CoCoA_ASSERT(y == y%myModulus);
00233     CoCoA_ASSERT(z == z%myModulus);
00234     lhs += y*z;
00235     value_t tmp = myRecip*(lhs>>myMulShift1);  // these four lines are faster than doing %myModulus
00236     lhs -= myModulus*(tmp>>myMulShift2);       //
00237     if (lhs >= 2*myModulus) lhs -= 2*myModulus;//
00238     if (lhs >= myModulus) lhs -= myModulus;    //
00239     return myIsZero(lhs);
00240   }
00241 
00242 
00243   inline bool SmallFpImpl::myIsEqual(value_t x, value_t y) const
00244   {
00245     CoCoA_ASSERT(x == x%myModulus);
00246     CoCoA_ASSERT(y == y%myModulus);
00247     return x==y;
00248   }
00249 
00250 
00251 } // end of namespace CoCoA
00252 
00253 
00254 // RCS header/log in the next few lines
00255 // $Header: /Volumes/Home/cocoa/cvs-repository/CoCoALib-0.99/include/CoCoA/SmallFpImpl.H,v 1.1.1.1 2007/03/09 15:16:11 abbott Exp $
00256 // $Log: SmallFpImpl.H,v $
00257 // Revision 1.1.1.1  2007/03/09 15:16:11  abbott
00258 // Imported files
00259 //
00260 // Revision 1.7  2007/03/08 18:42:05  cocoa
00261 // Cleaned up whitespace.
00262 //
00263 // Revision 1.6  2007/01/11 14:07:42  cocoa
00264 // -- changed names to arguments called "rsh"
00265 //
00266 // Revision 1.5  2006/12/06 17:30:02  cocoa
00267 // -- rearranged #include
00268 //
00269 // Revision 1.4  2006/11/24 17:22:05  cocoa
00270 // -- removed OpenMathFwd.H
00271 //
00272 // Revision 1.3  2006/11/02 13:25:44  cocoa
00273 // Simplification of header files: the OpenMath classes have been renamed.
00274 // Many minor consequential changes.
00275 //
00276 // Revision 1.2  2006/10/06 14:04:15  cocoa
00277 // Corrected position of #ifndef in header files.
00278 // Separated CoCoA_ASSERT into assert.H from config.H;
00279 // many minor consequential changes (have to #include assert.H).
00280 // A little tidying of #include directives (esp. in Max's code).
00281 //
00282 // Revision 1.1.1.1  2006/05/30 11:39:37  cocoa
00283 // Imported files
00284 //
00285 // Revision 1.4  2006/05/12 16:10:58  cocoa
00286 // Added OpenMathFwd.H, and tidied OpenMath.H.
00287 // Many consequential but trivial changes.
00288 //
00289 // Revision 1.3  2006/03/27 12:21:26  cocoa
00290 // Minor silly changes to reduce number of complaints from some compiler or other.
00291 //
00292 // Revision 1.2  2006/03/12 21:28:34  cocoa
00293 // Major check in after many changes
00294 //
00295 // Revision 1.1.1.1  2005/10/17 10:46:54  cocoa
00296 // Imported files
00297 //
00298 // Revision 1.5  2005/10/14 15:25:07  cocoa
00299 // Major tidying and cleaning to small prime finite fields.
00300 // Several consequential changes.  Improved their documentation.
00301 //
00302 // Added Makefile and script to include/CoCoA/ directory to
00303 // keep library.H up to date.
00304 //
00305 // Revision 1.4  2005/10/12 15:52:09  cocoa
00306 // Completed test-RingFp1 and corrected/cleaned the SmallFp*
00307 // and RingFp* files.
00308 //
00309 // Some minor tidying elsewhere.
00310 //
00311 // Revision 1.3  2005/10/11 16:37:30  cocoa
00312 // Added new small prime finite field class (see RingFpDouble).
00313 //
00314 // Cleaned makefiles and configuration script.
00315 //
00316 // Tidied PPMonoid code (to eliminate compiler warnings).
00317 //
00318 // Fixed bug in RingFloat::myIsInteger.
00319 //
00320 // Revision 1.2  2005/09/22 18:04:17  cocoa
00321 // It compiles; the tests run OK.  The examples compile.
00322 // No documentation -- the mindless eurocrats have rendered
00323 // me mindless too.
00324 //
00325 // Revision 1.1.1.1  2005/05/03 15:47:31  cocoa
00326 // Imported files
00327 //
00328 // Revision 1.4  2005/04/19 14:06:04  cocoa
00329 // Added GPL and GFDL licence stuff.
00330 //
00331 // Revision 1.3  2005/02/28 15:58:56  cocoa
00332 // Resynch after some minor changes.
00333 //
00334 // Revision 1.2  2005/02/11 16:45:24  cocoa
00335 // Removed the useless and misleading functions myInit and myKill
00336 // from the SmallFp*Impl classes; various consequential changes.
00337 //
00338 // Revision 1.1.1.1  2005/01/27 15:12:13  cocoa
00339 // Imported files
00340 //
00341 // Revision 1.7  2004/11/12 15:49:29  cocoa
00342 // Tidying prior to 0.90 release.
00343 // (a) documentation improved (or marked as poor)
00344 // (b) sundry minor improvements to the code
00345 //
00346 // Revision 1.6  2004/11/11 13:05:49  cocoa
00347 // -- added \include *.txt for doxygen
00348 //
00349 // Revision 1.5  2004/11/04 18:47:42  cocoa
00350 // (1) Ring member functions which previously expected mpz_t args
00351 //     now expect ZZ args.  Numerous minor consequential changes.
00352 // (2) Renamed function which gives access to the mpz_t value inside
00353 //     a ZZ object: previously was raw(...), now is mpzref(...).
00354 //     Plenty of calls had to be altered.
00355 //
00356 // Revision 1.4  2004/07/20 15:04:06  cocoa
00357 // The next step in the new "ring element" conversion process:
00358 // handling the case of creating a "const RefRingElem" object
00359 // (since C++ refuses to do this properly itself).
00360 //
00361 // Revision 1.3  2004/07/16 15:45:12  cocoa
00362 // First stage of new RingElem implementation completed.
00363 //
00364 // Revision 1.2  2004/07/14 16:40:42  cocoa
00365 // Separated RingFpLog from its implementation which now resides in
00366 // a new class: SmallFpLogImpl.  This is analogous to the change made
00367 // to RingFp yesterday.
00368 //
00369 // Some tidying and other sundry minor changes.
00370 //
00371 // Revision 1.1  2004/07/13 16:32:26  cocoa
00372 // First stage of major revamp of ring elements.
00373 // Implementation of RingFp has been split into "ring interface"
00374 // and "algorithms plus data structures".
00375 //
00376 //
00377 
00378 
00379 #endif

Generated on Wed May 23 13:43:36 2007 for CoCoALib by  doxygen 1.4.6