mCRL2
Loading...
Searching...
No Matches
big_numbers.h
Go to the documentation of this file.
1// Author(s): Jan Friso Groote
2// Copyright: see the accompanying file COPYING or copy at
3// https://github.com/mCRL2org/mCRL2/blob/master/COPYING
4//
5// Distributed under the Boost Software License, Version 1.0.
6// (See accompanying file LICENSE_1_0.txt or copy at
7// http://www.boost.org/LICENSE_1_0.txt)
8//
9
18#ifndef MCRL2_UTILITIES_BIG_NUMBERS_H
19#define MCRL2_UTILITIES_BIG_NUMBERS_H
20
21#include <algorithm>
22#include <limits>
23#include <string>
26
27// Prototype.
28namespace mcrl2
29{
30namespace utilities
31{
32class big_natural_number;
33
34inline std::string pp(const big_natural_number& l);
35
36} // namespace utilities
37} // namespace mcrl2
38
39
40namespace mcrl2
41{
42namespace utilities
43{
44namespace detail
45{
46
47 // Calculate <carry,result>:=n1+n2+carry. The carry can be either 0 or 1, both
48 // at the input and the output.
49 inline std::size_t add_single_number(const std::size_t n1, const std::size_t n2, std::size_t& carry)
50 {
51 assert(carry<=1);
52 std::size_t result=n1+n2+carry;
53 if (carry==0)
54 {
55 if (result<n1)
56 {
57 carry=1;
58 }
59 }
60 else // carry==1
61 {
62 if (result>n1)
63 {
64 carry=0;
65 }
66 }
67 return result;
68 }
69
70 // Calculate <carry,result>:=n1-n2-carry. The carry can be either 0 or 1, both
71 // at the input and the output. If the carry is 1, this indicated that 1 must be subtracted.
72 inline std::size_t subtract_single_number(const std::size_t n1, const std::size_t n2, std::size_t& carry)
73 {
74 assert(carry<=1);
75 std::size_t result=n1-n2-carry;
76 if (carry==0)
77 {
78 if (result>n1)
79 {
80 carry=1;
81 }
82 }
83 else // carry==1
84 {
85 if (result<n1)
86 {
87 carry=0;
88 }
89 }
90 return result;
91 }
92
93 // Calculate <carry,result>:=n1*n2+carry, where the lower bits of the calculation
94 // are stored in the result, and the higher bits are stored in carry.
95 inline std::size_t multiply_single_number(const std::size_t n1, const std::size_t n2, std::size_t& multiplication_carry)
96 {
97 // TODO: It is more concise and efficient to use 128bit machine calculation when available.
98 const int no_of_bits_per_digit=std::numeric_limits<std::size_t>::digits;
99
100 // split input numbers into no_of_bits_per_digit/2 digits
101 std::size_t n1ls = n1 & ((1LL<<(no_of_bits_per_digit/2))-1);
102 std::size_t n1ms = n1 >> (no_of_bits_per_digit/2);
103 std::size_t n2ls = n2 & ((1LL<<(no_of_bits_per_digit/2))-1);
104 std::size_t n2ms = n2 >> (no_of_bits_per_digit/2);
105
106 // First calculate the result of the least significant no_of_bits_per_digit.
107 std::size_t local_carry=0;
108 std::size_t result = add_single_number(n1ls*n2ls,multiplication_carry,local_carry);
109 std::size_t cumulative_carry=local_carry;
110 local_carry=0;
111 result=add_single_number(result,((n1ms*n2ls)<<(no_of_bits_per_digit/2)),local_carry);
112 cumulative_carry=cumulative_carry+local_carry;
113 local_carry=0;
114 result=add_single_number(result,((n1ls*n2ms)<<(no_of_bits_per_digit/2)),local_carry);
115 cumulative_carry=cumulative_carry+local_carry;
116
117 // Now calculate the result of the most significant no_of_bits_per_digit.
118 multiplication_carry=cumulative_carry;
119 multiplication_carry=multiplication_carry+((n1ms*n2ls)>>(no_of_bits_per_digit/2));
120 multiplication_carry=multiplication_carry+((n1ls*n2ms)>>(no_of_bits_per_digit/2));
121 multiplication_carry=multiplication_carry+n1ms*n2ms;
122
123 return result;
124 }
125
126 // Calculate <result,remainder>:=(remainder * 2^64 + p) / q assuming the result
127 // fits in 64 bits. More concretely, q>remainder.
128 inline std::size_t divide_single_number(const std::size_t p, const std::size_t q, std::size_t& remainder)
129 {
130 assert(q>remainder);
131 const int no_of_bits_per_digit=std::numeric_limits<std::size_t>::digits;
132
133 // Split input numbers into no_of_bits_per_digit/2 digits.
134 // First get the least significant part.
135 std::size_t pms = (p >> (no_of_bits_per_digit/2)) + (remainder << (no_of_bits_per_digit/2));
136
137 // First divide the most significant part by q.
138 std::size_t resultms = pms/q;
139 assert((resultms >> (no_of_bits_per_digit/2)) == 0);
140 std::size_t remainderms = pms%q;
141
142 // Now obtain the least significant part.
143 std::size_t pls = (p & ((1LL<<(no_of_bits_per_digit/2))-1)) + (remainderms << (no_of_bits_per_digit/2));
144
145 // Second divide the least significant part by q.
146 std::size_t resultls = pls/q;
147 remainder = pls%q;
148 assert((resultls >> (no_of_bits_per_digit/2)) == 0);
149
150 return resultls + (resultms << (no_of_bits_per_digit/2));
151 }
152
153 // Calculate the common greates divisor of p and q.
154 inline std::size_t greatest_common_divisor(std::size_t p, std::size_t q)
155 {
156 if (p==0) { return q; }
157 if (q==0) { return p; }
158 if (p<q)
159 {
160 std::swap(p,q);
161 }
162 // p is the largest.
163 std::size_t remainder=p % q;
164 while (remainder>0)
165 {
166 p=q;
167 q=remainder;
168 remainder=p % q;
169 }
170 return q;
171 }
172
173 inline void remove_common_divisor(std::size_t& p, std::size_t& q)
174 {
175 const std::size_t gcd=greatest_common_divisor(p,q);
176 p = p/gcd;
177 q = q/gcd;
178 assert(greatest_common_divisor(p,q)==1);
179 }
180
181} // namespace detail
182
183// class big_natural_number;
184inline std::string pp(const big_natural_number& l);
185
187{
188 friend std::hash<big_natural_number>;
189 friend inline void swap(big_natural_number& x, big_natural_number& y);
190
191 protected:
192 // Numbers are stored as std::size_t words, with the most significant number last.
193 // Note that the number representation is not unique. Numbers have no trailing
194 // zero's, i.e., this->back()!=0 (if this->size()>0). Therefore their representation is unique.
195 std::vector<std::size_t> m_number;
196
197 /* Multiply the current number by n and add the carry */
198 void multiply_by(std::size_t n, std::size_t carry)
199 {
200 for(std::size_t& i: m_number)
201 {
203 }
204 if (carry)
205 {
206 /* Add an extra digit with the carry */
207 m_number.push_back(carry);
208 }
211 }
212
213 // Remove zero's at the end of m_number vector that are
214 // leading and irrelevant zero's in the number representation.
216 {
217 for( ; m_number.size()>0 && m_number.back()==0 ; )
218 {
219 m_number.pop_back();
220 }
221 }
222
223 // Check that the number is well defined, in the sense
224 // that there are no most significant digits that are zero.
225 void is_well_defined() const
226 {
227 assert(m_number.size()==0 || m_number.back()!=0);
228 }
229
230 // \brief This functions prints a number in internal represenation. This function is useful and only meant for debugging.
231 void print_number(const std::string& s) const
232 {
233 std::cerr << s << " " << m_number.size() << "\n";
234 for(std::size_t i: m_number)
235 {
236 std::cerr << i << " ";
237 }
238 std::cerr << "\n---------------------\n";
239 }
240
241 public:
242 // Default constructor. The value is 0 by default.
244 {
245 }
246
247 // Constructor based on a std::size_t. The value of the number will be n.
248 explicit big_natural_number(const std::size_t n)
249 {
250 if (n>0)
251 {
252 m_number.push_back(n);
253 }
255 }
256
257 // Constructor based on a string. The string is a digital number.
258 big_natural_number(const std::string& s)
259 {
260 for(char c: s)
261 {
262 if (!isdigit(c))
263 {
264 throw mcrl2::runtime_error("Number " + s + " contains symbol '" + c + "' which is not a digit.");
265 }
266 if (c>='0')
267 {
268 multiply_by(10,std::size_t(c-'0'));
269 }
270 }
272 }
273
274 // Add a digit the this natural number.
275 void push_back(const std::size_t n)
276 {
277 m_number.push_back(n);
278 }
279
283 bool is_zero() const
284 {
286 return m_number.size()==0;
287 }
288
292 bool is_number(std::size_t n) const
293 {
295 if (n==0)
296 {
297 return m_number.size()==0;
298 }
299 return m_number.size()==1 && m_number.front()==n;
300 }
301
305 void clear()
306 {
308 m_number.clear();
309 }
310
314 explicit operator std::size_t() const
315 {
317 if (m_number.size()>1)
318 {
319 throw mcrl2::runtime_error("It is not possible to transform a big natural number into a machine size number if it does not fit.");
320 }
321 if (m_number.size()==0)
322 {
323 return 0;
324 }
325 return m_number.front();
326 }
327
330 std::size_t size() const
331 {
332 return m_number.size();
333 }
334
337 std::size_t operator[](const std::size_t n) const
338 {
339 assert(n<m_number.size());
340 return m_number.at(n);
341 }
342
343 /* \brief Standard comparison operator.
344 */
345 bool operator==(const big_natural_number& other) const
346 {
348 other.is_well_defined();
349 return m_number==other.m_number;
350 }
351
352 /* \brief Standard comparison operator.
353 */
354 bool operator!=(const big_natural_number& other) const
355 {
356 return !this->operator==(other);
357 }
358
359 /* \brief Standard comparison operator.
360 */
361 bool operator<(const big_natural_number& other) const
362 {
364 other.is_well_defined();
365 if (m_number.size()<other.m_number.size())
366 {
367 return true;
368 }
369 if (m_number.size()>other.m_number.size())
370 {
371 return false;
372 }
373 assert(m_number.size()==other.m_number.size());
374 std::vector<std::size_t>::const_reverse_iterator j=other.m_number.rbegin();
375 for(std::vector<std::size_t>::const_reverse_iterator i=m_number.rbegin(); i!=m_number.rend(); ++i, ++j)
376 {
377 if (*i < *j)
378 {
379 return true;
380 }
381 if (*i > *j)
382 {
383 return false;
384 }
385 }
386 // The numbers are equal.
387 assert(m_number==other.m_number);
388 return false;
389 }
390
391 /* \brief Standard comparison operator.
392 */
393 bool operator<=(const big_natural_number& other) const
394 {
395 return !this->operator>(other);
396 }
397
398 /* \brief Standard comparison operator.
399 */
400 bool operator>(const big_natural_number& other) const
401 {
402 return other.operator<(*this);
403 }
404
405 /* \brief Standard comparison operator.
406 */
407 bool operator>=(const big_natural_number& other) const
408 {
409 return other.operator<=(*this);
410 }
411
412 /* Divide the current number by n. If there is a remainder return it. */
413 std::size_t divide_by(std::size_t n)
414 {
415 std::size_t remainder=0;
416 for(std::vector<std::size_t>::reverse_iterator i=m_number.rbegin(); i!=m_number.rend(); ++i)
417 {
418 *i=detail::divide_single_number(*i,n,remainder);
419 }
422 return remainder;
423 }
424
425 // Add the argument to this big natural number
426 void add(const big_natural_number& other)
427 {
429 other.is_well_defined();
430
431 // big_natural_number result;
432 // result.m_number.reserve((std::max)(m_number.size(),other.m_number.size()));
433 std::size_t carry=0;
434 for(std::size_t i=0; i < (std::max)(m_number.size(),other.m_number.size()); ++i)
435 {
436 if (i>=m_number.size())
437 {
438 m_number.push_back(detail::add_single_number(0,other.m_number[i],carry));
439 }
440 else if (i>=other.m_number.size())
441 {
443 }
444 else
445 {
447 }
448 }
449 if (carry>0)
450 {
451 m_number.push_back(carry);
452 }
454 }
455
456
457 /* \brief Standard addition operator.
458 */
460 {
462 other.is_well_defined();
463
464 big_natural_number result=*this;
465 result.add(other);
466 return result;
467 }
468
469 /* \brief Standard subtraction.
470 \detail Subtract other from this number. Throws an exception if
471 the result is negative and cannot be represented.
472 */
473 void subtract(const big_natural_number& other)
474 {
476 other.is_well_defined();
477
478 assert(m_number.size()==0 || m_number.back()!=0);
479 assert(other.m_number.size()==0 || other.m_number.back()!=0);
480 if (m_number.size()<other.m_number.size())
481 {
482 throw mcrl2::runtime_error("Subtracting numbers " + pp(*this) + " and " + pp(other) + " yields a non representable negative result (1).");
483 }
484 std::size_t carry=0;
485 for(std::size_t i=0; i<m_number.size(); ++i)
486 {
487 if (i>=other.m_number.size())
488 {
490 }
491 else
492 {
494 }
495 }
496 if (carry>0)
497 {
498 throw mcrl2::runtime_error("Subtracting numbers " + pp(*this) + " and " + pp(other) + " yields a non representable negative result (2).");
499 }
502 }
503
504 /* \brief Standard subtraction operator. Throws an exception if the result
505 * is negative and cannot be represented.
506 */
508 {
510 other.is_well_defined();
511 big_natural_number result=*this;
512 result.subtract(other);
513 return result;
514 }
515
516
517
518 /* \brief Efficient multiplication operator that does not declare auxiliary vectors.
519 \detail Initially result must be zero. At the end: result equals (*this)*other+result.
520 The calculation_buffer does not need to be initialised.
521 */
522 void multiply(const big_natural_number& other,
523 big_natural_number& result,
524 big_natural_number& calculation_buffer_for_multiplicand) const
525 {
527 other.is_well_defined();
528 std::size_t offset=0;
529 for(std::size_t digit: other.m_number)
530 {
531 // Move n2 to the multiplicand and multiply it with base^offset.
532 calculation_buffer_for_multiplicand.clear();
533 for(std::size_t i=0; i< offset; ++i) { calculation_buffer_for_multiplicand.m_number.push_back(0); }
534 for(std::size_t n: m_number)
535 {
536 calculation_buffer_for_multiplicand.m_number.push_back(n);
537 }
538
539 // Multiply the multiplicand with digit.
540 calculation_buffer_for_multiplicand.multiply_by(digit,0);
541 // Add the multiplicand to the result.
542 result.add(calculation_buffer_for_multiplicand);
543 offset++;
544 }
545 result.is_well_defined();
546 }
547
548 /* \brief Standard multiplication operator. This is not very efficient as it declares two temporary vectors.
549 */
551 {
552 big_natural_number result, buffer;
553 multiply(other,result,buffer);
554 return result;
555 }
556
557 // This is an auxiliary function getting the n-th digit,
558 // where digit 0 is the least significant one.
559 // It is not necessary that n is in range.
560 /* std::size_t getdigit(const std::size_t n) const
561 {
562 if (n>=m_number.size())
563 {
564 return 0;
565 }
566 return m_number[n];
567 } */
568
569 /* \brief Efficient divide operator that does not declare auxiliary vectors.
570 \detail Initially result must be zero. At the end: result equals (*this)*other+result.
571 The calculation_buffer does not need to be initialised.
572 The algorithm uses standard "primary school" division, except that
573 the digits in this case are 64 bits numbers. The calculation is tricky
574 as the most significant digit of this may be a remaining digit from
575 the previous calculation.
576 */
577 void div_mod(const big_natural_number& other,
578 big_natural_number& result,
579 big_natural_number& remainder,
580 big_natural_number& calculation_buffer_divisor) const
581 {
583 other.is_well_defined();
584 assert(!other.is_zero());
585
586 if (m_number.size()==1 && other.m_number.size()==1)
587 {
588 std::size_t n=m_number.front()/other.m_number.front(); // Calculate div.
589 if (n==0)
590 {
591 result.clear();
592 }
593 else
594 {
595 result.m_number.resize(1);
596 result.m_number[0]=n;
597 }
598 n=m_number.front() % other.m_number.front(); // Calculate mod.
599 if (n==0)
600 {
601 remainder.clear();
602 }
603 else
604 {
605 remainder.m_number.resize(1);
606 remainder.m_number[0]=n;
607 }
608 result.is_well_defined();
609 remainder.is_well_defined();
610 return;
611 }
612
613 // TODO: The procedure below works bitwise, as no efficient division algorithm has yet
614 // been implemented. A natural candidate is the algorithm in "Per Brinch Hansen, Multiple
615 // length division revisited: A tour of the minefield. Software practice and experience 24,
616 // 579-601, 1994.
617 result.clear();
618 remainder=*this;
619
620 if (m_number.size()<other.m_number.size())
621 {
622 result.is_well_defined();
623 remainder.is_well_defined();
624 return;
625 }
626 const int no_of_bits_per_digit=std::numeric_limits<std::size_t>::digits;
627
628 big_natural_number divisor;
629 calculation_buffer_divisor.clear();
630 for(std::size_t i=0; i< (1+m_number.size())-other.m_number.size(); ++i) { calculation_buffer_divisor.m_number.push_back(0); }
631
632 // Place 0 digits at least significant position of the calculation_buffer_divisor to make it of comparable length as the remainder.
633 for(std::size_t i: other.m_number)
634 {
635 calculation_buffer_divisor.m_number.push_back(i);
636 }
637 calculation_buffer_divisor.remove_significant_digits_that_are_zero();
638
639 for(std::size_t i=0; i<=no_of_bits_per_digit*(m_number.size()-other.m_number.size()+1); ++i)
640 {
641 if (remainder<calculation_buffer_divisor)
642 {
643 // We cannot subtract the calculation_buffer_divisor from the remainder.
644 result.multiply_by(2,0); // result=result*2
645 }
646 else
647 {
648 // We subtract the calculation_buffer_divisor from the remainder.
649 result.multiply_by(2,1); // result=result*2 + 1
650 remainder.subtract(calculation_buffer_divisor);
651 }
652 calculation_buffer_divisor.divide_by(2); // Shift the calculation_buffer_divisor one bit to the left.
653 }
654
656 result.is_well_defined();
657 remainder.is_well_defined();
658 }
659
660 /* void div_mod(const big_natural_number& other,
661 big_natural_number& result,
662 big_natural_number& remainder,
663 big_natural_number& calculation_buffer_subtractor) const
664 {
665 is_well_defined();
666 other.is_well_defined();
667 assert(!other.is_zero());
668
669 result.clear();
670 remainder=*this;
671
672 if (m_number.size()<other.m_number.size())
673 {
674 return;
675 }
676this->print_number("div_mod: this: ");
677other.print_number("div_mod: other: ");
678 std::size_t remaining_digit=0;
679 for(std::size_t n=remainder.m_number.size()-1; n>=other.m_number.size(); n--)
680 {
681std::cerr << "Wat is n " << n << "\n";
682 std::size_t r=remainder.getdigit(n+1);
683 std::size_t divisor=detail::divide_single_number(
684 remainder.getdigit(n),
685 other.m_number.back(),
686 r);
687
688result.print_number("div_mod: result: ");
689remainder.print_number("div_mod: remainder: ");
690std::cerr << "dmwhile: divisor: " << divisor <<"\n";
691calculation_buffer_subtractor.is_well_defined();
692 calculation_buffer_subtractor.m_number=std::vector<std::size_t>(n-other.m_number.size(),0); Inefficient, want constructie
693 for(std::size_t i: other.m_number)
694 {
695 calculation_buffer_subtractor.m_number.push_back(i);
696 }
697 calculation_buffer_subtractor.multiply_by(divisor,0);
698calculation_buffer_subtractor.print_number("div_mod: subtractor: ");
699 if (remainder<calculation_buffer_subtractor)
700 {
701 divisor=divisor-1;
702std::cerr << "dmwhile: divisor adapted: " << divisor <<"\n";
703 calculation_buffer_subtractor.m_number=std::vector<std::size_t>(n-other.m_number.size(),0);
704 for(std::size_t i: other.m_number)
705 {
706 calculation_buffer_subtractor.m_number.push_back(i);
707 }
708 calculation_buffer_subtractor.multiply_by(divisor,0);
709 }
710 result.m_number.push_back(divisor);
711remainder.print_number("remainder before assert");
712calculation_buffer_subtractor.print_number("subtractor before assert");
713 assert(remainder>=calculation_buffer_subtractor);
714 std::size_t old_remainder_size=remainder.m_number.size();
715 remainder.subtract(calculation_buffer_subtractor);
716 remaining_digit=(remaining_digit?
717 remainder.m_number.size()+1==old_remainder_size:
718 remainder.m_number.size()==old_remainder_size);
719 }
720result.print_number("div_mod: result voor swap: ");
721 if (result.m_number.size()==0)
722 {
723 return;
724 }
725 // Result must be reverted.
726 std::size_t begin = 0;
727 std::size_t end = result.m_number.size()-1;
728 while (begin<end)
729 {
730 std::swap(result.m_number[begin],result.m_number[end]);
731 begin++;
732 end--;
733 }
734 result.remove_significant_digits_that_are_zero();
735result.print_number("div_mod: result na swap: ");
736 result.is_well_defined();
737 remainder.is_well_defined();
738 } */
739
740 /* \brief Standard division operator. This is currently implemented by a bit wise subtraction. Can be optimized by a 64 bit calculation.
741 \detail. This routine is not particularly efficient as it declares three temporary vectors.
742 */
744 {
745 // Division by zero is not allowed.
746 if (other.is_zero())
747 {
748 throw mcrl2::runtime_error("Division by zero.");
749 }
750 // Zero divided by something is zero.
751 if (is_zero())
752 {
753 return *this;
754 }
755
756 // Often numbers only consist of one digit. Deal with this using machine division.
757 if (m_number.size()==1 && other.m_number.size()==1)
758 {
759 return big_natural_number(m_number.front()/other.m_number.front());
760 }
761
762 // Otherwise do a multiple digit division.
763 big_natural_number result, remainder, buffer;
764 div_mod(other,result,remainder,buffer);
765 return result;
766 }
767
768 /* \brief Standard modulo operator. This is currently implemented by a bit wise subtraction. Can be optimized by a 64 bit calculation.
769 \detail. This routine is not particularly efficient as it declares three temporary vectors.
770 */
772 {
773 // Modulo zero is yields the value itself.
774 // Zero modulo something is zero.
775 if (other.is_zero() || is_zero())
776 {
777 return *this;
778 }
779
780 // Often numbers only consist of one digit. Deal with this using machine division.
781 if (m_number.size()==1 && other.m_number.size()==1)
782 {
783 return big_natural_number(m_number.front()%other.m_number.front());
784 }
785
786 big_natural_number result, remainder, buffer;
787 div_mod(other,result,remainder,buffer);
788 return remainder;
789
790 }
791};
792
793inline std::ostream& operator<<(std::ostream& ss, const big_natural_number& l)
794{
795 static big_natural_number n; // This code is not re-entrant, but it avoids declaring a vector continuously.
796 n=l;
797 std::string s; // This string contains the number in reverse ordering.
798 for( ; !n.is_zero() ; )
799 {
800 std::size_t remainder = n.divide_by(10); /* This divides n by 10. */
801 s.push_back(static_cast<char>('0'+remainder));
802 }
803 if (s.empty())
804 {
805 ss << "0";
806 }
807 else
808 {
809 for(std::string::const_reverse_iterator i=s.rbegin(); i!=s.rend(); ++i)
810 {
811 ss << *i;
812 }
813 }
814 return ss;
815}
816
817
821{
822 x.m_number.swap(y.m_number);
823}
824
825} // namespace utilities
826} // namespace mcrl2
827
828namespace std
829{
830
831template <>
832struct hash< mcrl2::utilities::big_natural_number >
833{
835 {
836 hash<std::vector<std::size_t> > hasher;
837 return hasher(n.m_number);
838 }
839};
840
841
842} // namespace std
843
844namespace mcrl2
845{
846namespace utilities
847{
848/* \brief A pretty print operator on action labels, returning it as a string.
849*/
850inline std::string pp(const big_natural_number& l)
851{
852 std::stringstream s;
853 s << l;
854 return s.str();
855}
856} // namespace utilities
857} // namespace mcrl2
858
859
860#endif // MCRL2_UTILITIES_BIG_NUMBERS_H
861
862
Standard exception class for reporting runtime errors.
Definition exception.h:27
void div_mod(const big_natural_number &other, big_natural_number &result, big_natural_number &remainder, big_natural_number &calculation_buffer_divisor) const
bool is_number(std::size_t n) const
Returns whether this number equals a number of std::size_t.
big_natural_number(const std::size_t n)
big_natural_number operator*(const big_natural_number &other) const
big_natural_number(const std::string &s)
bool operator>=(const big_natural_number &other) const
void print_number(const std::string &s) const
std::size_t operator[](const std::size_t n) const
Give the n-th digit where the most significant digit is positioned last.
void add(const big_natural_number &other)
std::vector< std::size_t > m_number
big_natural_number operator+(const big_natural_number &other) const
bool operator==(const big_natural_number &other) const
std::size_t divide_by(std::size_t n)
big_natural_number operator%(const big_natural_number &other) const
std::size_t size() const
Give the number of digits in this big number.
big_natural_number operator-(const big_natural_number &other) const
friend void swap(big_natural_number &x, big_natural_number &y)
Standard overload of swap.
bool operator<=(const big_natural_number &other) const
big_natural_number operator/(const big_natural_number &other) const
void clear()
Sets the number to zero.
bool operator!=(const big_natural_number &other) const
bool is_zero() const
Returns whether this number equals zero.
void multiply(const big_natural_number &other, big_natural_number &result, big_natural_number &calculation_buffer_for_multiplicand) const
void push_back(const std::size_t n)
bool operator<(const big_natural_number &other) const
void subtract(const big_natural_number &other)
bool operator>(const big_natural_number &other) const
void multiply_by(std::size_t n, std::size_t carry)
Exception classes for use in libraries and tools.
This file contains a specialisation for hashes on pairs. This is not a part of the standard,...
void remove_common_divisor(std::size_t &p, std::size_t &q)
std::size_t multiply_single_number(const std::size_t n1, const std::size_t n2, std::size_t &multiplication_carry)
Definition big_numbers.h:95
std::size_t divide_single_number(const std::size_t p, const std::size_t q, std::size_t &remainder)
std::size_t add_single_number(const std::size_t n1, const std::size_t n2, std::size_t &carry)
Definition big_numbers.h:49
std::size_t greatest_common_divisor(std::size_t p, std::size_t q)
std::size_t subtract_single_number(const std::size_t n1, const std::size_t n2, std::size_t &carry)
Definition big_numbers.h:72
void swap(big_natural_number &x, big_natural_number &y)
Standard overload of swap.
std::string pp(const big_natural_number &l)
std::ostream & operator<<(std::ostream &ss, const big_natural_number &l)
A class that takes a linear process specification and checks all tau-summands of that LPS for conflue...
Definition indexed_set.h:72
STL namespace.
void swap(atermpp::unprotected_aterm_core &t1, atermpp::unprotected_aterm_core &t2) noexcept
Swaps two aterms.
Definition aterm.h:462
std::size_t operator()(const mcrl2::utilities::big_natural_number &n) const
#define hash(l, r, m)
Definition tree_set.cpp:23