dune-common  2.2.0
bigunsignedint.hh
Go to the documentation of this file.
1 // $Id: bigunsignedint.hh 6280 2010-11-29 23:40:59Z dedner $
2 
3 #ifndef DUNE_BIGUNSIGNEDINT_HH
4 #define DUNE_BIGUNSIGNEDINT_HH
5 
6 #include<iostream>
7 #include<limits>
8 #include<cstdlib>
10 
17 namespace Dune
18 {
24 #if HAVE_MPI
25  template<class K>
26  struct MPITraits;
27 #endif
28 
38  template<int k>
40  public:
41 
42  // unsigned short is 16 bits wide, n is the number of digits needed
43  enum { bits=std::numeric_limits<unsigned short>::digits, n=k/bits+(k%bits!=0),
44  hexdigits=4, bitmask=0xFFFF, compbitmask=0xFFFF0000,
45  overflowmask=0x1 };
46 
48  bigunsignedint ();
49 
51  bigunsignedint (int x);
52 
54  bigunsignedint (std::size_t x);
55 
57  void print (std::ostream& s) const ;
58 
61 
64 
67 
70 
75 
80 
81 
84 
87 
90 
93 
94 
96  bigunsignedint<k> operator<< (int i) const;
97 
99  bigunsignedint<k> operator>> (int i) const;
100 
101 
103  bool operator< (const bigunsignedint<k>& x) const;
104 
106  bool operator<= (const bigunsignedint<k>& x) const;
107 
109  bool operator> (const bigunsignedint<k>& x) const;
110 
112  bool operator>= (const bigunsignedint<k>& x) const;
113 
115  bool operator== (const bigunsignedint<k>& x) const;
116 
118  bool operator!= (const bigunsignedint<k>& x) const;
119 
120 
122 // operator unsigned int () const;
123  unsigned int touint() const;
129  double todouble() const;
130 
131  friend class bigunsignedint<k/2>;
132  friend struct std::numeric_limits< bigunsignedint<k> >;
133 
134  private:
135  unsigned short digit[n];
136 #if HAVE_MPI
137  friend class MPITraits<bigunsignedint<k> >;
138 #endif
139  inline void assign(std::size_t x);
140 
141 
142  } ;
143 
144  // Constructors
145  template<int k>
147  {
148  assign(0u);
149  }
150 
151  template<int k>
153  {
154  std::size_t x = std::abs(y);
155  assign(x);
156  }
157 
158  template<int k>
160  {
161  assign(x);
162  }
163  template<int k>
164  void bigunsignedint<k>::assign(std::size_t x)
165  {
166  int no=std::min(static_cast<int>(n),
167  static_cast<int>(std::numeric_limits<std::size_t>::digits/bits));
168 
169  for(int i=0; i<no; ++i){
170  digit[i] = (x&bitmask);
171  x=x>>bits;
172  }
173  for (unsigned int i=no; i<n; i++) digit[i]=0;
174  }
175 
176  // export
177  template<int k>
178  inline unsigned int bigunsignedint<k>::touint () const
179  {
180  return (digit[1]<<bits)+digit[0];
181  }
182 
183  template<int k>
184  inline double bigunsignedint<k>::todouble() const
185  {
186  int firstInZeroRange=n;
187  for(int i=n-1; i>=0; --i)
188  if(digit[i]!=0)
189  break;
190  else
191  --firstInZeroRange;
192  int representableDigits=std::numeric_limits<double>::digits/bits;
193  int lastInRepresentableRange=0;
194  if(representableDigits<firstInZeroRange)
195  lastInRepresentableRange=firstInZeroRange-representableDigits;
196  double val=0;
197  for(int i=firstInZeroRange-1; i>=lastInRepresentableRange; --i)
198  val =val*(1<<bits)+digit[i];
199  return val*(1<<(bits*lastInRepresentableRange));
200  }
201  // print
202  template<int k>
203  inline void bigunsignedint<k>::print (std::ostream& s) const
204  {
205  bool leading=false;
206 
207  // print from left to right
208  for (int i=n-1; i>=0; i--)
209  for (int d=hexdigits-1; d>=0; d--)
210  {
211  // extract one hex digit
212  int current = (digit[i]>>(d*4))&0xF;
213  if (current!=0)
214  {
215  // s.setf(std::ios::noshowbase);
216  s << std::hex << current;
217  leading = false;
218  }
219  else if (!leading) s << std::hex << current;
220  }
221  if (leading) s << "0";
222  s << std::dec;
223  }
224 
225  template <int k>
226  inline std::ostream& operator<< (std::ostream& s, const bigunsignedint<k>& x)
227  {
228  x.print(s);
229  return s;
230  }
231 
232 
233  // Operators
234  template <int k>
236  {
237  bigunsignedint<k> result;
238  int overflow=0;
239 
240  for (unsigned int i=0; i<n; i++)
241  {
242  int sum = ((int)digit[i]) + ((int)x.digit[i]) + overflow;
243  result.digit[i] = sum&bitmask;
244  overflow = (sum>>bits)&overflowmask;
245  }
246  return result;
247  }
248 
249  template <int k>
251  {
252  bigunsignedint<k> result;
253  int overflow=0;
254 
255  for (unsigned int i=0; i<n; i++)
256  {
257  int diff = ((int)digit[i]) - (((int)x.digit[i]) + overflow);
258  if (diff>=0)
259  result.digit[i] = (unsigned short) diff;
260  else
261  {
262  result.digit[i] = (unsigned short) (diff+bitmask);
263  overflow = 1;
264  }
265  }
266  return result;
267  }
268 
269  template <int k>
271  {
272  bigunsignedint<2*k> finalproduct(0);
273 
274  for (unsigned int m=0; m<n; m++) // digit in right factor
275  {
276  bigunsignedint<2*k> singleproduct(0);
277  unsigned int overflow(0);
278  for (unsigned int i=0; i<n; i++)
279  {
280  unsigned int digitproduct = ((unsigned int)digit[i])*((unsigned int)x.digit[m])+overflow;
281  singleproduct.digit[i+m] = (unsigned short) (digitproduct&bitmask);
282  overflow = (digitproduct>>bits)&bitmask;
283  }
284  finalproduct = finalproduct+singleproduct;
285  }
286 
287  bigunsignedint<k> result;
288  for (unsigned int i=0; i<n; i++) result.digit[i] = finalproduct.digit[i];
289  return result;
290  }
291 
292  template <int k>
294  {
295  int overflow=1;
296 
297  for (unsigned int i=0; i<n; i++)
298  {
299  int sum = ((int)digit[i]) + overflow;
300  digit[i] = sum&bitmask;
301  overflow = (sum>>bits)&overflowmask;
302  }
303  return *this;
304  }
305 
306  template <int k>
308  {
309  if(x==0)
310  DUNE_THROW(Dune::MathError, "division by zero!");
311 
312  // better slow than nothing
313  bigunsignedint<k> temp(*this);
314  bigunsignedint<k> result(0);
315 
316  while (temp>=x)
317  {
318  ++result;
319  temp = temp-x;
320  }
321 
322  return result;
323  }
324 
325  template <int k>
327  {
328  // better slow than nothing
329  bigunsignedint<k> temp(*this);
330  bigunsignedint<k> result(0);
331 
332  while (temp>=x)
333  {
334  ++result;
335  temp = temp-x;
336  }
337 
338  return temp;
339  }
340 
341 
342  template <int k>
344  {
345  bigunsignedint<k> result;
346  for (unsigned int i=0; i<n; i++)
347  result.digit[i] = digit[i]&x.digit[i];
348  return result;
349  }
350 
351  template <int k>
353  {
354  bigunsignedint<k> result;
355  for (unsigned int i=0; i<n; i++)
356  result.digit[i] = digit[i]^x.digit[i];
357  return result;
358  }
359 
360  template <int k>
362  {
363  bigunsignedint<k> result;
364  for (unsigned int i=0; i<n; i++)
365  result.digit[i] = digit[i]|x.digit[i];
366  return result;
367  }
368 
369  template <int k>
371  {
372  bigunsignedint<k> result;
373  for (unsigned int i=0; i<n; i++)
374  result.digit[i] = ~digit[i];
375  return result;
376  }
377 
378  template <int k>
380  {
381  bigunsignedint<k> result(0);
382 
383  // multiples of bits
384  int j=shift/bits;
385  for (int i=n-1-j; i>=0; i--)
386  result.digit[i+j] = digit[i];
387 
388  // remainder
389  j=shift%bits;
390  for (int i=n-1; i>=0; i--)
391  {
392  unsigned int temp = result.digit[i];
393  temp = temp<<j;
394  result.digit[i] = (unsigned short) (temp&bitmask);
395  temp = temp>>bits;
396  if (i+1<(int)n)
397  result.digit[i+1] = result.digit[i+1]|temp;
398  }
399 
400  return result;
401  }
402 
403  template <int k>
405  {
406  bigunsignedint<k> result(0);
407 
408  // multiples of bits
409  int j=shift/bits;
410  for (unsigned int i=0; i<n-j; i++)
411  result.digit[i] = digit[i+j];
412 
413  // remainder
414  j=shift%bits;
415  for (unsigned int i=0; i<n; i++)
416  {
417  unsigned int temp = result.digit[i];
418  temp = temp<<(bits-j);
419  result.digit[i] = (unsigned short) ((temp&compbitmask)>>bits);
420  if (i>0)
421  result.digit[i-1] = result.digit[i-1] | (temp&bitmask);
422  }
423 
424  return result;
425  }
426 
427  template <int k>
429  {
430  for (unsigned int i=0; i<n; i++)
431  if (digit[i]!=x.digit[i]) return true;
432  return false;
433  }
434 
435  template <int k>
437  {
438  return !((*this)!=x);
439  }
440 
441  template <int k>
443  {
444  for (int i=n-1; i>=0; i--)
445  if (digit[i]<x.digit[i]) return true;
446  else if (digit[i]>x.digit[i]) return false;
447  return false;
448  }
449 
450  template <int k>
452  {
453  for (int i=n-1; i>=0; i--)
454  if (digit[i]<x.digit[i]) return true;
455  else if (digit[i]>x.digit[i]) return false;
456  return true;
457  }
458 
459  template <int k>
461  {
462  return !((*this)<=x);
463  }
464 
465  template <int k>
467  {
468  return !((*this)<x);
469  }
470 
471 
472  template <int k>
473  inline bigunsignedint<k> operator+ (const bigunsignedint<k>& x, std::size_t y)
474  {
475  bigunsignedint<k> temp(y);
476  return x+temp;
477  }
478 
479  template <int k>
480  inline bigunsignedint<k> operator- (const bigunsignedint<k>& x, std::size_t y)
481  {
482  bigunsignedint<k> temp(y);
483  return x-temp;
484  }
485 
486  template <int k>
487  inline bigunsignedint<k> operator* (const bigunsignedint<k>& x, std::size_t y)
488  {
489  bigunsignedint<k> temp(y);
490  return x*temp;
491  }
492 
493  template <int k>
494  inline bigunsignedint<k> operator/ (const bigunsignedint<k>& x, std::size_t y)
495  {
496  bigunsignedint<k> temp(y);
497  return x/temp;
498  }
499 
500  template <int k>
501  inline bigunsignedint<k> operator% (const bigunsignedint<k>& x, std::size_t y)
502  {
503  bigunsignedint<k> temp(y);
504  return x%temp;
505  }
506 
507  template <int k>
508  inline bigunsignedint<k> operator+ (std::size_t x, const bigunsignedint<k>& y)
509  {
510  bigunsignedint<k> temp(x);
511  return temp+y;
512  }
513 
514  template <int k>
515  inline bigunsignedint<k> operator- (std::size_t x, const bigunsignedint<k>& y)
516  {
517  bigunsignedint<k> temp(x);
518  return temp-y;
519  }
520 
521  template <int k>
522  inline bigunsignedint<k> operator* (std::size_t x, const bigunsignedint<k>& y)
523  {
524  bigunsignedint<k> temp(x);
525  return temp*y;
526  }
527 
528  template <int k>
529  inline bigunsignedint<k> operator/ (std::size_t x, const bigunsignedint<k>& y)
530  {
531  bigunsignedint<k> temp(x);
532  return temp/y;
533  }
534 
535  template <int k>
536  inline bigunsignedint<k> operator% (std::size_t x, const bigunsignedint<k>& y)
537  {
538  bigunsignedint<k> temp(x);
539  return temp%y;
540  }
541 
542 
544 }
545 
546 namespace std
547 {
548  template<int k>
549  struct numeric_limits<Dune::bigunsignedint<k> >
550  {
551  public:
552  static const bool is_specialized = true;
553 
555  {
556  return static_cast<Dune::bigunsignedint<k> >(0);
557  }
558 
560  {
562  for(std::size_t i=0; i < Dune::bigunsignedint<k>::n; ++i)
563  max_.digit[i]=std::numeric_limits<unsigned short>::max();
564  return max_;
565  }
566 
567 
568  static const int digits = Dune::bigunsignedint<k>::bits *
570  static const bool is_signed = false;
571  static const bool is_integer = true;
572  static const bool is_exact = true;
573  static const int radix = 2;
574 
575  static Dune::bigunsignedint<k> epsilon()
576  {
577  return static_cast<Dune::bigunsignedint<k> >(0);
578  }
579 
580  static Dune::bigunsignedint<k> round_error()
581  {
582  return static_cast<Dune::bigunsignedint<k> >(0);
583  }
584 
585  static const int min_exponent = 0;
586  static const int min_exponent10 = 0;
587  static const int max_exponent = 0;
588  static const int max_exponent10 = 0;
589 
590  static const bool has_infinity = false;
591  static const bool has_quiet_NaN = false;
592  static const bool has_signaling_NaN = false;
593 
594  static const float_denorm_style has_denorm = denorm_absent;
595  static const bool has_denorm_loss = false;
596 
597  static Dune::bigunsignedint<k> infinity() throw()
598  {
599  return static_cast<Dune::bigunsignedint<k> >(0);
600  }
601 
602  static Dune::bigunsignedint<k> quiet_NaN() throw()
603  {
604  return static_cast<Dune::bigunsignedint<k> >(0);
605  }
606 
607  static Dune::bigunsignedint<k> signaling_NaN() throw()
608  {
609  return static_cast<Dune::bigunsignedint<k> >(0);
610  }
611 
612  static Dune::bigunsignedint<k> denorm_min() throw()
613  {
614  return static_cast<Dune::bigunsignedint<k> >(0);
615  }
616 
617  static const bool is_iec559 = false;
618  static const bool is_bounded = true;
619  static const bool is_modulo = true;
620 
621  static const bool traps = false;
622  static const bool tinyness_before = false;
623  static const float_round_style round_style = round_toward_zero;
624 
625  };
626 
627 }
628 
629 #endif