Line data Source code
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 :
10 : /** \file
11 : *
12 : * \brief This file contains a class big_natural_number that stores big positive numbers of arbitrary size.
13 : * It has all common operations that one can expect on big numbers.
14 : * \author Jan Friso Groote
15 : */
16 :
17 :
18 : #ifndef MCRL2_UTILITIES_BIG_NUMBERS_H
19 : #define MCRL2_UTILITIES_BIG_NUMBERS_H
20 :
21 : #include "mcrl2/utilities/exception.h"
22 : #include "mcrl2/utilities/hash_utility.h"
23 : #include <algorithm>
24 : #include <limits>
25 : #include <string>
26 :
27 : // Prototype.
28 : namespace mcrl2
29 : {
30 : namespace utilities
31 : {
32 : class big_natural_number;
33 :
34 : inline std::string pp(const big_natural_number& l);
35 :
36 : } // namespace utilities
37 : } // namespace mcrl2
38 :
39 :
40 : namespace mcrl2
41 : {
42 : namespace utilities
43 : {
44 : namespace 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 1681404 : inline std::size_t add_single_number(const std::size_t n1, const std::size_t n2, std::size_t& carry)
50 : {
51 1681404 : assert(carry<=1);
52 1681404 : std::size_t result=n1+n2+carry;
53 1681404 : if (carry==0)
54 : {
55 1673731 : if (result<n1)
56 : {
57 20288 : carry=1;
58 : }
59 : }
60 : else // carry==1
61 : {
62 7673 : if (result>n1)
63 : {
64 4155 : carry=0;
65 : }
66 : }
67 1681404 : 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 384604 : inline std::size_t subtract_single_number(const std::size_t n1, const std::size_t n2, std::size_t& carry)
73 : {
74 384604 : assert(carry<=1);
75 384604 : std::size_t result=n1-n2-carry;
76 384604 : if (carry==0)
77 : {
78 284341 : if (result>n1)
79 : {
80 55249 : carry=1;
81 : }
82 : }
83 : else // carry==1
84 : {
85 100263 : if (result<n1)
86 : {
87 55249 : carry=0;
88 : }
89 : }
90 384604 : 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 534105 : 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 534105 : 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 534105 : std::size_t n1ls = n1 & ((1LL<<(no_of_bits_per_digit/2))-1);
102 534105 : std::size_t n1ms = n1 >> (no_of_bits_per_digit/2);
103 534105 : std::size_t n2ls = n2 & ((1LL<<(no_of_bits_per_digit/2))-1);
104 534105 : 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 534105 : std::size_t local_carry=0;
108 534105 : std::size_t result = add_single_number(n1ls*n2ls,multiplication_carry,local_carry);
109 534105 : std::size_t cumulative_carry=local_carry;
110 534105 : local_carry=0;
111 534105 : result=add_single_number(result,((n1ms*n2ls)<<(no_of_bits_per_digit/2)),local_carry);
112 534105 : cumulative_carry=cumulative_carry+local_carry;
113 534105 : local_carry=0;
114 534105 : result=add_single_number(result,((n1ls*n2ms)<<(no_of_bits_per_digit/2)),local_carry);
115 534105 : cumulative_carry=cumulative_carry+local_carry;
116 :
117 : // Now calculate the result of the most significant no_of_bits_per_digit.
118 534105 : multiplication_carry=cumulative_carry;
119 534105 : multiplication_carry=multiplication_carry+((n1ms*n2ls)>>(no_of_bits_per_digit/2));
120 534105 : multiplication_carry=multiplication_carry+((n1ls*n2ms)>>(no_of_bits_per_digit/2));
121 534105 : multiplication_carry=multiplication_carry+n1ms*n2ms;
122 :
123 534105 : 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 7562256 : inline std::size_t divide_single_number(const std::size_t p, const std::size_t q, std::size_t& remainder)
129 : {
130 7562256 : assert(q>remainder);
131 7562256 : 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 7562256 : 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 7562256 : std::size_t resultms = pms/q;
139 7562256 : assert((resultms >> (no_of_bits_per_digit/2)) == 0);
140 7562256 : std::size_t remainderms = pms%q;
141 :
142 : // Now obtain the least significant part.
143 7562256 : 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 7562256 : std::size_t resultls = pls/q;
147 7562256 : remainder = pls%q;
148 7562256 : assert((resultls >> (no_of_bits_per_digit/2)) == 0);
149 :
150 7562256 : return resultls + (resultms << (no_of_bits_per_digit/2));
151 : }
152 : } // namespace detail
153 :
154 : class big_natural_number;
155 : inline std::string pp(const big_natural_number& l);
156 :
157 : class big_natural_number
158 : {
159 : friend std::hash<big_natural_number>;
160 : friend inline void swap(big_natural_number& x, big_natural_number& y);
161 :
162 : protected:
163 : // Numbers are stored as std::size_t words, with the most significant number last.
164 : // Note that the number representation is not unique. Numbers have no trailing
165 : // zero's, i.e., this->back()!=0 (if this->size()>0). Therefore their representation is unique.
166 : std::vector<std::size_t> m_number;
167 :
168 : /* Multiply the current number by n and add the carry */
169 800284 : void multiply_by(std::size_t n, std::size_t carry)
170 : {
171 1334389 : for(std::size_t& i: m_number)
172 : {
173 534105 : i=detail::multiply_single_number(i,n,carry);
174 : }
175 800284 : if (carry)
176 : {
177 : /* Add an extra digit with the carry */
178 15399 : m_number.push_back(carry);
179 : }
180 800284 : remove_significant_digits_that_are_zero();
181 800284 : is_well_defined();
182 800284 : }
183 :
184 : // Remove zero's at the end of m_number vector that are
185 : // leading and irrelevant zero's in the number representation.
186 1605650 : void remove_significant_digits_that_are_zero()
187 : {
188 1620884 : for( ; m_number.size()>0 && m_number.back()==0 ; )
189 : {
190 15234 : m_number.pop_back();
191 : }
192 1605650 : }
193 :
194 : // Check that the number is well defined, in the sense
195 : // that there are no most significant digits that are zero.
196 4001326 : void is_well_defined() const
197 : {
198 4001326 : assert(m_number.size()==0 || m_number.back()!=0);
199 4001326 : }
200 :
201 : // \brief This functions prints a number in internal represenation. This function is useful and only meant for debugging.
202 : void print_number(const std::string& s) const
203 : {
204 : std::cerr << s << " " << m_number.size() << "\n";
205 : for(std::size_t i: m_number)
206 : {
207 : std::cerr << i << " ";
208 : }
209 : std::cerr << "\n---------------------\n";
210 : }
211 :
212 : public:
213 : // Default constructor. The value is 0 by default.
214 12928 : explicit big_natural_number()
215 12928 : {
216 12928 : }
217 :
218 : // Constructor based on a std::size_t. The value of the number will be n.
219 1961 : explicit big_natural_number(const std::size_t n)
220 1961 : {
221 1961 : if (n>0)
222 : {
223 1952 : m_number.push_back(n);
224 : }
225 1961 : is_well_defined();
226 1961 : }
227 :
228 : // Constructor based on a string. The string is a digital number.
229 2388 : big_natural_number(const std::string& s)
230 2388 : {
231 23974 : for(char c: s)
232 : {
233 21586 : if (!isdigit(c))
234 : {
235 0 : throw mcrl2::runtime_error("Number " + s + " contains symbol '" + c + "' which is not a digit.");
236 : }
237 21586 : if (c>='0')
238 : {
239 21586 : multiply_by(10,std::size_t(c-'0'));
240 : }
241 : }
242 2388 : is_well_defined();
243 2388 : }
244 :
245 : /** \brief Returns whether this number equals zero.
246 : \details This is more efficient than checking x==big_natural_number(0).
247 : */
248 125858 : bool is_zero() const
249 : {
250 125858 : is_well_defined();
251 125858 : return m_number.size()==0;
252 : }
253 :
254 : /** \brief Returns whether this number equals a number of std::size_t.
255 : \details This is more efficient than checking x==big_natural_number(1).
256 : */
257 6696 : bool is_number(std::size_t n) const
258 : {
259 6696 : is_well_defined();
260 6696 : if (n==0)
261 : {
262 0 : return m_number.size()==0;
263 : }
264 6696 : return m_number.size()==1 && m_number.front()==n;
265 : }
266 :
267 : /** \brief Sets the number to zero.
268 : \details This is more efficient than using an assignment x=0.
269 : */
270 161915 : void clear()
271 : {
272 161915 : is_well_defined();
273 161915 : m_number.clear();
274 161915 : }
275 :
276 : /** \brief Transforms this number to a std::size_t, provided it is sufficiently small.
277 : If not an mcrl2::runtime_error is thrown.
278 : */
279 : explicit operator std::size_t() const
280 : {
281 : is_well_defined();
282 : if (m_number.size()>1)
283 : {
284 : throw mcrl2::runtime_error("It is not possible to transform a big natural number into a machine size number if it does not fit.");
285 : }
286 : if (m_number.size()==0)
287 : {
288 : return 0;
289 : }
290 : return m_number.front();
291 : }
292 :
293 : /* \brief Standard comparison operator.
294 : */
295 5077 : bool operator==(const big_natural_number& other) const
296 : {
297 5077 : is_well_defined();
298 5077 : other.is_well_defined();
299 5077 : return m_number==other.m_number;
300 : }
301 :
302 : /* \brief Standard comparison operator.
303 : */
304 : bool operator!=(const big_natural_number& other) const
305 : {
306 : return !this->operator==(other);
307 : }
308 :
309 : /* \brief Standard comparison operator.
310 : */
311 755119 : bool operator<(const big_natural_number& other) const
312 : {
313 755119 : is_well_defined();
314 755119 : other.is_well_defined();
315 755119 : if (m_number.size()<other.m_number.size())
316 : {
317 328551 : return true;
318 : }
319 426568 : if (m_number.size()>other.m_number.size())
320 : {
321 439 : return false;
322 : }
323 426129 : assert(m_number.size()==other.m_number.size());
324 426129 : std::vector<std::size_t>::const_reverse_iterator j=other.m_number.rbegin();
325 434316 : for(std::vector<std::size_t>::const_reverse_iterator i=m_number.rbegin(); i!=m_number.rend(); ++i, ++j)
326 : {
327 426041 : if (*i < *j)
328 : {
329 417854 : return true;
330 : }
331 62234 : if (*i > *j)
332 : {
333 54047 : return false;
334 : }
335 : }
336 : // The numbers are equal.
337 8275 : assert(m_number==other.m_number);
338 8275 : return false;
339 : }
340 :
341 : /* \brief Standard comparison operator.
342 : */
343 7812 : bool operator<=(const big_natural_number& other) const
344 : {
345 7812 : return !this->operator>(other);
346 : }
347 :
348 : /* \brief Standard comparison operator.
349 : */
350 21240 : bool operator>(const big_natural_number& other) const
351 : {
352 21240 : return other.operator<(*this);
353 : }
354 :
355 : /* \brief Standard comparison operator.
356 : */
357 22 : bool operator>=(const big_natural_number& other) const
358 : {
359 22 : return other.operator<=(*this);
360 : }
361 :
362 : /* Divide the current number by n. If there is a remainder return it. */
363 750251 : std::size_t divide_by(std::size_t n)
364 : {
365 750251 : std::size_t remainder=0;
366 8312507 : for(std::vector<std::size_t>::reverse_iterator i=m_number.rbegin(); i!=m_number.rend(); ++i)
367 : {
368 7562256 : *i=detail::divide_single_number(*i,n,remainder);
369 : }
370 750251 : remove_significant_digits_that_are_zero();
371 750251 : is_well_defined();
372 750251 : return remainder;
373 : }
374 :
375 : // Add the argument to this big natural number
376 64076 : void add(const big_natural_number& other)
377 : {
378 64076 : is_well_defined();
379 64076 : other.is_well_defined();
380 :
381 : // big_natural_number result;
382 : // result.m_number.reserve((std::max)(m_number.size(),other.m_number.size()));
383 64076 : std::size_t carry=0;
384 143165 : for(std::size_t i=0; i < (std::max)(m_number.size(),other.m_number.size()); ++i)
385 : {
386 79089 : if (i>=m_number.size())
387 : {
388 49376 : m_number.push_back(detail::add_single_number(0,other.m_number[i],carry));
389 : }
390 29713 : else if (i>=other.m_number.size())
391 : {
392 182 : m_number[i]=detail::add_single_number(m_number[i],0,carry);
393 : }
394 : else
395 : {
396 29531 : m_number[i]=detail::add_single_number(m_number[i],other.m_number[i],carry);
397 : }
398 : }
399 64076 : if (carry>0)
400 : {
401 0 : m_number.push_back(carry);
402 : }
403 64076 : is_well_defined();
404 64076 : }
405 :
406 :
407 : /* \brief Standard addition operator.
408 : */
409 146 : big_natural_number operator+(const big_natural_number& other) const
410 : {
411 146 : is_well_defined();
412 146 : other.is_well_defined();
413 :
414 146 : big_natural_number result=*this;
415 146 : result.add(other);
416 146 : return result;
417 0 : }
418 :
419 : /* \brief Standard subtraction.
420 : \detail Subtract other from this number. Throws an exception if
421 : the result is negative and cannot be represented.
422 : */
423 34653 : void subtract(const big_natural_number& other)
424 : {
425 34653 : is_well_defined();
426 34653 : other.is_well_defined();
427 :
428 34653 : assert(m_number.size()==0 || m_number.back()!=0);
429 34653 : assert(other.m_number.size()==0 || other.m_number.back()!=0);
430 34653 : if (m_number.size()<other.m_number.size())
431 : {
432 0 : throw mcrl2::runtime_error("Subtracting numbers " + pp(*this) + " and " + pp(other) + " yields a non representable negative result (1).");
433 : }
434 34653 : std::size_t carry=0;
435 419257 : for(std::size_t i=0; i<m_number.size(); ++i)
436 : {
437 384604 : if (i>=other.m_number.size())
438 : {
439 488 : m_number[i]=detail::subtract_single_number(m_number[i],0,carry);
440 : }
441 : else
442 : {
443 384116 : m_number[i]=detail::subtract_single_number(m_number[i],other.m_number[i],carry);
444 : }
445 : }
446 34653 : if (carry>0)
447 : {
448 0 : throw mcrl2::runtime_error("Subtracting numbers " + pp(*this) + " and " + pp(other) + " yields a non representable negative result (2).");
449 : }
450 34653 : remove_significant_digits_that_are_zero();
451 34653 : is_well_defined();
452 34653 : }
453 :
454 : /* \brief Standard subtraction operator. Throws an exception if the result
455 : * is negative and cannot be represented.
456 : */
457 133 : big_natural_number operator-(const big_natural_number& other) const
458 : {
459 133 : is_well_defined();
460 133 : other.is_well_defined();
461 133 : big_natural_number result=*this;
462 133 : result.subtract(other);
463 133 : return result;
464 0 : }
465 :
466 :
467 :
468 : /* \brief Efficient multiplication operator that does not declare auxiliary vectors.
469 : \detail Initially result must be zero. At the end: result equals (*this)*other+result.
470 : The calculation_buffer does not need to be initialised.
471 : */
472 56852 : void multiply(const big_natural_number& other,
473 : big_natural_number& result,
474 : big_natural_number& calculation_buffer_for_multiplicand) const
475 : {
476 56852 : is_well_defined();
477 56852 : other.is_well_defined();
478 56852 : std::size_t offset=0;
479 114983 : for(std::size_t digit: other.m_number)
480 : {
481 : // Move n2 to the multiplicand and multiply it with base^offset.
482 58131 : calculation_buffer_for_multiplicand.clear();
483 67387 : for(std::size_t i=0; i< offset; ++i) { calculation_buffer_for_multiplicand.m_number.push_back(0); }
484 120244 : for(std::size_t n: m_number)
485 : {
486 62113 : calculation_buffer_for_multiplicand.m_number.push_back(n);
487 : }
488 :
489 : // Multiply the multiplicand with digit.
490 58131 : calculation_buffer_for_multiplicand.multiply_by(digit,0);
491 : // Add the multiplicand to the result.
492 58131 : result.add(calculation_buffer_for_multiplicand);
493 58131 : offset++;
494 : }
495 56852 : result.is_well_defined();
496 56852 : }
497 :
498 : /* \brief Standard multiplication operator. This is not very efficient as it declares two temporary vectors.
499 : */
500 263 : big_natural_number operator*(const big_natural_number& other) const
501 : {
502 263 : big_natural_number result, buffer;
503 263 : multiply(other,result,buffer);
504 526 : return result;
505 263 : }
506 :
507 : // This is an auxiliary function getting the n-th digit,
508 : // where digit 0 is the least significant one.
509 : // It is not necessary that n is in range.
510 : /* std::size_t getdigit(const std::size_t n) const
511 : {
512 : if (n>=m_number.size())
513 : {
514 : return 0;
515 : }
516 : return m_number[n];
517 : } */
518 :
519 : /* \brief Efficient divide operator that does not declare auxiliary vectors.
520 : \detail Initially result must be zero. At the end: result equals (*this)*other+result.
521 : The calculation_buffer does not need to be initialised.
522 : The algorithm uses standard "primary school" division, except that
523 : the digits in this case are 64 bits numbers. The calculation is tricky
524 : as the most significant digit of this may be a remaining digit from
525 : the previous calculation.
526 : */
527 41070 : void div_mod(const big_natural_number& other,
528 : big_natural_number& result,
529 : big_natural_number& remainder,
530 : big_natural_number& calculation_buffer_divisor) const
531 : {
532 41070 : is_well_defined();
533 41070 : other.is_well_defined();
534 41070 : assert(!other.is_zero());
535 :
536 41070 : if (m_number.size()==1 && other.m_number.size()==1)
537 : {
538 30803 : std::size_t n=m_number.front()/other.m_number.front(); // Calculate div.
539 30803 : if (n==0)
540 : {
541 0 : result.clear();
542 : }
543 : else
544 : {
545 30803 : result.m_number.resize(1);
546 30803 : result.m_number[0]=n;
547 : }
548 30803 : n=m_number.front() % other.m_number.front(); // Calculate mod.
549 30803 : if (n==0)
550 : {
551 26697 : remainder.clear();
552 : }
553 : else
554 : {
555 4106 : remainder.m_number.resize(1);
556 4106 : remainder.m_number[0]=n;
557 : }
558 30803 : result.is_well_defined();
559 30803 : remainder.is_well_defined();
560 30839 : return;
561 : }
562 :
563 : // TODO: The procedure below works bitwise, as no efficient division algorithm has yet
564 : // been implemented. A natural candidate is the algorithm in "Per Brinch Hansen, Multiple
565 : // length division revisited: A tour of the minefield. Software practice and experience 24,
566 : // 579-601, 1994.
567 10267 : result.clear();
568 10267 : remainder=*this;
569 :
570 10267 : if (m_number.size()<other.m_number.size())
571 : {
572 36 : result.is_well_defined();
573 36 : remainder.is_well_defined();
574 36 : return;
575 : }
576 10231 : const int no_of_bits_per_digit=std::numeric_limits<std::size_t>::digits;
577 :
578 10231 : big_natural_number divisor;
579 10231 : calculation_buffer_divisor.clear();
580 21330 : for(std::size_t i=0; i< (1+m_number.size())-other.m_number.size(); ++i) { calculation_buffer_divisor.m_number.push_back(0); }
581 :
582 : // Place 0 digits at least significant position of the calculation_buffer_divisor to make it of comparable length as the remainder.
583 106316 : for(std::size_t i: other.m_number)
584 : {
585 96085 : calculation_buffer_divisor.m_number.push_back(i);
586 : }
587 10231 : calculation_buffer_divisor.remove_significant_digits_that_are_zero();
588 :
589 730798 : for(std::size_t i=0; i<=no_of_bits_per_digit*(m_number.size()-other.m_number.size()+1); ++i)
590 : {
591 720567 : if (remainder<calculation_buffer_divisor)
592 : {
593 : // We cannot subtract the calculation_buffer_divisor from the remainder.
594 686909 : result.multiply_by(2,0); // result=result*2
595 : }
596 : else
597 : {
598 : // We subtract the calculation_buffer_divisor from the remainder.
599 33658 : result.multiply_by(2,1); // result=result*2 + 1
600 33658 : remainder.subtract(calculation_buffer_divisor);
601 : }
602 720567 : calculation_buffer_divisor.divide_by(2); // Shift the calculation_buffer_divisor one bit to the left.
603 : }
604 :
605 10231 : result.remove_significant_digits_that_are_zero();
606 10231 : result.is_well_defined();
607 10231 : remainder.is_well_defined();
608 10231 : }
609 :
610 : /* void div_mod(const big_natural_number& other,
611 : big_natural_number& result,
612 : big_natural_number& remainder,
613 : big_natural_number& calculation_buffer_subtractor) const
614 : {
615 : is_well_defined();
616 : other.is_well_defined();
617 : assert(!other.is_zero());
618 :
619 : result.clear();
620 : remainder=*this;
621 :
622 : if (m_number.size()<other.m_number.size())
623 : {
624 : return;
625 : }
626 : this->print_number("div_mod: this: ");
627 : other.print_number("div_mod: other: ");
628 : std::size_t remaining_digit=0;
629 : for(std::size_t n=remainder.m_number.size()-1; n>=other.m_number.size(); n--)
630 : {
631 : std::cerr << "Wat is n " << n << "\n";
632 : std::size_t r=remainder.getdigit(n+1);
633 : std::size_t divisor=detail::divide_single_number(
634 : remainder.getdigit(n),
635 : other.m_number.back(),
636 : r);
637 :
638 : result.print_number("div_mod: result: ");
639 : remainder.print_number("div_mod: remainder: ");
640 : std::cerr << "dmwhile: divisor: " << divisor <<"\n";
641 : calculation_buffer_subtractor.is_well_defined();
642 : calculation_buffer_subtractor.m_number=std::vector<std::size_t>(n-other.m_number.size(),0); Inefficient, want constructie
643 : for(std::size_t i: other.m_number)
644 : {
645 : calculation_buffer_subtractor.m_number.push_back(i);
646 : }
647 : calculation_buffer_subtractor.multiply_by(divisor,0);
648 : calculation_buffer_subtractor.print_number("div_mod: subtractor: ");
649 : if (remainder<calculation_buffer_subtractor)
650 : {
651 : divisor=divisor-1;
652 : std::cerr << "dmwhile: divisor adapted: " << divisor <<"\n";
653 : calculation_buffer_subtractor.m_number=std::vector<std::size_t>(n-other.m_number.size(),0);
654 : for(std::size_t i: other.m_number)
655 : {
656 : calculation_buffer_subtractor.m_number.push_back(i);
657 : }
658 : calculation_buffer_subtractor.multiply_by(divisor,0);
659 : }
660 : result.m_number.push_back(divisor);
661 : remainder.print_number("remainder before assert");
662 : calculation_buffer_subtractor.print_number("subtractor before assert");
663 : assert(remainder>=calculation_buffer_subtractor);
664 : std::size_t old_remainder_size=remainder.m_number.size();
665 : remainder.subtract(calculation_buffer_subtractor);
666 : remaining_digit=(remaining_digit?
667 : remainder.m_number.size()+1==old_remainder_size:
668 : remainder.m_number.size()==old_remainder_size);
669 : }
670 : result.print_number("div_mod: result voor swap: ");
671 : if (result.m_number.size()==0)
672 : {
673 : return;
674 : }
675 : // Result must be reverted.
676 : std::size_t begin = 0;
677 : std::size_t end = result.m_number.size()-1;
678 : while (begin<end)
679 : {
680 : std::swap(result.m_number[begin],result.m_number[end]);
681 : begin++;
682 : end--;
683 : }
684 : result.remove_significant_digits_that_are_zero();
685 : result.print_number("div_mod: result na swap: ");
686 : result.is_well_defined();
687 : remainder.is_well_defined();
688 : } */
689 :
690 : /* \brief Standard division operator. This is currently implemented by a bit wise subtraction. Can be optimized by a 64 bit calculation.
691 : \detail. This routine is not particularly efficient as it declares three temporary vectors.
692 : */
693 42 : big_natural_number operator/(const big_natural_number& other) const
694 : {
695 : // Division by zero is not allowed.
696 42 : if (other.is_zero())
697 : {
698 0 : throw mcrl2::runtime_error("Division by zero.");
699 : }
700 : // Zero divided by something is zero.
701 42 : if (is_zero())
702 : {
703 2 : return *this;
704 : }
705 :
706 : // Often numbers only consist of one digit. Deal with this using machine division.
707 40 : if (m_number.size()==1 && other.m_number.size()==1)
708 : {
709 8 : return big_natural_number(m_number.front()/other.m_number.front());
710 : }
711 :
712 : // Otherwise do a multiple digit division.
713 32 : big_natural_number result, remainder, buffer;
714 32 : div_mod(other,result,remainder,buffer);
715 32 : return result;
716 32 : }
717 :
718 : /* \brief Standard modulo operator. This is currently implemented by a bit wise subtraction. Can be optimized by a 64 bit calculation.
719 : \detail. This routine is not particularly efficient as it declares three temporary vectors.
720 : */
721 42 : big_natural_number operator%(const big_natural_number& other) const
722 : {
723 : // Modulo zero is yields the value itself.
724 : // Zero modulo something is zero.
725 42 : if (other.is_zero() || is_zero())
726 : {
727 2 : return *this;
728 : }
729 :
730 : // Often numbers only consist of one digit. Deal with this using machine division.
731 40 : if (m_number.size()==1 && other.m_number.size()==1)
732 : {
733 8 : return big_natural_number(m_number.front()%other.m_number.front());
734 : }
735 :
736 32 : big_natural_number result, remainder, buffer;
737 32 : div_mod(other,result,remainder,buffer);
738 32 : return remainder;
739 :
740 32 : }
741 : };
742 :
743 470 : inline std::ostream& operator<<(std::ostream& ss, const big_natural_number& l)
744 : {
745 470 : static big_natural_number n; // This code is not re-entrant, but it avoids declaring a vector continuously.
746 470 : n=l;
747 470 : std::string s; // This string contains the number in reverse ordering.
748 30154 : for( ; !n.is_zero() ; )
749 : {
750 29684 : std::size_t remainder = n.divide_by(10); /* This divides n by 10. */
751 29684 : s.push_back(static_cast<char>('0'+remainder));
752 : }
753 470 : if (s.empty())
754 : {
755 14 : ss << "0";
756 : }
757 : else
758 : {
759 30140 : for(std::string::const_reverse_iterator i=s.rbegin(); i!=s.rend(); ++i)
760 : {
761 29684 : ss << *i;
762 : }
763 : }
764 470 : return ss;
765 470 : }
766 :
767 :
768 : /** \brief Standard overload of swap.
769 : **/
770 25 : inline void swap(big_natural_number& x, big_natural_number& y)
771 : {
772 25 : x.m_number.swap(y.m_number);
773 25 : }
774 :
775 : } // namespace utilities
776 : } // namespace mcrl2
777 :
778 : namespace std
779 : {
780 :
781 : template <>
782 : struct hash< mcrl2::utilities::big_natural_number >
783 : {
784 3030 : std::size_t operator()(const mcrl2::utilities::big_natural_number& n) const
785 : {
786 : hash<std::vector<std::size_t> > hasher;
787 3030 : return hasher(n.m_number);
788 : }
789 : };
790 :
791 :
792 : } // namespace std
793 :
794 : namespace mcrl2
795 : {
796 : namespace utilities
797 : {
798 : /* \brief A pretty print operator on action labels, returning it as a string.
799 : */
800 0 : inline std::string pp(const big_natural_number& l)
801 : {
802 0 : std::stringstream s;
803 0 : s << l;
804 0 : return s.str();
805 0 : }
806 : } // namespace utilities
807 : } // namespace mcrl2
808 :
809 :
810 : #endif // MCRL2_UTILITIES_BIG_NUMBERS_H
811 :
812 :
|
