18#ifndef MCRL2_UTILITIES_BIG_NUMBERS_H
19#define MCRL2_UTILITIES_BIG_NUMBERS_H
32class big_natural_number;
34inline std::string
pp(
const big_natural_number& l);
49 inline std::size_t
add_single_number(
const std::size_t n1,
const std::size_t n2, std::size_t& carry)
52 std::size_t result=n1+n2+carry;
75 std::size_t result=n1-n2-carry;
95 inline std::size_t
multiply_single_number(
const std::size_t n1,
const std::size_t n2, std::size_t& multiplication_carry)
98 const int no_of_bits_per_digit=std::numeric_limits<std::size_t>::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);
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;
111 result=
add_single_number(result,((n1ms*n2ls)<<(no_of_bits_per_digit/2)),local_carry);
112 cumulative_carry=cumulative_carry+local_carry;
114 result=
add_single_number(result,((n1ls*n2ms)<<(no_of_bits_per_digit/2)),local_carry);
115 cumulative_carry=cumulative_carry+local_carry;
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;
131 const int no_of_bits_per_digit=std::numeric_limits<std::size_t>::digits;
135 std::size_t pms = (p >> (no_of_bits_per_digit/2)) + (remainder << (no_of_bits_per_digit/2));
138 std::size_t resultms = pms/q;
139 assert((resultms >> (no_of_bits_per_digit/2)) == 0);
140 std::size_t remainderms = pms%q;
143 std::size_t pls = (p & ((1LL<<(no_of_bits_per_digit/2))-1)) + (remainderms << (no_of_bits_per_digit/2));
146 std::size_t resultls = pls/q;
148 assert((resultls >> (no_of_bits_per_digit/2)) == 0);
150 return resultls + (resultms << (no_of_bits_per_digit/2));
156 if (p==0) {
return q; }
157 if (q==0) {
return p; }
163 std::size_t remainder=p % q;
184inline std::string
pp(
const big_natural_number& l);
188 friend std::hash<big_natural_number>;
233 std::cerr << s <<
" " <<
m_number.size() <<
"\n";
236 std::cerr << i <<
" ";
238 std::cerr <<
"\n---------------------\n";
264 throw mcrl2::runtime_error(
"Number " + s +
" contains symbol '" + c +
"' which is not a digit.");
314 explicit operator std::size_t()
const
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.");
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)
402 return other.operator<(*this);
409 return other.operator<=(*this);
415 std::size_t remainder=0;
416 for(std::vector<std::size_t>::reverse_iterator i=
m_number.rbegin(); i!=
m_number.rend(); ++i)
434 for(std::size_t i=0; i < (std::max)(
m_number.size(),other.
m_number.size()); ++i)
482 throw mcrl2::runtime_error(
"Subtracting numbers " +
pp(*
this) +
" and " +
pp(other) +
" yields a non representable negative result (1).");
485 for(std::size_t i=0; i<
m_number.size(); ++i)
498 throw mcrl2::runtime_error(
"Subtracting numbers " +
pp(*
this) +
" and " +
pp(other) +
" yields a non representable negative result (2).");
528 std::size_t offset=0;
529 for(std::size_t digit: other.
m_number)
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); }
536 calculation_buffer_for_multiplicand.
m_number.push_back(n);
540 calculation_buffer_for_multiplicand.
multiply_by(digit,0);
542 result.
add(calculation_buffer_for_multiplicand);
626 const int no_of_bits_per_digit=std::numeric_limits<std::size_t>::digits;
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); }
635 calculation_buffer_divisor.
m_number.push_back(i);
639 for(std::size_t i=0; i<=no_of_bits_per_digit*(
m_number.size()-other.
m_number.size()+1); ++i)
641 if (remainder<calculation_buffer_divisor)
650 remainder.
subtract(calculation_buffer_divisor);
764 div_mod(other,result,remainder,buffer);
787 div_mod(other,result,remainder,buffer);
801 s.push_back(
static_cast<char>(
'0'+remainder));
809 for(std::string::const_reverse_iterator i=s.rbegin(); i!=s.rend(); ++i)
836 hash<std::vector<std::size_t> > hasher;
Standard exception class for reporting runtime errors.
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 is_well_defined() 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.
void remove_significant_digits_that_are_zero()
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)
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)
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)
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...
void swap(atermpp::unprotected_aterm_core &t1, atermpp::unprotected_aterm_core &t2) noexcept
Swaps two aterms.
std::size_t operator()(const mcrl2::utilities::big_natural_number &n) const