Dune Core Modules (2.4.1)

bigunsignedint.hh
Go to the documentation of this file.
1// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
2// vi: set et ts=4 sw=2 sts=2:
3
4#ifndef DUNE_BIGUNSIGNEDINT_HH
5#define DUNE_BIGUNSIGNEDINT_HH
6
7#include <iostream>
8#include <limits>
9#include <cstdint>
10#include <cstdlib>
11#include <type_traits>
13#include <dune/common/hash.hh>
14
21namespace Dune
22{
28#if HAVE_MPI
29 template<class K>
30 struct MPITraits;
31#endif
32
33 namespace {
34
35 // numeric_limits_helper provides std::numeric_limits access to the internals
36 // of bigunsignedint. Previously, the correct specialization of std::numeric_limits
37 // was a friend of bigunsignedint, but that creates problems on recent versions
38 // of clang with the alternative libc++ library, because that library declares the
39 // base template of std::numeric_limits as a class and clang subsequently complains
40 // if the friend declaration uses 'struct'. Unfortunately, libstdc++ uses a struct,
41 // making it impossible to keep clang happy for both standard libraries.
42 // So we move the access helper functionality into a custom struct and simply let
43 // the numeric_limits specialization inherit from the helper.
44
45 template<typename T>
46 struct numeric_limits_helper
47 {
48
49 protected:
50
51 static std::uint16_t& digit(T& big_unsigned_int, std::size_t i)
52 {
53 return big_unsigned_int.digit[i];
54 }
55
56 };
57
58 }
59
69 template<int k>
71 public:
72
73 // unsigned short is 16 bits wide, n is the number of digits needed
74 enum { bits=std::numeric_limits<std::uint16_t>::digits, n=k/bits+(k%bits!=0),
75 hexdigits=4, bitmask=0xFFFF, compbitmask=0xFFFF0000,
76 overflowmask=0x1 };
77
80
82 template<typename Signed>
83 bigunsignedint (Signed x, typename std::enable_if<std::is_integral<Signed>::value && std::is_signed<Signed>::value>::type* = 0);
84
86 bigunsignedint (std::uintmax_t x);
87
89 void print (std::ostream& s) const ;
90
93
96
99
102
107
112
113
116
119
122
125
126
128 bigunsignedint<k> operator<< (int i) const;
129
131 bigunsignedint<k> operator>> (int i) const;
132
133
135 bool operator< (const bigunsignedint<k>& x) const;
136
138 bool operator<= (const bigunsignedint<k>& x) const;
139
141 bool operator> (const bigunsignedint<k>& x) const;
142
144 bool operator>= (const bigunsignedint<k>& x) const;
145
147 bool operator== (const bigunsignedint<k>& x) const;
148
150 bool operator!= (const bigunsignedint<k>& x) const;
151
152
154 // operator unsigned int () const;
155 std::uint_least32_t touint() const;
161 double todouble() const;
162
163 friend class bigunsignedint<k/2>;
164 friend struct numeric_limits_helper< bigunsignedint<k> >;
165
166 inline friend std::size_t hash_value(const bigunsignedint& arg)
167 {
168 return hash_range(arg.digit,arg.digit + arg.n);
169 }
170
171 private:
172 std::uint16_t digit[n];
173#if HAVE_MPI
174 friend struct MPITraits<bigunsignedint<k> >;
175#endif
176 inline void assign(std::uintmax_t x);
177
178
179 } ;
180
181 // Constructors
182 template<int k>
184 {
185 assign(0u);
186 }
187
188 template<int k>
189 template<typename Signed>
190 bigunsignedint<k>::bigunsignedint (Signed y, typename std::enable_if<std::is_integral<Signed>::value && std::is_signed<Signed>::value>::type*)
191 {
192 if (y < 0)
193 DUNE_THROW(Dune::Exception, "Trying to construct a Dune::bigunsignedint from a negative integer: " << y);
194 assign(y);
195 }
196
197 template<int k>
199 {
200 assign(x);
201 }
202 template<int k>
203 void bigunsignedint<k>::assign(std::uintmax_t x)
204 {
205 static const int no=std::min(static_cast<int>(n),
206 static_cast<int>(std::numeric_limits<std::uintmax_t>::digits/bits));
207
208 for(int i=0; i<no; ++i) {
209 digit[i] = (x&bitmask);
210 x=x>>bits;
211 }
212 for (unsigned int i=no; i<n; i++) digit[i]=0;
213 }
214
215 // export
216 template<int k>
217 inline std::uint_least32_t bigunsignedint<k>::touint () const
218 {
219 return (digit[1]<<bits)+digit[0];
220 }
221
222 template<int k>
223 inline double bigunsignedint<k>::todouble() const
224 {
225 int firstInZeroRange=n;
226 for(int i=n-1; i>=0; --i)
227 if(digit[i]!=0)
228 break;
229 else
230 --firstInZeroRange;
231 int representableDigits=std::numeric_limits<double>::digits/bits;
232 int lastInRepresentableRange=0;
233 if(representableDigits<firstInZeroRange)
234 lastInRepresentableRange=firstInZeroRange-representableDigits;
235 double val=0;
236 for(int i=firstInZeroRange-1; i>=lastInRepresentableRange; --i)
237 val =val*(1<<bits)+digit[i];
238 return val*(1<<(bits*lastInRepresentableRange));
239 }
240 // print
241 template<int k>
242 inline void bigunsignedint<k>::print (std::ostream& s) const
243 {
244 bool leading=false;
245
246 // print from left to right
247 for (int i=n-1; i>=0; i--)
248 for (int d=hexdigits-1; d>=0; d--)
249 {
250 // extract one hex digit
251 int current = (digit[i]>>(d*4))&0xF;
252 if (current!=0)
253 {
254 // s.setf(std::ios::noshowbase);
255 s << std::hex << current;
256 leading = false;
257 }
258 else if (!leading) s << std::hex << current;
259 }
260 if (leading) s << "0";
261 s << std::dec;
262 }
263
264 template <int k>
265 inline std::ostream& operator<< (std::ostream& s, const bigunsignedint<k>& x)
266 {
267 x.print(s);
268 return s;
269 }
270
271
272 // Operators
273 template <int k>
275 {
276 bigunsignedint<k> result;
277 std::uint_fast32_t overflow=0;
278
279 for (unsigned int i=0; i<n; i++)
280 {
281 std::uint_fast32_t sum = static_cast<std::uint_fast32_t>(digit[i]) + static_cast<std::uint_fast32_t>(x.digit[i]) + overflow;
282 result.digit[i] = sum&bitmask;
283 overflow = (sum>>bits)&overflowmask;
284 }
285 return result;
286 }
287
288 template <int k>
290 {
291 bigunsignedint<k> result;
292 std::int_fast32_t overflow=0;
293
294 for (unsigned int i=0; i<n; i++)
295 {
296 std::int_fast32_t diff = static_cast<std::int_fast32_t>(digit[i]) - static_cast<std::int_fast32_t>(x.digit[i]) - overflow;
297 if (diff>=0)
298 {
299 result.digit[i] = static_cast<std::uint16_t>(diff);
300 overflow = 0;
301 }
302 else
303 {
304 result.digit[i] = static_cast<std::uint16_t>(diff+bitmask+1);
305 overflow = 1;
306 }
307 }
308 return result;
309 }
310
311 template <int k>
313 {
314 bigunsignedint<2*k> finalproduct(0);
315
316 for (unsigned int m=0; m<n; m++) // digit in right factor
317 {
318 bigunsignedint<2*k> singleproduct(0);
319 std::uint_fast32_t overflow(0);
320 for (unsigned int i=0; i<n; i++)
321 {
322 std::uint_fast32_t digitproduct = static_cast<std::uint_fast32_t>(digit[i])*static_cast<std::uint_fast32_t>(x.digit[m])+overflow;
323 singleproduct.digit[i+m] = static_cast<std::uint16_t>(digitproduct&bitmask);
324 overflow = (digitproduct>>bits)&bitmask;
325 }
326 finalproduct = finalproduct+singleproduct;
327 }
328
329 bigunsignedint<k> result;
330 for (unsigned int i=0; i<n; i++) result.digit[i] = finalproduct.digit[i];
331 return result;
332 }
333
334 template <int k>
336 {
337 std::uint_fast32_t overflow=1;
338
339 for (unsigned int i=0; i<n; i++)
340 {
341 std::uint_fast32_t sum = static_cast<std::uint_fast32_t>(digit[i]) + overflow;
342 digit[i] = sum&bitmask;
343 overflow = (sum>>bits)&overflowmask;
344 }
345 return *this;
346 }
347
348 template <int k>
350 {
351 if(x==0)
352 DUNE_THROW(Dune::MathError, "division by zero!");
353
354 // better slow than nothing
355 bigunsignedint<k> temp(*this);
356 bigunsignedint<k> result(0);
357
358 while (temp>=x)
359 {
360 ++result;
361 temp = temp-x;
362 }
363
364 return result;
365 }
366
367 template <int k>
369 {
370 // better slow than nothing
371 bigunsignedint<k> temp(*this);
372
373 while (temp>=x)
374 {
375 temp = temp-x;
376 }
377
378 return temp;
379 }
380
381
382 template <int k>
384 {
385 bigunsignedint<k> result;
386 for (unsigned int i=0; i<n; i++)
387 result.digit[i] = digit[i]&x.digit[i];
388 return result;
389 }
390
391 template <int k>
393 {
394 bigunsignedint<k> result;
395 for (unsigned int i=0; i<n; i++)
396 result.digit[i] = digit[i]^x.digit[i];
397 return result;
398 }
399
400 template <int k>
402 {
403 bigunsignedint<k> result;
404 for (unsigned int i=0; i<n; i++)
405 result.digit[i] = digit[i]|x.digit[i];
406 return result;
407 }
408
409 template <int k>
411 {
412 bigunsignedint<k> result;
413 for (unsigned int i=0; i<n; i++)
414 result.digit[i] = ~digit[i];
415 return result;
416 }
417
418 template <int k>
420 {
421 bigunsignedint<k> result(0);
422
423 // multiples of bits
424 int j=shift/bits;
425 for (int i=n-1-j; i>=0; i--)
426 result.digit[i+j] = digit[i];
427
428 // remainder
429 j=shift%bits;
430 for (int i=n-1; i>=0; i--)
431 {
432 unsigned int temp = result.digit[i];
433 temp = temp<<j;
434 result.digit[i] = static_cast<std::uint16_t>(temp&bitmask);
435 temp = temp>>bits;
436 if (i+1<(int)n)
437 result.digit[i+1] = result.digit[i+1]|temp;
438 }
439
440 return result;
441 }
442
443 template <int k>
445 {
446 bigunsignedint<k> result(0);
447
448 // multiples of bits
449 int j=shift/bits;
450 for (unsigned int i=0; i<n-j; i++)
451 result.digit[i] = digit[i+j];
452
453 // remainder
454 j=shift%bits;
455 for (unsigned int i=0; i<n; i++)
456 {
457 std::uint_fast32_t temp = result.digit[i];
458 temp = temp<<(bits-j);
459 result.digit[i] = static_cast<std::uint16_t>((temp&compbitmask)>>bits);
460 if (i>0)
461 result.digit[i-1] = result.digit[i-1] | (temp&bitmask);
462 }
463
464 return result;
465 }
466
467 template <int k>
469 {
470 for (unsigned int i=0; i<n; i++)
471 if (digit[i]!=x.digit[i]) return true;
472 return false;
473 }
474
475 template <int k>
477 {
478 return !((*this)!=x);
479 }
480
481 template <int k>
483 {
484 for (int i=n-1; i>=0; i--)
485 if (digit[i]<x.digit[i]) return true;
486 else if (digit[i]>x.digit[i]) return false;
487 return false;
488 }
489
490 template <int k>
492 {
493 for (int i=n-1; i>=0; i--)
494 if (digit[i]<x.digit[i]) return true;
495 else if (digit[i]>x.digit[i]) return false;
496 return true;
497 }
498
499 template <int k>
501 {
502 return !((*this)<=x);
503 }
504
505 template <int k>
507 {
508 return !((*this)<x);
509 }
510
511
512 template <int k>
513 inline bigunsignedint<k> operator+ (const bigunsignedint<k>& x, std::uintmax_t y)
514 {
515 bigunsignedint<k> temp(y);
516 return x+temp;
517 }
518
519 template <int k>
520 inline bigunsignedint<k> operator- (const bigunsignedint<k>& x, std::uintmax_t y)
521 {
522 bigunsignedint<k> temp(y);
523 return x-temp;
524 }
525
526 template <int k>
527 inline bigunsignedint<k> operator* (const bigunsignedint<k>& x, std::uintmax_t y)
528 {
529 bigunsignedint<k> temp(y);
530 return x*temp;
531 }
532
533 template <int k>
534 inline bigunsignedint<k> operator/ (const bigunsignedint<k>& x, std::uintmax_t y)
535 {
536 bigunsignedint<k> temp(y);
537 return x/temp;
538 }
539
540 template <int k>
541 inline bigunsignedint<k> operator% (const bigunsignedint<k>& x, std::uintmax_t y)
542 {
543 bigunsignedint<k> temp(y);
544 return x%temp;
545 }
546
547 template <int k>
548 inline bigunsignedint<k> operator+ (std::uintmax_t x, const bigunsignedint<k>& y)
549 {
550 bigunsignedint<k> temp(x);
551 return temp+y;
552 }
553
554 template <int k>
555 inline bigunsignedint<k> operator- (std::uintmax_t x, const bigunsignedint<k>& y)
556 {
557 bigunsignedint<k> temp(x);
558 return temp-y;
559 }
560
561 template <int k>
562 inline bigunsignedint<k> operator* (std::uintmax_t x, const bigunsignedint<k>& y)
563 {
564 bigunsignedint<k> temp(x);
565 return temp*y;
566 }
567
568 template <int k>
569 inline bigunsignedint<k> operator/ (std::uintmax_t x, const bigunsignedint<k>& y)
570 {
571 bigunsignedint<k> temp(x);
572 return temp/y;
573 }
574
575 template <int k>
576 inline bigunsignedint<k> operator% (std::uintmax_t x, const bigunsignedint<k>& y)
577 {
578 bigunsignedint<k> temp(x);
579 return temp%y;
580 }
581
582
584}
585
586namespace std
587{
588 template<int k>
589 struct numeric_limits<Dune::bigunsignedint<k> >
590 : private Dune::numeric_limits_helper<Dune::bigunsignedint<k> > // for access to internal state of bigunsignedint
591 {
592 public:
593 static const bool is_specialized = true;
594
595 static Dune::bigunsignedint<k> min()
596 {
597 return static_cast<Dune::bigunsignedint<k> >(0);
598 }
599
600 static Dune::bigunsignedint<k> max()
601 {
603 for(std::size_t i=0; i < Dune::bigunsignedint<k>::n; ++i)
604 // access internal state via the helper base class
605 Dune::numeric_limits_helper<Dune::bigunsignedint<k> >::
606 digit(max_,i)=std::numeric_limits<std::uint16_t>::max();
607 return max_;
608 }
609
610
611 static const int digits = Dune::bigunsignedint<k>::bits *
613 static const bool is_signed = false;
614 static const bool is_integer = true;
615 static const bool is_exact = true;
616 static const int radix = 2;
617
618 static Dune::bigunsignedint<k> epsilon()
619 {
620 return static_cast<Dune::bigunsignedint<k> >(0);
621 }
622
623 static Dune::bigunsignedint<k> round_error()
624 {
625 return static_cast<Dune::bigunsignedint<k> >(0);
626 }
627
628 static const int min_exponent = 0;
629 static const int min_exponent10 = 0;
630 static const int max_exponent = 0;
631 static const int max_exponent10 = 0;
632
633 static const bool has_infinity = false;
634 static const bool has_quiet_NaN = false;
635 static const bool has_signaling_NaN = false;
636
637 static const float_denorm_style has_denorm = denorm_absent;
638 static const bool has_denorm_loss = false;
639
640 static Dune::bigunsignedint<k> infinity() throw()
641 {
642 return static_cast<Dune::bigunsignedint<k> >(0);
643 }
644
645 static Dune::bigunsignedint<k> quiet_NaN() throw()
646 {
647 return static_cast<Dune::bigunsignedint<k> >(0);
648 }
649
650 static Dune::bigunsignedint<k> signaling_NaN() throw()
651 {
652 return static_cast<Dune::bigunsignedint<k> >(0);
653 }
654
655 static Dune::bigunsignedint<k> denorm_min() throw()
656 {
657 return static_cast<Dune::bigunsignedint<k> >(0);
658 }
659
660 static const bool is_iec559 = false;
661 static const bool is_bounded = true;
662 static const bool is_modulo = true;
663
664 static const bool traps = false;
665 static const bool tinyness_before = false;
666 static const float_round_style round_style = round_toward_zero;
667
668 };
669
670}
671
673
674#endif
Base class for Dune-Exceptions.
Definition: exceptions.hh:91
Default exception class for mathematical errors.
Definition: exceptions.hh:266
Portable very large unsigned integers.
Definition: bigunsignedint.hh:70
A few common exception classes.
bigunsignedint< k > operator|(const bigunsignedint< k > &x) const
bitwise or
Definition: bigunsignedint.hh:401
bigunsignedint< k > operator<<(int i) const
left shift1/
Definition: bigunsignedint.hh:419
bool operator<=(const bigunsignedint< k > &x) const
less than or equal
Definition: bigunsignedint.hh:491
bigunsignedint< k > operator^(const bigunsignedint< k > &x) const
bitwise exor
Definition: bigunsignedint.hh:392
void print(std::ostream &s) const
Print number in hex notation.
Definition: bigunsignedint.hh:242
bigunsignedint< k > operator*(const bigunsignedint< k > &x) const
multiply
Definition: bigunsignedint.hh:312
bool operator<(const bigunsignedint< k > &x) const
less than
Definition: bigunsignedint.hh:482
bool operator==(const bigunsignedint< k > &x) const
equal
Definition: bigunsignedint.hh:476
bool operator!=(const bigunsignedint< k > &x) const
not equal
Definition: bigunsignedint.hh:468
bigunsignedint< k > operator%(const bigunsignedint< k > &x) const
Definition: bigunsignedint.hh:368
bigunsignedint()
Construct uninitialized.
Definition: bigunsignedint.hh:183
bool operator>=(const bigunsignedint< k > &x) const
greater or equal
Definition: bigunsignedint.hh:506
std::ostream & operator<<(std::ostream &s, const array< T, N > &e)
Output operator for array.
Definition: array.hh:26
bigunsignedint< k > operator>>(int i) const
right shift
Definition: bigunsignedint.hh:444
bigunsignedint< k > operator~() const
bitwise komplement
Definition: bigunsignedint.hh:410
bigunsignedint< k > operator-(const bigunsignedint< k > &x) const
subtract
Definition: bigunsignedint.hh:289
bigunsignedint< k > & operator++()
prefix increment
Definition: bigunsignedint.hh:335
double todouble() const
Convert to a double.
Definition: bigunsignedint.hh:223
bigunsignedint< k > operator&(const bigunsignedint< k > &x) const
bitwise and
Definition: bigunsignedint.hh:383
bigunsignedint< k > operator/(const bigunsignedint< k > &x) const
Definition: bigunsignedint.hh:349
bigunsignedint< k > operator+(const bigunsignedint< k > &x) const
add
Definition: bigunsignedint.hh:274
bool operator>(const bigunsignedint< k > &x) const
greater than
Definition: bigunsignedint.hh:500
std::uint_least32_t touint() const
export to other types
Definition: bigunsignedint.hh:217
#define DUNE_THROW(E, m)
Definition: exceptions.hh:243
Support for calculating hash values of objects.
#define DUNE_DEFINE_HASH(template_args, type)
Defines the required struct specialization to make type hashable via Dune::hash.
Definition: hash.hh:98
#define DUNE_HASH_TYPE(...)
Wrapper macro for the type to be hashed in DUNE_DEFINE_HASH.
Definition: hash.hh:115
#define DUNE_HASH_TEMPLATE_ARGS(...)
Wrapper macro for the template arguments in DUNE_DEFINE_HASH.
Definition: hash.hh:107
Dune namespace.
Definition: alignment.hh:10
std::size_t hash_range(It first, It last)
Hashes all elements in the range [first,last) and returns the combined hash.
Definition: hash.hh:309
STL namespace.
A traits class describing the mapping of types onto MPI_Datatypes.
Definition: mpitraits.hh:37
Creative Commons License   |  Legal Statements / Impressum  |  Hosted by TU Dresden  |  generated with Hugo v0.111.3 (Nov 12, 23:30, 2024)