dune-common
2.2.0
|
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