1 /*
2  * InfInt - Arbitrary-Precision Integer Arithmetic Library
3  * Copyright (C) 2013 Sercan Tutar
4  *
5  * This Source Code Form is subject to the terms of the Mozilla Public
6  * License, v. 2.0. If a copy of the MPL was not distributed with this
7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8  */
9 
10 #ifndef _STEM4U_IntInf_h_
11 #define _STEM4U_IntInf_h_
12 
13 namespace Upp {
14 
15 #ifdef _MSC_VER
16 #define LONG_LONG_MIN LLONG_MIN
17 #define LONG_LONG_MAX LLONG_MAX
18 #define ULONG_LONG_MAX ULLONG_MAX
19 #endif
20 
21 typedef int ELEM_TYPE;
22 typedef long long PRODUCT_TYPE;
23 static const ELEM_TYPE BASE = 1000000000;
24 static const ELEM_TYPE UPPER_BOUND = 999999999;
25 static const ELEM_TYPE DIGIT_COUNT = 9;
26 static const int powersOfTen[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000 };
27 
28 template <class T>
29 struct cdiv_t {
30     T quot{};
31     T rem{};
32 };
33 
34 template <class T>
cdiv(T num,T denom)35 constexpr cdiv_t<T> cdiv(T num, T denom) {
36     cdiv_t<T> result;
37     result.quot = num / denom;
38     result.rem = num - denom * result.quot;
39     return result;
40 }
41 
42 class intInf {
43 public:
44     /* constructors */
45     intInf();
46     intInf(const char* c);
47     intInf(const String& s);
48     template <typename T>
49 	intInf(T l);
50     intInf(unsigned int l);
51     intInf(unsigned long l);
52     intInf(unsigned long long l);
53     intInf(const intInf& l);
54 
55     /* assignment operators */
56     const intInf& operator=(const char* c);
57     const intInf& operator=(const String& s);
58     const intInf& operator=(int l);
59     const intInf& operator=(long l);
60     const intInf& operator=(long long l);
61     const intInf& operator=(unsigned int l);
62     const intInf& operator=(unsigned long l);
63     const intInf& operator=(unsigned long long l);
64     const intInf& operator=(const intInf& l);
65 
66     /* unary increment/decrement operators */
67     const intInf& operator++();
68     const intInf& operator--();
69     intInf operator++(int);
70     intInf operator--(int);
71 
72     /* operational assignments */
73     const intInf& operator+=(const intInf& right);
74     const intInf& operator-=(const intInf& right);
75     const intInf& operator*=(const intInf& right);
76     const intInf& operator/=(const intInf& right);
77     const intInf& operator%=(const intInf& right);
78     const intInf& operator*=(ELEM_TYPE right);
79 
80     /* operations */
81     intInf operator-() const;
82     intInf operator+(const intInf& right) const;
83     intInf operator-(const intInf& right) const;
84     intInf operator*(const intInf& right) const;
85     intInf operator/(const intInf& right) const;
86     intInf operator%(const intInf& right) const;
87     intInf operator*(ELEM_TYPE right) const;
88 
89 	template <typename T>
90 	intInf operator+(T right) const {return *this + intInf(right);}
91 	template <typename T>
92 	intInf operator-(T right) const {return *this - intInf(right);}
93 	template <typename T>
94 	intInf operator/(T right) const {return *this / intInf(right);}
95 
96     /* relational operations */
97     bool operator==(const intInf& right) const;
98     bool operator!=(const intInf& right) const;
99     bool operator<(const intInf& right) const;
100     bool operator<=(const intInf& right) const;
101     bool operator>(const intInf& right) const;
102     bool operator>=(const intInf& right) const;
103 
104 	template <typename T>
105 	bool operator<(T right) const {
106 		return *this < intInf(right);
107 	}
108 	template <typename T>
109 	bool operator==(T right) const {
110 		return *this == intInf(right);
111 	}
112 	template <typename T>
113 	bool operator>=(T right) const {
114 		return *this >= intInf(right);
115 	}
116 
117     /* integer square root */
118     intInf intSqrt() const;
119 
120     /* digit operations */
121     char digitAt(int i) const;
122     int numberOfDigits() const;
123 
124     /* size in bytes */
125     int size() const;
126 
127     /* string conversion */
128     String ToString() const;
129 
130     /* conversion to primitive types */
131     int toInt() const;
132     long toLong() const;
133     long long toLongLong() const;
134     unsigned int toUnsignedInt() const;
135     unsigned long toUnsignedLong() const;
136     unsigned long long toUnsignedLongLong() const;
137 
138 	operator int() 					{return toInt();}
139 	operator long() 				{return toLong();}
140 	operator long long()			{return toLongLong();}
141 	operator unsigned int() 		{return toUnsignedInt();}
142 	operator unsigned long() 		{return toUnsignedLong();}
143 	operator unsigned long long() 	{return toUnsignedLongLong();}
144 
145 private:
146     static ELEM_TYPE dInR(const intInf& R, const intInf& D);
147     static void multiplyByDigit(ELEM_TYPE factor, Vector<ELEM_TYPE>& val);
148 
149     void correct(bool justCheckLeadingZeros = false, bool hasValidSign = false);
150     void fromString(const String& s);
151     void optimizeSqrtSearchBounds(intInf& lo, intInf& hi) const;
152     void truncateToBase();
153     bool equalizeSigns();
154     void removeLeadingZeros();
155 
156     bool pos; // true if number is positive
157     Vector<ELEM_TYPE> val; // number with base FACTOR
158 };
159 
intInf()160 inline intInf::intInf() : pos(true) {
161     val.push_back((ELEM_TYPE) 0);
162 }
163 
intInf(const char * c)164 inline intInf::intInf(const char* c) {
165     fromString(c);
166 }
167 
intInf(const String & s)168 inline intInf::intInf(const String& s) {
169     fromString(s);
170 }
171 
172 template <class T>
intInf(T l)173 inline intInf::intInf(T l) : pos(l >= 0) {
174     bool subtractOne = false;
175     if (l == std::numeric_limits<T>::min()) {
176         subtractOne = true;
177         ++l;
178     }
179     if (!pos)
180         l = -l;
181 
182     do {
183         auto dt = cdiv<T>(l, BASE);
184         val.push_back((ELEM_TYPE) dt.rem);
185         l = dt.quot;
186     } while (l > 0);
187 
188     if (subtractOne)
189         --*this;
190 }
191 
intInf(unsigned int l)192 inline intInf::intInf(unsigned int l) : pos(true) {
193     do {
194         val.push_back((ELEM_TYPE) (l % BASE));
195         l = l / BASE;
196     } while (l > 0);
197 }
198 
intInf(unsigned long l)199 inline intInf::intInf(unsigned long l) : pos(true) {
200     do {
201         val.push_back((ELEM_TYPE) (l % BASE));
202         l = l / BASE;
203     } while (l > 0);
204 }
205 
intInf(unsigned long long l)206 inline intInf::intInf(unsigned long long l) : pos(true) {
207     do {
208         val.push_back((ELEM_TYPE) (l % BASE));
209         l = l / BASE;
210     } while (l > 0);
211 }
212 
intInf(const intInf & l)213 inline intInf::intInf(const intInf& l) : pos(l.pos), val(clone(l.val)) {}
214 
215 inline const intInf& intInf::operator=(const char* c) {
216     fromString(c);
217     return *this;
218 }
219 
220 inline const intInf& intInf::operator=(const String& s) {
221     fromString(s);
222     return *this;
223 }
224 
225 inline const intInf& intInf::operator=(int l) {
226     bool subtractOne = false;
227     if (l == INT_MIN) {
228         subtractOne = true;
229         ++l;
230     }
231     pos = l >= 0;
232     val.clear();
233     if (!pos)
234         l = -l;
235     do {
236         auto dt = cdiv<int>(l, BASE);
237         val.push_back((ELEM_TYPE) dt.rem);
238         l = dt.quot;
239     } while (l > 0);
240 
241     return subtractOne ? --*this : *this;
242 }
243 
244 inline const intInf& intInf::operator=(long l) {
245     bool subtractOne = false;
246     if (l == LONG_MIN) {
247         subtractOne = true;
248         ++l;
249     }
250     pos = l >= 0;
251     val.clear();
252     if (!pos)
253         l = -l;
254     do {
255         auto dt = cdiv<long>(l, BASE);
256         val.push_back((ELEM_TYPE) dt.rem);
257         l = dt.quot;
258     } while (l > 0);
259 
260     return subtractOne ? --*this : *this;
261 }
262 
263 inline const intInf& intInf::operator=(long long l) {
264     bool subtractOne = false;
265     if (l == LONG_LONG_MIN) {
266         subtractOne = true;
267         ++l;
268     }
269     pos = l >= 0;
270     val.clear();
271     if (!pos)
272         l = -l;
273     do {
274         auto dt = cdiv<long long>(l, BASE);
275         val.push_back((ELEM_TYPE) dt.rem);
276         l = dt.quot;
277     } while (l > 0);
278 
279     return subtractOne ? --*this : *this;
280 }
281 
282 inline const intInf& intInf::operator=(unsigned int l) {
283     pos = true;
284     val.clear();
285     do {
286         val.push_back((ELEM_TYPE) (l % BASE));
287         l = l / BASE;
288     } while (l > 0);
289     return *this;
290 }
291 
292 inline const intInf& intInf::operator=(unsigned long l) {
293     pos = true;
294     val.clear();
295     do {
296         val.push_back((ELEM_TYPE) (l % BASE));
297         l = l / BASE;
298     } while (l > 0);
299     return *this;
300 }
301 
302 inline const intInf& intInf::operator=(unsigned long long l) {
303     pos = true;
304     val.clear();
305     do {
306         val.push_back((ELEM_TYPE) (l % BASE));
307         l = l / BASE;
308     } while (l > 0);
309     return *this;
310 }
311 
312 inline const intInf& intInf::operator=(const intInf& l) {
313     pos = l.pos;
314     val = clone(l.val);
315     return *this;
316 }
317 
318 inline const intInf& intInf::operator++() {
319     val[0] += (pos ? 1 : -1);
320     this->correct(false, true);
321     return *this;
322 }
323 
324 inline const intInf& intInf::operator--() {
325     val[0] -= (pos ? 1 : -1);
326     this->correct(false, true);
327     return *this;
328 }
329 
330 inline intInf intInf::operator++(int) {
331     intInf result = *this;
332     val[0] += (pos ? 1 : -1);
333     this->correct(false, true);
334     return result;
335 }
336 
337 inline intInf intInf::operator--(int) {
338     intInf result = *this;
339     val[0] -= (pos ? 1 : -1);
340     this->correct(false, true);
341     return result;
342 }
343 
344 inline const intInf& intInf::operator+=(const intInf& right) {
345     if (right.val.GetCount() > val.GetCount())
346         val.SetCount(right.val.GetCount(), 0);
347     for (int i = 0; i < val.GetCount(); ++i)
348         val[i] = (pos ? val[i] : -val[i]) + (i < right.val.GetCount() ? (right.pos ? right.val[i] : -right.val[i]) : 0);
349     correct();
350     return *this;
351 }
352 
353 inline const intInf& intInf::operator-=(const intInf& right) {
354     if (right.val.GetCount() > val.GetCount())
355         val.SetCount(right.val.GetCount(), 0);
356     for (int i = 0; i < val.GetCount(); ++i)
357         val[i] = (pos ? val[i] : -val[i]) - (i < right.val.GetCount() ? (right.pos ? right.val[i] : -right.val[i]) : 0);
358     correct();
359     return *this;
360 }
361 
362 inline const intInf& intInf::operator*=(const intInf& right) {
363     *this = *this * right;
364     return *this;
365 }
366 
367 inline const intInf& intInf::operator/=(const intInf& right) {
368     if (right == 0)
369         throw Exc("division by zero");
370 
371     intInf R, D = (right.pos ? right : -right), N = (pos ? *this : -*this);
372     bool oldpos = pos;
373     val.Set(0, 0, val.GetCount());
374     for (int i = (int) N.val.GetCount() - 1; i >= 0; --i) {
375         R.val.Insert(0, N.val[i]);
376         R.correct(true);
377         ELEM_TYPE cnt = dInR(R, D);
378         R -= D * cnt;
379         val[i] += cnt;
380     }
381     correct();
382     pos = (val.GetCount() == 1 && val[0] == 0) ? true : (oldpos == right.pos);
383     return *this;
384 }
385 
386 inline const intInf& intInf::operator%=(const intInf& right) {
387     *this = *this % right;
388     return *this;
389 }
390 
391 inline const intInf& intInf::operator*=(ELEM_TYPE right) {
392     ELEM_TYPE factor = right < 0 ? -right : right;
393     bool oldpos = pos;
394     multiplyByDigit(factor, val);
395     correct();
396     pos = (val.GetCount() == 1 && val[0] == 0) ? true : (oldpos == (right >= 0));
397     return *this;
398 }
399 
400 inline intInf intInf::operator-() const {
401     intInf result = *this;
402     result.pos = !pos;
403     return result;
404 }
405 
406 inline intInf intInf::operator+(const intInf& right) const {
407     intInf result;
408     result.val.SetCount(val.GetCount() > right.val.GetCount() ? val.GetCount() : right.val.GetCount(), 0);
409     for (int i = 0; i < val.GetCount() || i < right.val.GetCount(); ++i)
410         result.val[i] = (i < val.GetCount() ? (pos ? val[i] : -val[i]) : 0) + (i < right.val.GetCount() ? (right.pos ? right.val[i] : -right.val[i]) : 0);
411     result.correct();
412     return result;
413 }
414 
415 inline intInf intInf::operator-(const intInf& right) const {
416     intInf result;
417     result.val.SetCount(val.GetCount() > right.val.GetCount() ? val.GetCount() : right.val.GetCount(), 0);
418     for (int i = 0; i < val.GetCount() || i < right.val.GetCount(); ++i)
419         result.val[i] = (i < val.GetCount() ? (pos ? val[i] : -val[i]) : 0) - (i < right.val.GetCount() ? (right.pos ? right.val[i] : -right.val[i]) : 0);
420     result.correct();
421     return result;
422 }
423 
424 inline intInf intInf::operator*(const intInf& right) const {
425     intInf result;
426     result.val.SetCount(val.GetCount() + right.val.GetCount(), 0);
427     PRODUCT_TYPE carry = 0;
428     int digit = 0;
429     for (;; ++digit) {
430         auto dt = cdiv<long long>(carry, BASE);
431         carry = dt.quot;
432         result.val[digit] = (ELEM_TYPE) dt.rem;
433 
434         bool found = false;
435         for (int i = digit < right.val.GetCount() ? 0 : digit - right.val.GetCount() + 1; i < val.GetCount() && i <= digit; ++i) {
436             PRODUCT_TYPE pval = result.val[digit] + val[i] * (PRODUCT_TYPE) right.val[digit - i];
437             if (pval >= BASE || pval <= -BASE)
438             {
439                 auto dt = cdiv<long long>(pval, BASE);
440                 carry += dt.quot;
441                 pval = dt.rem;
442             }
443             result.val[digit] = (ELEM_TYPE) pval;
444             found = true;
445         }
446         if (!found)
447             break;
448     }
449     for (; carry > 0; ++digit) {
450         auto dt = cdiv<long long>(carry, BASE);
451         result.val[digit] = (ELEM_TYPE) dt.rem;
452         carry = dt.quot;
453     }
454     result.correct();
455     result.pos = (result.val.GetCount() == 1 && result.val[0] == 0) ? true : (pos == right.pos);
456     return result;
457 }
458 
459 inline intInf intInf::operator/(const intInf& right) const {
460     if (right == 0)
461         throw Exc("division by zero");
462 
463     intInf Q, R, D = (right.pos ? right : -right), N = (pos ? *this : -*this);
464     Q.val.SetCount(N.val.GetCount(), 0);
465     for (int i = (int) N.val.GetCount() - 1; i >= 0; --i) {
466         R.val.Insert(0, N.val[i]);
467         R.correct(true);
468         ELEM_TYPE cnt = dInR(R, D);
469         R -= D * cnt;
470         Q.val[i] += cnt;
471     }
472     Q.correct();
473     Q.pos = (Q.val.GetCount() == 1 && Q.val[0] == 0) ? true : (pos == right.pos);
474     return Q;
475 }
476 
477 inline intInf intInf::operator%(const intInf& right) const {
478     if (right == 0)
479         throw Exc("division by zero");
480 
481     intInf R, D = (right.pos ? right : -right), N = (pos ? *this : -*this);
482     for (int i = (int) N.val.GetCount() - 1; i >= 0; --i) {
483         R.val.Insert(0, N.val[i]);
484         R.correct(true);
485         R -= D * dInR(R, D);
486     }
487     R.correct();
488     R.pos = (R.val.GetCount() == 1 && R.val[0] == 0) ? true : pos;
489     return R;
490 }
491 
492 inline intInf intInf::operator*(ELEM_TYPE right) const {
493     intInf result = *this;
494     ELEM_TYPE factor = right < 0 ? -right : right;
495     multiplyByDigit(factor, result.val);
496     result.correct();
497     result.pos = (result.val.GetCount() == 1 && result.val[0] == 0) ? true : (pos == (right >= 0));
498     return result;
499 }
500 
501 inline bool intInf::operator==(const intInf& right) const {
502     if (pos != right.pos || val.GetCount() != right.val.GetCount())
503         return false;
504     for (int i = val.GetCount() - 1; i >= 0; --i)
505         if (val[i] != right.val[i])
506             return false;
507     return true;
508 }
509 
510 inline bool intInf::operator!=(const intInf& right) const {
511     if (pos != right.pos || val.GetCount() != right.val.GetCount())
512         return true;
513     for (int i = (int) val.GetCount() - 1; i >= 0; --i)
514         if (val[i] != right.val[i])
515             return true;
516     return false;
517 }
518 
519 inline bool intInf::operator<(const intInf& right) const {
520     if (pos && !right.pos)
521         return false;
522     if (!pos && right.pos)
523         return true;
524     if (val.GetCount() > right.val.GetCount())
525         return pos ? false : true;
526     if (val.GetCount() < right.val.GetCount())
527         return pos ? true : false;
528     for (int i = (int) val.GetCount() - 1; i >= 0; --i) {
529         if (val[i] < right.val[i])
530             return pos ? true : false;
531         if (val[i] > right.val[i])
532             return pos ? false : true;
533     }
534     return false;
535 }
536 
537 inline bool intInf::operator<=(const intInf& right) const {
538     if (pos && !right.pos)
539         return false;
540     if (!pos && right.pos)
541         return true;
542     if (val.GetCount() > right.val.GetCount())
543         return pos ? false : true;
544     if (val.GetCount() < right.val.GetCount())
545         return pos ? true : false;
546     for (int i = (int) val.GetCount() - 1; i >= 0; --i) {
547         if (val[i] < right.val[i])
548             return pos ? true : false;
549         if (val[i] > right.val[i])
550             return pos ? false : true;
551     }
552     return true;
553 }
554 
555 inline bool intInf::operator>(const intInf& right) const {
556     if (pos && !right.pos)
557         return true;
558     if (!pos && right.pos)
559         return false;
560     if (val.GetCount() > right.val.GetCount())
561         return pos ? true : false;
562     if (val.GetCount() < right.val.GetCount())
563         return pos ? false : true;
564     for (int i = (int) val.GetCount() - 1; i >= 0; --i) {
565         if (val[i] < right.val[i])
566             return pos ? false : true;
567         if (val[i] > right.val[i])
568             return pos ? true : false;
569     }
570     return false;
571 }
572 
573 inline bool intInf::operator>=(const intInf& right) const {
574     if (pos && !right.pos)
575         return true;
576     if (!pos && right.pos)
577         return false;
578     if (val.GetCount() > right.val.GetCount())
579         return pos ? true : false;
580     if (val.GetCount() < right.val.GetCount())
581         return pos ? false : true;
582     for (int i = (int) val.GetCount() - 1; i >= 0; --i) {
583         if (val[i] < right.val[i])
584             return pos ? false : true;
585         if (val[i] > right.val[i])
586             return pos ? true : false;
587     }
588     return true;
589 }
590 
optimizeSqrtSearchBounds(intInf & lo,intInf & hi)591 inline void intInf::optimizeSqrtSearchBounds(intInf& lo, intInf& hi) const {
592     intInf hdn = 1;
593     for (int i = (int) this->numberOfDigits() / 2; i >= 2; --i)
594         hdn *= 10;
595     if (lo < hdn)
596         lo = hdn;
597     hdn *= 100;
598     if (hi > hdn)
599         hi = hdn;
600 }
601 
602 
intSqrt()603 inline intInf intInf::intSqrt() const {
604     if (*this <= 0)
605         throw Exc("intSqrt called for non-positive integer");
606 
607     intInf hi = *this / 2 + 1, lo = 0, mid, mid2;
608     optimizeSqrtSearchBounds(lo, hi);
609     do {
610         mid = (hi + lo) / 2; // 8 factor
611         mid2 = mid * mid; // 1 factor
612         if (mid2 == *this) {
613             lo = mid;
614             break;
615         } else if (mid2 < *this)
616             lo = mid;
617         else
618             hi = mid;
619     } while (lo < hi - 1 && mid2 != *this);
620     return lo;
621 }
622 
digitAt(int i)623 inline char intInf::digitAt(int i) const {
624     ASSERT(numberOfDigits() <= i);
625 
626     return (val[i / DIGIT_COUNT] / powersOfTen[i % DIGIT_COUNT]) % 10;
627 }
628 
numberOfDigits()629 inline int intInf::numberOfDigits() const {
630     return (val.GetCount() - 1) * DIGIT_COUNT +
631         (val.back() > 99999999 ? 9 : (val.back() > 9999999 ? 8 : (val.back() > 999999 ? 7 : (val.back() > 99999 ? 6 :
632         (val.back() > 9999 ? 5 : (val.back() > 999 ? 4 : (val.back() > 99 ? 3 : (val.back() > 9 ? 2 : 1))))))));
633 }
634 
ToString()635 inline String intInf::ToString() const {
636 	String s;
637     if (!pos)
638         s << '-';
639     bool first = true;
640     for (int i = (int) val.GetCount() - 1; i >= 0; --i) {
641         if (first) {
642             s << val[i];
643             first = false;
644         } else
645             s << FormatIntDec(val[i], DIGIT_COUNT, '0');
646     }
647     return s;
648 }
649 
size()650 inline int intInf::size() const {
651     return val.GetCount() * sizeof(ELEM_TYPE) + sizeof(bool);
652 }
653 
toInt()654 inline int intInf::toInt() const {
655     if (*this > INT_MAX || *this < INT_MIN)
656         throw Exc("out of bounds");
657 
658     int result = 0;
659     for (int i = (int) val.GetCount() - 1; i >= 0; --i)
660         result = result * BASE + val[i];
661     return pos ? result : -result;
662 }
663 
toLong()664 inline long intInf::toLong() const {
665     if (*this > LONG_MAX || *this < LONG_MIN)
666         throw Exc("out of bounds");
667 
668     long result = 0;
669     for (int i = (int) val.GetCount() - 1; i >= 0; --i)
670         result = result * BASE + val[i];
671     return pos ? result : -result;
672 }
673 
toLongLong()674 inline long long intInf::toLongLong() const {
675     if (*this > LONG_LONG_MAX || *this < LONG_LONG_MIN)
676         throw Exc("out of bounds");
677 
678     long long result = 0;
679     for (int i = (int) val.GetCount() - 1; i >= 0; --i)
680         result = result * BASE + val[i];
681     return pos ? result : -result;
682 }
683 
toUnsignedInt()684 inline unsigned int intInf::toUnsignedInt() const {
685     if (!pos || *this > UINT_MAX)
686         throw Exc("out of bounds");
687 
688     unsigned int result = 0;
689     for (int i = (int) val.GetCount() - 1; i >= 0; --i)
690         result = result * BASE + val[i];
691     return result;
692 }
693 
toUnsignedLong()694 inline unsigned long intInf::toUnsignedLong() const {
695     if (!pos || *this > ULONG_MAX)
696         throw Exc("out of bounds");
697 
698     unsigned long result = 0;
699     for (int i = (int) val.GetCount() - 1; i >= 0; --i)
700         result = result * BASE + val[i];
701     return result;
702 }
703 
toUnsignedLongLong()704 inline unsigned long long intInf::toUnsignedLongLong() const {
705     if (!pos || *this > ULONG_LONG_MAX)
706         throw Exc("out of bounds");
707 
708     unsigned long long result = 0;
709     for (int i = (int) val.GetCount() - 1; i >= 0; --i)
710         result = result * BASE + val[i];
711     return result;
712 }
713 
truncateToBase()714 inline void intInf::truncateToBase() {
715     for (int i = 0; i < val.GetCount(); ++i) { // truncate each
716         if (val[i] >= BASE || val[i] <= -BASE) {
717             auto dt = cdiv<int>(val[i], BASE);
718             val[i] = dt.rem;
719             if (i + 1 >= val.GetCount())
720                 val.push_back(dt.quot);
721             else
722                 val[i + 1] += dt.quot;
723         }
724     }
725 }
726 
equalizeSigns()727 inline bool intInf::equalizeSigns() {
728     bool isPositive = true;
729     int i = (int) ((val.GetCount())) - 1;
730     for (; i >= 0; --i) {
731         if (val[i] != 0) {
732             isPositive = val[i--] > 0;
733             break;
734         }
735     }
736 
737     if (isPositive) {
738         for (; i >= 0; --i) {
739             if (val[i] < 0) {
740                 int k = 0, index = i + 1;
741                 for (; index < val.GetCount() && val[index] == 0; ++k, ++index)
742                     ; // count adjacent zeros on left
743                 //if ((size_t)(index) < val.size() && val[index] > 0)
744                 { // number on the left is positive
745                     val[index] -= 1;
746                     val[i] += BASE;
747                     for (; k > 0; --k)
748                     {
749                         val[i + k] = UPPER_BOUND;
750                     }
751                 }
752             }
753         }
754     } else {
755         for (; i >= 0; --i) {
756             if (val[i] > 0) {
757                 int k = 0, index = i + 1;
758                 for (; index < val.GetCount() && val[index] == 0; ++k, ++index)
759                     ; // count adjacent zeros on right
760                 //if ((size_t)(index) < val.size() && val[index] < 0)
761                 { // number on the left is negative
762                     val[index] += 1;
763                     val[i] -= BASE;
764                     for (; k > 0; --k)
765                         val[i + k] = -UPPER_BOUND;
766                 }
767             }
768         }
769     }
770 
771     return isPositive;
772 }
773 
removeLeadingZeros()774 inline void intInf::removeLeadingZeros() {
775     for (int i = (int) (val.GetCount()) - 1; i > 0; --i) { // remove leading 0's
776         if (val[i] != 0)
777             return;
778         else
779             val.Remove(i);
780     }
781 }
782 
correct(bool justCheckLeadingZeros,bool hasValidSign)783 inline void intInf::correct(bool justCheckLeadingZeros, bool hasValidSign) {
784     if (!justCheckLeadingZeros) {
785         truncateToBase();
786 
787         if (equalizeSigns())
788             pos = ((val.GetCount() == 1 && val[0] == 0) || !hasValidSign) ? true : pos;
789         else {
790             pos = hasValidSign ? !pos : false;
791             for (int i = 0; i < val.GetCount(); ++i)
792                 val[i] = ::abs(val[i]);
793         }
794     }
795     removeLeadingZeros();
796 }
797 
fromString(const String & s)798 inline void intInf::fromString(const String& s) {
799     pos = true;
800     val.Clear();
801     val.Reserve(s.GetCount() / DIGIT_COUNT + 1);
802     int i = s.GetCount() - DIGIT_COUNT;
803     for (; i >= 0; i -= DIGIT_COUNT)
804         val << atoi(s.Mid(i, DIGIT_COUNT));
805     if (i > -DIGIT_COUNT) {
806         String ss = s.Left(i + DIGIT_COUNT);
807         if (ss.GetCount() == 1 && ss[0] == '-')
808             pos = false;
809         else
810             val.push_back(atoi(ss));
811     }
812     if (val.back() < 0) {
813         val.back() = -val.back();
814         pos = false;
815     }
816     correct(true);
817 }
818 
dInR(const intInf & R,const intInf & D)819 inline ELEM_TYPE intInf::dInR(const intInf& R, const intInf& D) {
820     ELEM_TYPE min = 0, max = UPPER_BOUND;
821     while (max > min) {
822         ELEM_TYPE avg = max + min;
823         auto dt = cdiv<int>(avg, 2);
824         avg = dt.rem ? (dt.quot + 1) : dt.quot;
825         intInf prod = D * avg;
826         if (R == prod)
827             return avg;
828         else if (R > prod)
829             min = avg;
830         else
831             max = avg - 1;
832     }
833     return min;
834 }
835 
multiplyByDigit(ELEM_TYPE factor,Vector<ELEM_TYPE> & val)836 inline void intInf::multiplyByDigit(ELEM_TYPE factor, Vector<ELEM_TYPE>& val) {
837     ELEM_TYPE carry = 0;
838     for (int i = 0; i < val.GetCount(); ++i) {
839         PRODUCT_TYPE pval = val[i] * (PRODUCT_TYPE) factor + carry;
840         if (pval >= BASE || pval <= -BASE) {
841             auto dt = cdiv<long long>(pval, BASE);
842             carry = (ELEM_TYPE) dt.quot;
843             pval = dt.rem;
844         } else
845             carry = 0;
846         val[i] = (ELEM_TYPE) pval;
847     }
848     if (carry > 0)
849         val.push_back(carry);
850 }
851 
852 }
853 
854 #endif
855