dune-common  2.2.0
bigunsignedint.hh
Go to the documentation of this file.
00001 // $Id: bigunsignedint.hh 6280 2010-11-29 23:40:59Z dedner $
00002 
00003 #ifndef DUNE_BIGUNSIGNEDINT_HH
00004 #define DUNE_BIGUNSIGNEDINT_HH
00005 
00006 #include<iostream>
00007 #include<limits>
00008 #include<cstdlib>
00009 #include<dune/common/exceptions.hh>
00010 
00017 namespace Dune
00018 {
00024 #if HAVE_MPI
00025   template<class K>
00026   struct MPITraits;
00027 #endif
00028 
00038   template<int k>
00039   class bigunsignedint {
00040   public:
00041 
00042         // unsigned short is 16 bits wide, n is the number of digits needed
00043     enum { bits=std::numeric_limits<unsigned short>::digits, n=k/bits+(k%bits!=0), 
00044            hexdigits=4, bitmask=0xFFFF, compbitmask=0xFFFF0000, 
00045            overflowmask=0x1 };
00046 
00048         bigunsignedint ();
00049 
00051        bigunsignedint (int x);
00052 
00054         bigunsignedint (std::size_t x);
00055 
00057         void print (std::ostream& s) const ;
00058 
00060         bigunsignedint<k> operator+ (const bigunsignedint<k>& x) const;
00061 
00063         bigunsignedint<k> operator- (const bigunsignedint<k>& x) const;
00064 
00066         bigunsignedint<k> operator* (const bigunsignedint<k>& x) const;
00067 
00069         bigunsignedint<k>& operator++ ();
00070 
00074         bigunsignedint<k> operator/ (const bigunsignedint<k>& x) const;
00075 
00079         bigunsignedint<k> operator% (const bigunsignedint<k>& x) const;
00080 
00081 
00083         bigunsignedint<k> operator& (const bigunsignedint<k>& x) const;
00084 
00086         bigunsignedint<k> operator^ (const bigunsignedint<k>& x) const;
00087 
00089         bigunsignedint<k> operator| (const bigunsignedint<k>& x) const;
00090 
00092         bigunsignedint<k> operator~ () const;
00093 
00094 
00096         bigunsignedint<k> operator<< (int i) const;
00097 
00099         bigunsignedint<k> operator>> (int i) const;
00100 
00101 
00103         bool operator< (const bigunsignedint<k>& x) const;
00104 
00106         bool operator<= (const bigunsignedint<k>& x) const;
00107 
00109         bool operator> (const bigunsignedint<k>& x) const;
00110 
00112         bool operator>= (const bigunsignedint<k>& x) const;
00113 
00115         bool operator== (const bigunsignedint<k>& x) const;
00116 
00118         bool operator!= (const bigunsignedint<k>& x) const;
00119 
00120 
00122 //      operator unsigned int () const;
00123     unsigned int touint() const;
00129     double todouble() const;
00130 
00131         friend class bigunsignedint<k/2>;
00132     friend struct std::numeric_limits< bigunsignedint<k> >;
00133     
00134   private:
00135         unsigned short digit[n];
00136 #if HAVE_MPI
00137     friend class MPITraits<bigunsignedint<k> >;
00138 #endif
00139     inline void assign(std::size_t x);
00140     
00141     
00142   } ;
00143 
00144   // Constructors
00145   template<int k>
00146   bigunsignedint<k>::bigunsignedint ()
00147   { 
00148     assign(0u);
00149   }
00150 
00151   template<int k>
00152   bigunsignedint<k>::bigunsignedint (int y)
00153   {
00154     std::size_t x = std::abs(y);
00155     assign(x);
00156   }
00157 
00158   template<int k>
00159   bigunsignedint<k>::bigunsignedint (std::size_t x)
00160   {
00161     assign(x);
00162   }
00163   template<int k>
00164   void bigunsignedint<k>::assign(std::size_t x)
00165   {
00166     int no=std::min(static_cast<int>(n),
00167                     static_cast<int>(std::numeric_limits<std::size_t>::digits/bits));
00168     
00169     for(int i=0; i<no; ++i){
00170         digit[i] = (x&bitmask);
00171         x=x>>bits;
00172     }
00173     for (unsigned int i=no; i<n; i++) digit[i]=0;
00174   }
00175 
00176   // export
00177   template<int k>
00178   inline unsigned int bigunsignedint<k>::touint () const
00179   {
00180         return (digit[1]<<bits)+digit[0];
00181   }
00182 
00183   template<int k>
00184   inline double bigunsignedint<k>::todouble() const
00185   {
00186     int firstInZeroRange=n;
00187     for(int i=n-1; i>=0; --i)
00188       if(digit[i]!=0)
00189         break;
00190       else
00191         --firstInZeroRange;
00192     int representableDigits=std::numeric_limits<double>::digits/bits;
00193     int lastInRepresentableRange=0;
00194     if(representableDigits<firstInZeroRange)
00195       lastInRepresentableRange=firstInZeroRange-representableDigits;
00196     double val=0;
00197     for(int i=firstInZeroRange-1; i>=lastInRepresentableRange; --i)
00198       val =val*(1<<bits)+digit[i];
00199     return val*(1<<(bits*lastInRepresentableRange));
00200   }
00201   // print
00202   template<int k>
00203   inline void bigunsignedint<k>::print (std::ostream& s) const
00204   {    
00205         bool leading=false;
00206 
00207         // print from left to right
00208         for (int i=n-1; i>=0; i--)
00209           for (int d=hexdigits-1; d>=0; d--)
00210                 {
00211                   // extract one hex digit
00212                   int current = (digit[i]>>(d*4))&0xF;
00213                   if (current!=0)
00214                         {
00215                           //                      s.setf(std::ios::noshowbase);
00216                           s << std::hex << current;
00217                           leading = false;
00218                         }
00219                   else if (!leading) s << std::hex << current;
00220                 }
00221         if (leading) s << "0";
00222         s << std::dec;
00223   }
00224 
00225   template <int k>
00226   inline std::ostream& operator<< (std::ostream& s, const bigunsignedint<k>& x)
00227   {
00228         x.print(s);
00229         return s;
00230   }
00231 
00232 
00233   // Operators
00234   template <int k>
00235   inline bigunsignedint<k> bigunsignedint<k>::operator+ (const bigunsignedint<k>& x) const
00236   {
00237         bigunsignedint<k> result;
00238         int overflow=0;
00239 
00240         for (unsigned int i=0; i<n; i++)
00241           {
00242                 int sum = ((int)digit[i]) + ((int)x.digit[i]) + overflow;
00243                 result.digit[i] = sum&bitmask;
00244                 overflow = (sum>>bits)&overflowmask;
00245           }
00246         return result;
00247   }
00248 
00249   template <int k>
00250   inline bigunsignedint<k> bigunsignedint<k>::operator- (const bigunsignedint<k>& x) const
00251   {
00252         bigunsignedint<k> result;
00253         int overflow=0;
00254 
00255         for (unsigned int i=0; i<n; i++)
00256           {
00257                 int diff = ((int)digit[i]) - (((int)x.digit[i]) + overflow);
00258                 if (diff>=0)
00259                   result.digit[i] = (unsigned short) diff;
00260                 else
00261                   {
00262                         result.digit[i] = (unsigned short) (diff+bitmask);
00263                         overflow = 1;
00264                   }
00265           }
00266         return result;
00267   }
00268 
00269   template <int k>
00270   inline bigunsignedint<k> bigunsignedint<k>::operator* (const bigunsignedint<k>& x) const
00271   {
00272         bigunsignedint<2*k> finalproduct(0);
00273 
00274         for (unsigned int m=0; m<n; m++) // digit in right factor
00275           {
00276                 bigunsignedint<2*k> singleproduct(0);
00277                 unsigned int overflow(0);
00278                 for (unsigned int i=0; i<n; i++) 
00279                   {
00280                         unsigned int digitproduct = ((unsigned int)digit[i])*((unsigned int)x.digit[m])+overflow;
00281                         singleproduct.digit[i+m] = (unsigned short) (digitproduct&bitmask);
00282                         overflow = (digitproduct>>bits)&bitmask;
00283                   }
00284                 finalproduct = finalproduct+singleproduct;
00285           }
00286 
00287         bigunsignedint<k> result;
00288         for (unsigned int i=0; i<n; i++) result.digit[i] = finalproduct.digit[i];
00289         return result;
00290   }
00291 
00292   template <int k>
00293   inline  bigunsignedint<k>& bigunsignedint<k>::operator++ ()
00294   {
00295         int overflow=1;
00296 
00297         for (unsigned int i=0; i<n; i++)
00298           {
00299                 int sum = ((int)digit[i]) + overflow;
00300                 digit[i] = sum&bitmask;
00301                 overflow = (sum>>bits)&overflowmask;
00302           }
00303         return *this;
00304   }
00305 
00306   template <int k>
00307   inline bigunsignedint<k> bigunsignedint<k>::operator/ (const bigunsignedint<k>& x) const
00308   {
00309     if(x==0)
00310       DUNE_THROW(Dune::MathError, "division by zero!");
00311 
00312         // better slow than nothing
00313         bigunsignedint<k> temp(*this);
00314         bigunsignedint<k> result(0);
00315 
00316         while (temp>=x)
00317           {
00318                 ++result;
00319                 temp = temp-x;
00320           }
00321 
00322         return result;
00323   }
00324 
00325   template <int k>
00326   inline bigunsignedint<k> bigunsignedint<k>::operator% (const bigunsignedint<k>& x) const
00327   {
00328         // better slow than nothing
00329         bigunsignedint<k> temp(*this);
00330         bigunsignedint<k> result(0);
00331 
00332         while (temp>=x)
00333           {
00334                 ++result;
00335                 temp = temp-x;
00336           }
00337 
00338         return temp;
00339   }
00340 
00341 
00342   template <int k>
00343   inline bigunsignedint<k> bigunsignedint<k>::operator& (const bigunsignedint<k>& x) const
00344   {
00345         bigunsignedint<k> result;
00346         for (unsigned int i=0; i<n; i++)
00347           result.digit[i] = digit[i]&x.digit[i];
00348         return result;
00349   }
00350 
00351   template <int k>
00352   inline bigunsignedint<k> bigunsignedint<k>::operator^ (const bigunsignedint<k>& x) const
00353   {
00354         bigunsignedint<k> result;
00355         for (unsigned int i=0; i<n; i++)
00356           result.digit[i] = digit[i]^x.digit[i];
00357         return result;
00358   }
00359 
00360   template <int k>
00361   inline bigunsignedint<k> bigunsignedint<k>::operator| (const bigunsignedint<k>& x) const
00362   {
00363         bigunsignedint<k> result;
00364         for (unsigned int i=0; i<n; i++)
00365           result.digit[i] = digit[i]|x.digit[i];
00366         return result;
00367   }
00368 
00369   template <int k>
00370   inline bigunsignedint<k> bigunsignedint<k>::operator~ () const
00371   {
00372         bigunsignedint<k> result;
00373         for (unsigned int i=0; i<n; i++)
00374           result.digit[i] = ~digit[i];
00375         return result;
00376   }
00377 
00378   template <int k>
00379   inline bigunsignedint<k> bigunsignedint<k>::operator<< (int shift) const
00380   {
00381         bigunsignedint<k> result(0);
00382 
00383         // multiples of bits
00384         int j=shift/bits;
00385         for (int i=n-1-j; i>=0; i--)
00386           result.digit[i+j] = digit[i];
00387 
00388         // remainder
00389         j=shift%bits;
00390         for (int i=n-1; i>=0; i--)
00391           {
00392                 unsigned int temp = result.digit[i];
00393                 temp = temp<<j;
00394                 result.digit[i] = (unsigned short) (temp&bitmask);
00395                 temp = temp>>bits;
00396                 if (i+1<(int)n)
00397                   result.digit[i+1] = result.digit[i+1]|temp;
00398           }     
00399 
00400         return result;
00401   }
00402 
00403   template <int k>
00404   inline bigunsignedint<k> bigunsignedint<k>::operator>> (int shift) const
00405   {
00406         bigunsignedint<k> result(0);
00407 
00408         // multiples of bits
00409         int j=shift/bits;
00410         for (unsigned int i=0; i<n-j; i++)
00411           result.digit[i] = digit[i+j];
00412 
00413         // remainder
00414         j=shift%bits;
00415         for (unsigned int i=0; i<n; i++)
00416           {
00417                 unsigned int temp = result.digit[i];
00418                 temp = temp<<(bits-j);
00419                 result.digit[i] = (unsigned short) ((temp&compbitmask)>>bits);
00420                 if (i>0)
00421                   result.digit[i-1] = result.digit[i-1] | (temp&bitmask);
00422           }
00423 
00424         return result;
00425   }
00426 
00427   template <int k>
00428   inline bool bigunsignedint<k>::operator!= (const bigunsignedint<k>& x) const
00429   {
00430         for (unsigned int i=0; i<n; i++)
00431           if (digit[i]!=x.digit[i]) return true;
00432         return false;
00433   }
00434 
00435   template <int k>
00436   inline bool bigunsignedint<k>::operator== (const bigunsignedint<k>& x) const
00437   {
00438         return !((*this)!=x);
00439   }
00440 
00441   template <int k>
00442   inline bool bigunsignedint<k>::operator< (const bigunsignedint<k>& x) const
00443   {
00444         for (int i=n-1; i>=0; i--) 
00445           if (digit[i]<x.digit[i]) return true;
00446           else if (digit[i]>x.digit[i]) return false;
00447         return false;
00448   }
00449 
00450   template <int k>
00451   inline bool bigunsignedint<k>::operator<= (const bigunsignedint<k>& x) const
00452   {
00453         for (int i=n-1; i>=0; i--) 
00454           if (digit[i]<x.digit[i]) return true;
00455           else if (digit[i]>x.digit[i]) return false;
00456         return true;
00457   }
00458 
00459   template <int k>
00460   inline bool bigunsignedint<k>::operator> (const bigunsignedint<k>& x) const
00461   {
00462         return !((*this)<=x);   
00463   }
00464 
00465   template <int k>
00466   inline bool bigunsignedint<k>::operator>= (const bigunsignedint<k>& x) const
00467   {
00468         return !((*this)<x);    
00469   }
00470 
00471 
00472   template <int k>
00473   inline bigunsignedint<k> operator+ (const bigunsignedint<k>& x, std::size_t y)
00474   {
00475         bigunsignedint<k> temp(y);
00476         return x+temp;
00477   }
00478 
00479   template <int k>
00480   inline bigunsignedint<k> operator- (const bigunsignedint<k>& x, std::size_t y)
00481   {
00482         bigunsignedint<k> temp(y);
00483         return x-temp;
00484   }
00485 
00486   template <int k>
00487   inline bigunsignedint<k> operator* (const bigunsignedint<k>& x, std::size_t y)
00488   {
00489         bigunsignedint<k> temp(y);
00490         return x*temp;
00491   }
00492 
00493   template <int k>
00494   inline bigunsignedint<k> operator/ (const bigunsignedint<k>& x, std::size_t y)
00495   {
00496         bigunsignedint<k> temp(y);
00497         return x/temp;
00498   }
00499 
00500   template <int k>
00501   inline bigunsignedint<k> operator% (const bigunsignedint<k>& x, std::size_t y)
00502   {
00503         bigunsignedint<k> temp(y);
00504         return x%temp;
00505   }
00506 
00507   template <int k>
00508   inline bigunsignedint<k> operator+ (std::size_t x, const bigunsignedint<k>& y)
00509   {
00510         bigunsignedint<k> temp(x);
00511         return temp+y;
00512   }
00513 
00514   template <int k>
00515   inline bigunsignedint<k> operator- (std::size_t x, const bigunsignedint<k>& y)
00516   {
00517         bigunsignedint<k> temp(x);
00518         return temp-y;
00519   }
00520 
00521   template <int k>
00522   inline bigunsignedint<k> operator* (std::size_t x, const bigunsignedint<k>& y)
00523   {
00524         bigunsignedint<k> temp(x);
00525         return temp*y;
00526   }
00527 
00528   template <int k>
00529   inline bigunsignedint<k> operator/ (std::size_t x, const bigunsignedint<k>& y)
00530   {
00531         bigunsignedint<k> temp(x);
00532         return temp/y;
00533   }
00534 
00535   template <int k>
00536   inline bigunsignedint<k> operator% (std::size_t x, const bigunsignedint<k>& y)
00537   {
00538         bigunsignedint<k> temp(x);
00539         return temp%y;
00540   }
00541 
00542 
00544 }
00545 
00546 namespace std
00547 {
00548   template<int k>
00549   struct numeric_limits<Dune::bigunsignedint<k> >
00550   {
00551   public:
00552     static const bool is_specialized = true;
00553     
00554     static Dune::bigunsignedint<k> min()
00555     {
00556       return static_cast<Dune::bigunsignedint<k> >(0);
00557     }
00558 
00559     static Dune::bigunsignedint<k> max()
00560     {
00561       Dune::bigunsignedint<k> max_;
00562       for(std::size_t i=0; i < Dune::bigunsignedint<k>::n; ++i)
00563         max_.digit[i]=std::numeric_limits<unsigned short>::max();
00564       return max_;
00565     }
00566     
00567     
00568     static const int digits = Dune::bigunsignedint<k>::bits *
00569     Dune::bigunsignedint<k>::n;
00570     static const bool is_signed = false;
00571     static const bool is_integer = true;
00572     static const bool is_exact = true;
00573     static const int radix = 2;
00574     
00575     static Dune::bigunsignedint<k> epsilon()
00576     {
00577       return static_cast<Dune::bigunsignedint<k> >(0);
00578     }
00579 
00580     static Dune::bigunsignedint<k> round_error()
00581     {
00582       return static_cast<Dune::bigunsignedint<k> >(0);
00583     }
00584     
00585     static const int min_exponent = 0;
00586     static const int min_exponent10 = 0;
00587     static const int max_exponent = 0;
00588     static const int max_exponent10 = 0;
00589     
00590     static const bool has_infinity = false;
00591     static const bool has_quiet_NaN = false;
00592     static const bool has_signaling_NaN = false; 
00593     
00594     static const float_denorm_style has_denorm = denorm_absent;
00595     static const bool has_denorm_loss = false;
00596 
00597     static Dune::bigunsignedint<k> infinity() throw()
00598     { 
00599       return static_cast<Dune::bigunsignedint<k> >(0); 
00600     }
00601 
00602     static Dune::bigunsignedint<k> quiet_NaN() throw()
00603     { 
00604       return static_cast<Dune::bigunsignedint<k> >(0); 
00605     }
00606 
00607     static Dune::bigunsignedint<k> signaling_NaN() throw()
00608     { 
00609       return static_cast<Dune::bigunsignedint<k> >(0); 
00610     }
00611 
00612     static Dune::bigunsignedint<k> denorm_min() throw()
00613     { 
00614       return static_cast<Dune::bigunsignedint<k> >(0); 
00615     }
00616 
00617     static const bool is_iec559 = false;
00618     static const bool is_bounded = true;
00619     static const bool is_modulo = true;
00620 
00621     static const bool traps = false;
00622     static const bool tinyness_before = false;
00623     static const float_round_style round_style = round_toward_zero;
00624 
00625   };
00626   
00627 }
00628 
00629 #endif