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