CoCoALib-0.9905 date: 23 May 2007


ZZ.H

Go to the documentation of this file.
00001 #ifndef CoCoA_ZZ_H
00002 #define CoCoA_ZZ_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 #include "CoCoA/assert.H"
00024 #include "CoCoA/MachineInteger.H"
00025 
00026 #include <cstddef>
00027 //using std::size_t
00028 #include <string>
00029 //using std::string;
00030 #include <iosfwd>
00031 //using std::ostream;
00032 //using std::istream;
00033 
00034 #include <gmp.h>
00035 
00036 namespace CoCoA
00037 {
00038 
00039   /*-----------------------------------------------------------------*/
00040   /** \include ZZ.txt  */
00041   /*-----------------------------------------------------------------*/
00042   class ZZ
00043   {
00044   private:
00045     friend mpz_t& mpzref(ZZ& N);
00046     friend const mpz_t& mpzref(const ZZ& N);
00047     mpz_t myRep;
00048     ZZ(MP_INT to_be_owned); // for efficient return values in operator+ etc.
00049 
00050   public:
00051     class rtn;
00052     friend class rtn;
00053     class rtn
00054     {
00055       mpz_t myRep;
00056     public:
00057       rtn(const ZZ& to_be_owned);
00058       rtn(const rtn& to_be_owned);
00059       rtn(MP_INT to_be_owned);
00060       ~rtn();
00061       friend class ZZ;
00062     };
00063     ZZ(const rtn& to_be_owned);
00064   public:
00065     ZZ();
00066     explicit ZZ(MachineInteger i);
00067     ZZ(const ZZ& from);
00068     explicit ZZ(const mpz_t to_be_copied);
00069 // ZZ& clone() const;
00070 
00071     ~ZZ();
00072 
00073     ZZ& operator=(const ZZ& rhs);
00074     ZZ& operator=(const ZZ::rtn& rhs);
00075 
00076     // -------- functions that modify at least one argument or `*this' ----------
00077 
00078     ZZ& operator+=(const ZZ& rhs);
00079     ZZ& operator-=(const ZZ& rhs);
00080     ZZ& operator*=(const ZZ& rhs);
00081     ZZ& operator/=(const ZZ& rhs);
00082     ZZ& operator%=(const ZZ& rhs);
00083         
00084     // Same but with RHS a long...
00085     ZZ& operator= (MachineInteger rhs);
00086     ZZ& operator+=(MachineInteger rhs);
00087     ZZ& operator-=(MachineInteger rhs);
00088     ZZ& operator*=(MachineInteger rhs);
00089     ZZ& operator/=(MachineInteger rhs);
00090     ZZ& operator%=(MachineInteger rhs);
00091 
00092 
00093     const ZZ& operator++( );
00094     const ZZ& operator--( );
00095     const ZZ operator++(int); // INEFFICIENT
00096     const ZZ operator--(int); // INEFFICIENT
00097 
00098   };
00099 
00100 
00101   // I/O FUNCTIONS
00102 
00103   std::ostream& operator<<(std::ostream& out, const ZZ& N);
00104   std::istream& operator>>(std::istream& in, ZZ& N);
00105 
00106 
00107   // STANDARD ARITHMETIC OPERATIONS
00108 
00109   void swap(ZZ& a, ZZ& b);
00110 
00111   const ZZ::rtn abs(const ZZ& N);
00112   const ZZ::rtn operator-(const ZZ& N);
00113 
00114   const ZZ::rtn operator+(const ZZ& N1, const ZZ& N2);
00115   const ZZ::rtn operator-(const ZZ& N1, const ZZ& N2);
00116   const ZZ::rtn operator*(const ZZ& N1, const ZZ& N2);
00117   const ZZ::rtn operator/(const ZZ& N1, const ZZ& N2);
00118   const ZZ::rtn operator%(const ZZ& N1, const ZZ& N2);
00119   const ZZ::rtn operator+(const ZZ& N1, MachineInteger n2);
00120   const ZZ::rtn operator-(const ZZ& N1, MachineInteger n2);
00121   const ZZ::rtn operator*(const ZZ& N1, MachineInteger n2);
00122   const ZZ::rtn operator/(const ZZ& N1, MachineInteger n2);
00123   const ZZ::rtn operator%(const ZZ& N1, MachineInteger n2);
00124   const ZZ::rtn operator+(MachineInteger n1, const ZZ& N2);
00125   const ZZ::rtn operator-(MachineInteger n1, const ZZ& N2);
00126   const ZZ::rtn operator*(MachineInteger n1, const ZZ& N2);
00127   const ZZ::rtn operator/(MachineInteger n1, const ZZ& N2);
00128   const ZZ::rtn operator%(MachineInteger n1, const ZZ& N2);
00129   const ZZ::rtn power(const ZZ& base, const ZZ& exponent);
00130   const ZZ::rtn power(const ZZ& base, MachineInteger exponent);
00131   const ZZ::rtn power(MachineInteger base, const ZZ& exponent);
00132   const ZZ::rtn power(MachineInteger base, MachineInteger exponent);
00133 
00134   void powermod(ZZ& dest, const ZZ& base, const ZZ& exp, const ZZ& modulus);
00135   void powermod(ZZ& dest, const ZZ& base, MachineInteger exp, const ZZ& modulus);
00136 
00137   const ZZ::rtn gcd(const ZZ& a, const ZZ& b);
00138   const ZZ::rtn lcm(const ZZ& a, const ZZ& b);
00139   void gcdext(ZZ& g, ZZ& c_a, ZZ& c_b, const ZZ& a, const ZZ& b);
00140   bool invmod(ZZ& dest, const ZZ& r, const ZZ& m);
00141 
00142 
00143   // Efficient arithmetic functions...
00144 
00145   void add(ZZ& lhs, const ZZ& N1, const ZZ& N2);
00146   void sub(ZZ& lhs, const ZZ& N1, const ZZ& N2);
00147   void mul(ZZ& lhs, const ZZ& N1, const ZZ& N2);
00148   void div(ZZ& lhs, const ZZ& N1, const ZZ& N2);
00149   void mod(ZZ& lhs, const ZZ& N1, const ZZ& N2);
00150   void quorem(ZZ& quo, ZZ& rem, const ZZ& num, const ZZ& den);
00151   void divexact(ZZ& lhs, const ZZ& N1, const ZZ& N2);
00152 
00153   void add(ZZ& lhs, const ZZ& N1, MachineInteger n2);
00154   void sub(ZZ& lhs, const ZZ& N1, MachineInteger n2);
00155   void mul(ZZ& lhs, const ZZ& N1, MachineInteger n2);
00156   void div(ZZ& lhs, const ZZ& N1, MachineInteger n2);
00157   void mod(ZZ& lhs, const ZZ& N1, MachineInteger n2);
00158   void quorem(ZZ& quo, ZZ& rem, const ZZ& num, MachineInteger den); // why is rem not of type MachineInteger???
00159   //???divexact???
00160 
00161   void add(ZZ& lhs, MachineInteger n1, const ZZ& N2);
00162   void sub(ZZ& lhs, MachineInteger n1, const ZZ& N2);
00163   void mul(ZZ& lhs, MachineInteger n1, const ZZ& N2);
00164   void div(ZZ& lhs, MachineInteger n1, const ZZ& N2);
00165   void mod(ZZ& lhs, MachineInteger n1, const ZZ& N2);
00166   void quorem(ZZ& quo, ZZ& rem, MachineInteger num, const ZZ& den);
00167   //???divexact???
00168 
00169   void neg(ZZ& lhs, const ZZ& rhs);
00170   void abs(ZZ& lhs, const ZZ& rhs);
00171   void gcd(ZZ& lhs, const ZZ& N1, const ZZ& N2);
00172   void lcm(ZZ& lhs, const ZZ& N1, const ZZ& N2);
00173 
00174 
00175   // SUNDRY PREDICATES.
00176 
00177   bool IsZero(const ZZ& N);
00178   bool IsOne(const ZZ& N);
00179   bool IsMinusOne(const ZZ& N);
00180   bool IsPositive(const ZZ& N);
00181   bool IsNegative(const ZZ& N);
00182   int sign(const ZZ& N);
00183   bool IsOdd(const ZZ& N);
00184   bool IsEven(const ZZ& N);
00185   bool IsPPrime(const ZZ& N, unsigned int niters = 25);
00186 //bool IsPerfectSquare(const ZZ& N);
00187 
00188   // Some of these predicates for MachineIntegers are in utils.H, the rest are here:
00189   bool IsPPrime(MachineInteger n, unsigned int NumIters = 25);
00190 // bool IsPerfectSquare(MachineInteger n);
00191 
00192 
00193   // COMPARISON FUNCTIONS
00194 
00195   int cmp(const ZZ& N1, const ZZ& N2);
00196   int cmp(const ZZ& N1, MachineInteger n2);
00197   int cmp(MachineInteger n1, const ZZ& N2);
00198 
00199   bool operator==(const ZZ& N1, const ZZ& N2);
00200   bool operator!=(const ZZ& N1, const ZZ& N2);
00201   bool operator> (const ZZ& N1, const ZZ& N2);
00202   bool operator>=(const ZZ& N1, const ZZ& N2);
00203   bool operator< (const ZZ& N1, const ZZ& N2);
00204   bool operator<=(const ZZ& N1, const ZZ& N2);
00205       
00206   bool operator==(const ZZ& N1, MachineInteger n2);
00207   bool operator!=(const ZZ& N1, MachineInteger n2);
00208   bool operator> (const ZZ& N1, MachineInteger n2);
00209   bool operator>=(const ZZ& N1, MachineInteger n2);
00210   bool operator< (const ZZ& N1, MachineInteger n2);
00211   bool operator<=(const ZZ& N1, MachineInteger n2);
00212           
00213   bool operator==(MachineInteger n1, const ZZ& N2);
00214   bool operator!=(MachineInteger n1, const ZZ& N2);
00215   bool operator> (MachineInteger n1, const ZZ& N2);
00216   bool operator>=(MachineInteger n1, const ZZ& N2);
00217   bool operator< (MachineInteger n1, const ZZ& N2);
00218   bool operator<=(MachineInteger n1, const ZZ& N2);
00219       
00220 
00221   // MISCELLANEOUS FUNCTIONS
00222 
00223   double mantissa(const ZZ& n);
00224   std::size_t exponent(const ZZ& n);
00225 
00226   std::size_t NumDigits(const ZZ& n, int base=2);
00227   double log(const ZZ& n);
00228 
00229   ZZ::rtn RangeFactorial(MachineInteger lo, MachineInteger hi); // computes lo*(lo+1)*(lo+2)*...*hi
00230   const ZZ::rtn factorial(const ZZ& N);
00231   const ZZ::rtn factorial(MachineInteger n);
00232   const ZZ::rtn binomial(const ZZ& N, const ZZ& R);
00233   const ZZ::rtn binomial(MachineInteger n, const ZZ& R);
00234   const ZZ::rtn binomial(const ZZ& N, MachineInteger r);
00235   const ZZ::rtn binomial(MachineInteger n, MachineInteger r);
00236   const ZZ::rtn fibonacci(const ZZ& N);
00237   const ZZ::rtn fibonacci(MachineInteger n);
00238 
00239   const ZZ::rtn random(const ZZ& lo, const ZZ& hi); ///< rnd number in range lo to hi (incl).
00240   const ZZ::rtn random(MachineInteger lo, MachineInteger hi);           ///< rnd number in range lo to hi (incl).
00241   const ZZ::rtn random(MachineInteger lo, const ZZ& hi);      ///< rnd number in range lo to hi (incl).
00242   const ZZ::rtn random(const ZZ& lo, MachineInteger hi);      ///< rnd number in range lo to hi (incl).
00243 
00244 
00245 /*
00246 ZZ::rtn root(const ZZ&, long n = 2);
00247 void root(ZZ&, const ZZ&, long n = 2);
00248 ZZ::rtn sqrt(const ZZ&);
00249 void sqrt(ZZ&, const ZZ&);
00250 void sqrt(ZZ&, ZZ&, const ZZ&); // square root and remainder
00251 bool IsSquare(const ZZ&);
00252 bool IsPower(const ZZ&);
00253 ZZ::rtn nextpprime(const ZZ&);
00254 void nextpprime(ZZ&, const ZZ&);
00255 int cmpabs(const ZZ&, const ZZ&);
00256 int cmpabs(const ZZ&, long);
00257 int cmpabs(long, const ZZ&);
00258 
00259 
00260   friend void           SqrtRem(ZZ& sqrt, ZZ& rem, const ZZ& b);
00261 ZZ         Div2Exp(const ZZ& b, unsigned long exponent_of_2);
00262 ZZ         Mod2Exp(const ZZ& b, unsigned long exponent_of_2);
00263 ZZ         Mul2Exp(const ZZ& b, unsigned long exponent_of_2);
00264 ZZ         sqrt   (const ZZ& b);
00265 */
00266 
00267 
00268   /////////////////////////////////////////////////////////////////////////////
00269   // Inline functions
00270 
00271   inline mpz_t& mpzref(ZZ& N)
00272   {
00273     return N.myRep;
00274   }
00275 
00276   inline const mpz_t& mpzref(const ZZ& N)
00277   {
00278     return N.myRep;
00279   }
00280 
00281 
00282 // I don't like this function name...
00283 //   inline void neg_(ZZ& x)
00284 //   {
00285 //     x.neg();
00286 //   }
00287 
00288 
00289   inline ZZ::~ZZ()
00290   {
00291     mpz_clear(myRep);
00292   }
00293 
00294 
00295   inline ZZ::rtn::rtn(const ZZ& to_be_owned)
00296   {
00297     myRep[0] = to_be_owned.myRep[0];
00298     const_cast<ZZ&>(to_be_owned).myRep->_mp_d = 0;
00299   }
00300 
00301 
00302   inline ZZ::rtn::rtn(const rtn& to_be_owned)
00303   {
00304     myRep[0] = to_be_owned.myRep[0];
00305     const_cast<rtn&>(to_be_owned).myRep->_mp_d = 0;
00306   }
00307 
00308 
00309   inline ZZ::rtn::rtn(MP_INT to_be_owned)
00310   {
00311     myRep[0] = to_be_owned;
00312   }
00313 
00314 
00315   inline ZZ::rtn::~rtn()
00316   {
00317     CoCoA_ASSERT(myRep->_mp_d == 0);
00318   }
00319 
00320 
00321   inline ZZ::ZZ(const rtn& to_be_owned)
00322   {
00323     myRep[0] = to_be_owned.myRep[0];
00324     const_cast<rtn&>(to_be_owned).myRep->_mp_d = 0;
00325   }
00326 
00327 
00328   inline ZZ& ZZ::operator=(const ZZ::rtn& rhs)
00329   {
00330     mpz_swap(myRep, const_cast<rtn&>(rhs).myRep);
00331     mpz_clear(const_cast<rtn&>(rhs).myRep);
00332     const_cast<rtn&>(rhs).myRep->_mp_d = 0;
00333     return *this;
00334   }
00335 
00336 
00337   inline bool IsPPrime(MachineInteger n, unsigned int niters) { return IsPPrime(ZZ(n), niters); }
00338 // inline bool IsPerfectSquare(MachineInteger n);
00339 
00340 } // end of namespace CoCoA
00341 
00342 
00343 
00344 // The next few lines contain RCS header/log information.
00345 // $Header: /Volumes/Home/cocoa/cvs-repository/CoCoALib-0.99/include/CoCoA/ZZ.H,v 1.5 2007/05/22 22:51:39 abbott Exp $
00346 // $Log: ZZ.H,v $
00347 // Revision 1.5  2007/05/22 22:51:39  abbott
00348 // Changed name of fn ndigits to NumDigits.
00349 // Changed return type of exponent and NumDigits.
00350 // Changed some exceptions from nonstandard to the appropriate standard one.
00351 //
00352 // Revision 1.4  2007/05/21 12:57:28  abbott
00353 // New class for passing machine integers as args; includes some simple
00354 // operations on machine integers (cmp, gcd, IsNegative,...).  Operations
00355 // between ZZ and machine integers modified to use the new class.  Inexact
00356 // integer division (of a ZZ) by a negative value now triggers an error;
00357 // new error for reporting inexact integer division by a negative value.
00358 //
00359 // Revision 1.3  2007/03/23 18:38:43  abbott
00360 // Separated the "convert" functions (and CheckedCast) into their own files.
00361 // Many consequential changes.  Also corrected conversion to doubles.
00362 //
00363 // Revision 1.2  2007/03/16 17:43:05  abbott
00364 // Added new convert function (from ZZ to double).
00365 //
00366 // Revision 1.1.1.1  2007/03/09 15:16:11  abbott
00367 // Imported files
00368 //
00369 // Revision 1.10  2007/03/08 18:42:05  cocoa
00370 // Cleaned up whitespace.
00371 //
00372 // Revision 1.9  2007/01/13 14:14:34  cocoa
00373 // Overhaul of RingHom code: it nows uses SmartPtrIRC, and printing is more logical.
00374 // Have not yet updated the documentation.
00375 //
00376 // Revision 1.8  2006/12/06 17:17:44  cocoa
00377 // -- removed #include "config.H"
00378 //
00379 // Revision 1.7  2006/11/29 11:59:35  cocoa
00380 // -- fixed: convert(double& z, const ZZ& num, const ZZ& den) now returns
00381 //    bool (was void) and does not throw errors
00382 //
00383 // Revision 1.6  2006/11/27 13:38:18  cocoa
00384 // -- added #include <cstddef> //using std::size_t
00385 //
00386 // Revision 1.5  2006/11/27 13:06:23  cocoa
00387 // Anna and Michael made me check without writing a proper message.
00388 //
00389 // Revision 1.4  2006/10/06 14:04:15  cocoa
00390 // Corrected position of #ifndef in header files.
00391 // Separated CoCoA_ASSERT into assert.H from config.H;
00392 // many minor consequential changes (have to #include assert.H).
00393 // A little tidying of #include directives (esp. in Max's code).
00394 //
00395 // Revision 1.3  2006/09/29 11:46:54  cocoa
00396 // Corrected bug in convert(ZZ, ZZ, double) -- now correct and simpler.
00397 // Previously went into infinite loop on negative doubles.
00398 //
00399 // Revision 1.2  2006/06/21 17:08:04  cocoa
00400 // Removed a pointless const.
00401 //
00402 // Revision 1.1.1.1  2006/05/30 11:39:37  cocoa
00403 // Imported files
00404 //
00405 // Revision 1.4  2006/05/12 16:10:58  cocoa
00406 // Added OpenMathFwd.H, and tidied OpenMath.H.
00407 // Many consequential but trivial changes.
00408 //
00409 // Revision 1.3  2006/03/27 12:21:26  cocoa
00410 // Minor silly changes to reduce number of complaints from some compiler or other.
00411 //
00412 // Revision 1.2  2006/03/14 15:01:49  cocoa
00413 // Improved the implementation of ring member fns for computing powers.
00414 // Should keep Intel C++ compiler quieter too.
00415 //
00416 // Revision 1.1.1.1  2005/10/17 10:46:54  cocoa
00417 // Imported files
00418 //
00419 // Revision 1.2  2005/08/08 16:36:32  cocoa
00420 // Just checking in before going on holiday.
00421 // Don't really recall what changes have been made.
00422 // Added IsIndet function for RingElem, PPMonoidElem,
00423 // and a member function of OrdvArith.
00424 // Improved the way failed assertions are handled.
00425 //
00426 // Revision 1.1.1.1  2005/05/03 15:47:31  cocoa
00427 // Imported files
00428 //
00429 // Revision 1.2  2005/04/19 14:06:04  cocoa
00430 // Added GPL and GFDL licence stuff.
00431 //
00432 // Revision 1.1.1.1  2005/01/27 15:12:13  cocoa
00433 // Imported files
00434 //
00435 // Revision 1.7  2004/11/12 15:49:29  cocoa
00436 // Tidying prior to 0.90 release.
00437 // (a) documentation improved (or marked as poor)
00438 // (b) sundry minor improvements to the code
00439 //
00440 // Revision 1.6  2004/11/11 13:20:47  cocoa
00441 // -- added \include *.txt for doxygen
00442 //
00443 // Revision 1.5  2004/11/04 18:47:42  cocoa
00444 // (1) Ring member functions which previously expected mpz_t args
00445 //     now expect ZZ args.  Numerous minor consequential changes.
00446 // (2) Renamed function which gives access to the mpz_t value inside
00447 //     a ZZ object: previously was raw(...), now is mpzref(...).
00448 //     Plenty of calls had to be altered.
00449 //
00450 // Revision 1.4  2004/05/27 16:14:02  cocoa
00451 // Minor revision for new coding conventions.
00452 //
00453 // Revision 1.3  2004/02/03 16:16:20  cocoa
00454 // Removed pointless IamGCDDomain functions from several concrete rings.
00455 // Added IamOrderedDomain functions where appropriate.
00456 // Tidied ctors for the small finite fields.
00457 //
00458 // Revision 1.2  2003/10/17 10:51:06  cocoa
00459 // Major cleaning, and new naming convention.
00460 //
00461 // Revision 1.1.1.1  2003/09/24 12:55:43  cocoa
00462 // Imported files
00463 //
00464 // Revision 1.2  2003/06/23 16:12:44  abbott
00465 // Minor cleaning prior to public release.
00466 //
00467 // Revision 1.1  2003/05/14 17:12:35  abbott
00468 // Initial revision
00469 //
00470 
00471 #endif

Generated on Wed May 23 13:45:25 2007 for CoCoALib by  doxygen 1.4.6