Version 7.3.5.2, tag libreoffice-7.3.5.2
[LibreOffice.git] / tools / source / generic / bigint.cxx
blobf6627200a61c77f43f5f0139ec28f590e6b840ec
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
3 * This file is part of the LibreOffice project.
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/.
9 * This file incorporates work covered by the following license notice:
11 * Licensed to the Apache Software Foundation (ASF) under one or more
12 * contributor license agreements. See the NOTICE file distributed
13 * with this work for additional information regarding copyright
14 * ownership. The ASF licenses this file to you under the Apache
15 * License, Version 2.0 (the "License"); you may not use this file
16 * except in compliance with the License. You may obtain a copy of
17 * the License at http://www.apache.org/licenses/LICENSE-2.0 .
20 #include <math.h>
22 #include <osl/diagnose.h>
23 #include <tools/bigint.hxx>
25 #include <algorithm>
26 #include <string.h>
28 /**
29 * The range in which we can perform add/sub without fear of overflow
31 const sal_Int32 MY_MAXLONG = 0x3fffffff;
32 const sal_Int32 MY_MINLONG = -MY_MAXLONG;
35 * The algorithms for Addition, Subtraction, Multiplication and Division
36 * of large numbers originate from SEMINUMERICAL ALGORITHMS by
37 * DONALD E. KNUTH in the series The Art of Computer Programming:
38 * chapter 4.3.1. The Classical Algorithms.
41 // TODO: Needs conversion to sal_uInt16/INT16/sal_uInt32/sal_Int32
42 void BigInt::MakeBigInt( const BigInt& rVal )
44 if ( rVal.nLen != 0 )
46 memcpy( static_cast<void*>(this), static_cast<const void*>(&rVal), sizeof( BigInt ) );
47 while ( nLen > 1 && nNum[nLen-1] == 0 )
48 nLen--;
50 else
52 nVal = rVal.nVal;
53 sal_uInt32 nTmp;
54 if (nVal < 0)
56 bIsNeg = true;
57 nTmp = -static_cast<sal_Int64>(nVal);
59 else
61 bIsNeg = false;
62 nTmp = nVal;
65 nNum[0] = static_cast<sal_uInt16>(nTmp & 0xffffL);
66 nNum[1] = static_cast<sal_uInt16>(nTmp >> 16);
67 if ( nTmp & 0xffff0000L )
68 nLen = 2;
69 else
70 nLen = 1;
74 void BigInt::Normalize()
76 if ( nLen != 0 )
78 while ( nLen > 1 && nNum[nLen-1] == 0 )
79 nLen--;
81 if ( nLen < 3 )
83 sal_Int32 newVal;
84 if ( nLen < 2 )
85 newVal = nNum[0];
86 else if ( nNum[1] & 0x8000 )
87 return;
88 else
89 newVal = (static_cast<sal_Int32>(nNum[1]) << 16) + nNum[0];
91 nLen = 0;
92 nVal = newVal;
94 if ( bIsNeg )
95 nVal = -nVal;
97 // else nVal is undefined !!! W.P.
99 // why? nVal is undefined ??? W.P.
100 else if ( nVal & 0xFFFF0000L )
101 nLen = 2;
102 else
103 nLen = 1;
106 void BigInt::Mult( const BigInt &rVal, sal_uInt16 nMul )
108 sal_uInt16 nK = 0;
109 for ( int i = 0; i < rVal.nLen; i++ )
111 sal_uInt32 nTmp = static_cast<sal_uInt32>(rVal.nNum[i]) * static_cast<sal_uInt32>(nMul) + nK;
112 nK = static_cast<sal_uInt16>(nTmp >> 16);
113 nNum[i] = static_cast<sal_uInt16>(nTmp);
116 if ( nK )
118 nNum[rVal.nLen] = nK;
119 nLen = rVal.nLen + 1;
121 else
122 nLen = rVal.nLen;
124 bIsNeg = rVal.bIsNeg;
127 void BigInt::Div( sal_uInt16 nDiv, sal_uInt16& rRem )
129 sal_uInt32 nK = 0;
130 for ( int i = nLen - 1; i >= 0; i-- )
132 sal_uInt32 nTmp = static_cast<sal_uInt32>(nNum[i]) + (nK << 16);
133 nNum[i] = static_cast<sal_uInt16>(nTmp / nDiv);
134 nK = nTmp % nDiv;
136 rRem = static_cast<sal_uInt16>(nK);
138 if ( nNum[nLen-1] == 0 )
139 nLen -= 1;
142 bool BigInt::IsLess( const BigInt& rVal ) const
144 if ( rVal.nLen < nLen)
145 return true;
146 if ( rVal.nLen > nLen )
147 return false;
149 int i;
150 for ( i = nLen - 1; i > 0 && nNum[i] == rVal.nNum[i]; i-- )
153 return rVal.nNum[i] < nNum[i];
156 void BigInt::AddLong( BigInt& rB, BigInt& rErg )
158 if ( bIsNeg == rB.bIsNeg )
160 int i;
161 char len;
163 // if length of the two values differ, fill remaining positions
164 // of the smaller value with zeros.
165 if (nLen >= rB.nLen)
167 len = nLen;
168 for (i = rB.nLen; i < len; i++)
169 rB.nNum[i] = 0;
171 else
173 len = rB.nLen;
174 for (i = nLen; i < len; i++)
175 nNum[i] = 0;
178 // Add numerals, starting from the back
179 sal_Int32 k;
180 sal_Int32 nZ = 0;
181 for (i = 0, k = 0; i < len; i++) {
182 nZ = static_cast<sal_Int32>(nNum[i]) + static_cast<sal_Int32>(rB.nNum[i]) + k;
183 if (nZ & 0xff0000L)
184 k = 1;
185 else
186 k = 0;
187 rErg.nNum[i] = static_cast<sal_uInt16>(nZ & 0xffffL);
189 // If an overflow occurred, add to solution
190 if (nZ & 0xff0000L) // or if(k)
192 rErg.nNum[i] = 1;
193 len++;
195 // Set length and sign
196 rErg.nLen = len;
197 rErg.bIsNeg = bIsNeg && rB.bIsNeg;
199 // If one of the values is negative, perform subtraction instead
200 else if (bIsNeg)
202 bIsNeg = false;
203 rB.SubLong(*this, rErg);
204 bIsNeg = true;
206 else
208 rB.bIsNeg = false;
209 SubLong(rB, rErg);
210 rB.bIsNeg = true;
214 void BigInt::SubLong( BigInt& rB, BigInt& rErg )
216 if ( bIsNeg == rB.bIsNeg )
218 int i;
219 char len;
220 sal_Int32 nZ, k;
222 // if length of the two values differ, fill remaining positions
223 // of the smaller value with zeros.
224 if (nLen >= rB.nLen)
226 len = nLen;
227 for (i = rB.nLen; i < len; i++)
228 rB.nNum[i] = 0;
230 else
232 len = rB.nLen;
233 for (i = nLen; i < len; i++)
234 nNum[i] = 0;
237 if ( IsLess(rB) )
239 for (i = 0, k = 0; i < len; i++)
241 nZ = static_cast<sal_Int32>(nNum[i]) - static_cast<sal_Int32>(rB.nNum[i]) + k;
242 if (nZ < 0)
243 k = -1;
244 else
245 k = 0;
246 rErg.nNum[i] = static_cast<sal_uInt16>(nZ & 0xffffL);
248 rErg.bIsNeg = bIsNeg;
250 else
252 for (i = 0, k = 0; i < len; i++)
254 nZ = static_cast<sal_Int32>(rB.nNum[i]) - static_cast<sal_Int32>(nNum[i]) + k;
255 if (nZ < 0)
256 k = -1;
257 else
258 k = 0;
259 rErg.nNum[i] = static_cast<sal_uInt16>(nZ & 0xffffL);
261 // if a < b, revert sign
262 rErg.bIsNeg = !bIsNeg;
264 rErg.nLen = len;
266 // If one of the values is negative, perform addition instead
267 else if (bIsNeg)
269 bIsNeg = false;
270 AddLong(rB, rErg);
271 bIsNeg = true;
272 rErg.bIsNeg = true;
274 else
276 rB.bIsNeg = false;
277 AddLong(rB, rErg);
278 rB.bIsNeg = true;
279 rErg.bIsNeg = false;
283 void BigInt::MultLong( const BigInt& rB, BigInt& rErg ) const
285 int i, j;
286 sal_uInt32 nZ, k;
288 rErg.bIsNeg = bIsNeg != rB.bIsNeg;
289 rErg.nLen = nLen + rB.nLen;
291 for (i = 0; i < rErg.nLen; i++)
292 rErg.nNum[i] = 0;
294 for (j = 0; j < rB.nLen; j++)
296 for (i = 0, k = 0; i < nLen; i++)
298 nZ = static_cast<sal_uInt32>(nNum[i]) * static_cast<sal_uInt32>(rB.nNum[j]) +
299 static_cast<sal_uInt32>(rErg.nNum[i + j]) + k;
300 rErg.nNum[i + j] = static_cast<sal_uInt16>(nZ & 0xffffU);
301 k = nZ >> 16;
303 rErg.nNum[i + j] = static_cast<sal_uInt16>(k);
307 void BigInt::DivLong( const BigInt& rB, BigInt& rErg ) const
309 int i, j;
310 sal_uInt16 nK, nQ, nMult;
311 sal_uInt16 nLenB = rB.nLen;
312 sal_uInt16 nLenB1 = rB.nLen - 1;
313 BigInt aTmpA, aTmpB;
315 nMult = static_cast<sal_uInt16>(0x10000L / (static_cast<sal_Int32>(rB.nNum[nLenB1]) + 1));
317 aTmpA.Mult( *this, nMult );
318 if ( aTmpA.nLen == nLen )
320 aTmpA.nNum[aTmpA.nLen] = 0;
321 aTmpA.nLen++;
324 aTmpB.Mult( rB, nMult );
326 for (j = aTmpA.nLen - 1; j >= nLenB; j--)
327 { // guess divisor
328 sal_uInt32 nTmp = ( static_cast<sal_uInt32>(aTmpA.nNum[j]) << 16 ) + aTmpA.nNum[j - 1];
329 if (aTmpA.nNum[j] == aTmpB.nNum[nLenB1])
330 nQ = 0xFFFF;
331 else
332 nQ = static_cast<sal_uInt16>(nTmp / aTmpB.nNum[nLenB1]);
334 if ( (static_cast<sal_uInt32>(aTmpB.nNum[nLenB1 - 1]) * nQ) >
335 ((nTmp - static_cast<sal_uInt32>(aTmpB.nNum[nLenB1]) * nQ) << 16) + aTmpA.nNum[j - 2])
336 nQ--;
337 // Start division
338 nK = 0;
339 for (i = 0; i < nLenB; i++)
341 nTmp = static_cast<sal_uInt32>(aTmpA.nNum[j - nLenB + i])
342 - (static_cast<sal_uInt32>(aTmpB.nNum[i]) * nQ)
343 - nK;
344 aTmpA.nNum[j - nLenB + i] = static_cast<sal_uInt16>(nTmp);
345 nK = static_cast<sal_uInt16>(nTmp >> 16);
346 if ( nK )
347 nK = static_cast<sal_uInt16>(0x10000U - nK);
349 sal_uInt16& rNum( aTmpA.nNum[j - nLenB + i] );
350 rNum -= nK;
351 if (aTmpA.nNum[j - nLenB + i] == 0)
352 rErg.nNum[j - nLenB] = nQ;
353 else
355 rErg.nNum[j - nLenB] = nQ - 1;
356 nK = 0;
357 for (i = 0; i < nLenB; i++)
359 nTmp = aTmpA.nNum[j - nLenB + i] + aTmpB.nNum[i] + nK;
360 aTmpA.nNum[j - nLenB + i] = static_cast<sal_uInt16>(nTmp & 0xFFFFL);
361 if (nTmp & 0xFFFF0000L)
362 nK = 1;
363 else
364 nK = 0;
369 rErg.bIsNeg = bIsNeg != rB.bIsNeg;
370 rErg.nLen = nLen - rB.nLen + 1;
373 void BigInt::ModLong( const BigInt& rB, BigInt& rErg ) const
375 sal_uInt16 i, j;
376 sal_uInt16 nK, nQ, nMult;
377 sal_Int16 nLenB = rB.nLen;
378 sal_Int16 nLenB1 = rB.nLen - 1;
379 BigInt aTmpA, aTmpB;
381 nMult = static_cast<sal_uInt16>(0x10000L / (static_cast<sal_Int32>(rB.nNum[nLenB1]) + 1));
383 aTmpA.Mult( *this, nMult);
384 if ( aTmpA.nLen == nLen )
386 aTmpA.nNum[aTmpA.nLen] = 0;
387 aTmpA.nLen++;
390 aTmpB.Mult( rB, nMult);
392 for (j = aTmpA.nLen - 1; j >= nLenB; j--)
393 { // Guess divisor
394 sal_uInt32 nTmp = ( static_cast<sal_uInt32>(aTmpA.nNum[j]) << 16 ) + aTmpA.nNum[j - 1];
395 if (aTmpA.nNum[j] == aTmpB.nNum[nLenB1])
396 nQ = 0xFFFF;
397 else
398 nQ = static_cast<sal_uInt16>(nTmp / aTmpB.nNum[nLenB1]);
400 if ( (static_cast<sal_uInt32>(aTmpB.nNum[nLenB1 - 1]) * nQ) >
401 ((nTmp - aTmpB.nNum[nLenB1] * nQ) << 16) + aTmpA.nNum[j - 2])
402 nQ--;
403 // Start division
404 nK = 0;
405 for (i = 0; i < nLenB; i++)
407 nTmp = static_cast<sal_uInt32>(aTmpA.nNum[j - nLenB + i])
408 - (static_cast<sal_uInt32>(aTmpB.nNum[i]) * nQ)
409 - nK;
410 aTmpA.nNum[j - nLenB + i] = static_cast<sal_uInt16>(nTmp);
411 nK = static_cast<sal_uInt16>(nTmp >> 16);
412 if ( nK )
413 nK = static_cast<sal_uInt16>(0x10000U - nK);
415 sal_uInt16& rNum( aTmpA.nNum[j - nLenB + i] );
416 rNum = rNum - nK;
417 if (aTmpA.nNum[j - nLenB + i] == 0)
418 rErg.nNum[j - nLenB] = nQ;
419 else
421 rErg.nNum[j - nLenB] = nQ - 1;
422 nK = 0;
423 for (i = 0; i < nLenB; i++) {
424 nTmp = aTmpA.nNum[j - nLenB + i] + aTmpB.nNum[i] + nK;
425 aTmpA.nNum[j - nLenB + i] = static_cast<sal_uInt16>(nTmp & 0xFFFFL);
426 if (nTmp & 0xFFFF0000L)
427 nK = 1;
428 else
429 nK = 0;
434 rErg = aTmpA;
435 rErg.Div( nMult, nQ );
438 bool BigInt::ABS_IsLess( const BigInt& rB ) const
440 if (nLen != 0 || rB.nLen != 0)
442 BigInt nA, nB;
443 nA.MakeBigInt( *this );
444 nB.MakeBigInt( rB );
445 if (nA.nLen == nB.nLen)
447 int i;
448 for (i = nA.nLen - 1; i > 0 && nA.nNum[i] == nB.nNum[i]; i--)
451 return nA.nNum[i] < nB.nNum[i];
453 else
454 return nA.nLen < nB.nLen;
456 if ( nVal < 0 )
457 if ( rB.nVal < 0 )
458 return nVal > rB.nVal;
459 else
460 return nVal > -rB.nVal;
461 else
462 if ( rB.nVal < 0 )
463 return nVal < -rB.nVal;
464 else
465 return nVal < rB.nVal;
468 BigInt::BigInt( const BigInt& rBigInt )
469 : nLen(0)
470 , bIsNeg(false)
472 if ( rBigInt.nLen != 0 )
473 memcpy( static_cast<void*>(this), static_cast<const void*>(&rBigInt), sizeof( BigInt ) );
474 else
475 nVal = rBigInt.nVal;
478 BigInt::BigInt( const OUString& rString )
479 : nLen(0)
481 bIsNeg = false;
482 nVal = 0;
484 bool bNeg = false;
485 const sal_Unicode* p = rString.getStr();
486 if ( *p == '-' )
488 bNeg = true;
489 p++;
491 while( *p >= '0' && *p <= '9' )
493 *this *= 10;
494 *this += *p - '0';
495 p++;
497 if ( nLen != 0 )
498 bIsNeg = bNeg;
499 else if( bNeg )
500 nVal = -nVal;
503 BigInt::BigInt( double nValue )
504 : nVal(0)
506 if ( nValue < 0 )
508 nValue *= -1;
509 bIsNeg = true;
511 else
513 bIsNeg = false;
516 if ( nValue < 1 )
518 nVal = 0;
519 nLen = 0;
521 else
523 int i=0;
525 while ( ( nValue > 65536.0 ) && ( i < MAX_DIGITS ) )
527 nNum[i] = static_cast<sal_uInt16>(fmod( nValue, 65536.0 ));
528 nValue -= nNum[i];
529 nValue /= 65536.0;
530 i++;
532 if ( i < MAX_DIGITS )
533 nNum[i++] = static_cast<sal_uInt16>(nValue);
535 nLen = i;
537 if ( i < 3 )
538 Normalize();
542 BigInt::BigInt( sal_uInt32 nValue )
543 : nVal(0)
545 if ( nValue & 0x80000000U )
547 bIsNeg = false;
548 nNum[0] = static_cast<sal_uInt16>(nValue & 0xffffU);
549 nNum[1] = static_cast<sal_uInt16>(nValue >> 16);
550 nLen = 2;
552 else
554 bIsNeg = false;
555 nVal = nValue;
556 nLen = 0;
560 BigInt::BigInt( sal_Int64 nValue )
561 : nVal(0)
563 bIsNeg = nValue < 0;
564 nLen = 0;
566 if ((nValue >= SAL_MIN_INT32) && (nValue <= SAL_MAX_INT32))
568 nVal = static_cast<sal_Int32>(nValue);
570 else
572 sal_uInt64 nUValue = static_cast<sal_uInt64>(bIsNeg ? -nValue : nValue);
573 for (int i = 0; (i != sizeof(sal_uInt64) / 2) && (nUValue != 0); ++i)
575 nNum[i] = static_cast<sal_uInt16>(nUValue & 0xffffUL);
576 nUValue = nUValue >> 16;
577 ++nLen;
582 BigInt::operator double() const
584 if ( nLen == 0 )
585 return static_cast<double>(nVal);
586 else
588 int i = nLen-1;
589 double nRet = static_cast<double>(static_cast<sal_uInt32>(nNum[i]));
591 while ( i )
593 nRet *= 65536.0;
594 i--;
595 nRet += static_cast<double>(static_cast<sal_uInt32>(nNum[i]));
598 if ( bIsNeg )
599 nRet *= -1;
601 return nRet;
605 BigInt& BigInt::operator=( const BigInt& rBigInt )
607 if (this == &rBigInt)
608 return *this;
610 if ( rBigInt.nLen != 0 )
611 memcpy( static_cast<void*>(this), static_cast<const void*>(&rBigInt), sizeof( BigInt ) );
612 else
614 nLen = 0;
615 nVal = rBigInt.nVal;
617 return *this;
620 BigInt& BigInt::operator+=( const BigInt& rVal )
622 if ( nLen == 0 && rVal.nLen == 0 )
624 if( nVal <= MY_MAXLONG && rVal.nVal <= MY_MAXLONG
625 && nVal >= MY_MINLONG && rVal.nVal >= MY_MINLONG )
626 { // No overflows may occur here
627 nVal += rVal.nVal;
628 return *this;
631 if( (nVal < 0) != (rVal.nVal < 0) )
632 { // No overflows may occur here
633 nVal += rVal.nVal;
634 return *this;
638 BigInt aTmp1, aTmp2;
639 aTmp1.MakeBigInt( *this );
640 aTmp2.MakeBigInt( rVal );
641 aTmp1.AddLong( aTmp2, *this );
642 Normalize();
643 return *this;
646 BigInt& BigInt::operator-=( const BigInt& rVal )
648 if ( nLen == 0 && rVal.nLen == 0 )
650 if ( nVal <= MY_MAXLONG && rVal.nVal <= MY_MAXLONG &&
651 nVal >= MY_MINLONG && rVal.nVal >= MY_MINLONG )
652 { // No overflows may occur here
653 nVal -= rVal.nVal;
654 return *this;
657 if ( (nVal < 0) == (rVal.nVal < 0) )
658 { // No overflows may occur here
659 nVal -= rVal.nVal;
660 return *this;
664 BigInt aTmp1, aTmp2;
665 aTmp1.MakeBigInt( *this );
666 aTmp2.MakeBigInt( rVal );
667 aTmp1.SubLong( aTmp2, *this );
668 Normalize();
669 return *this;
672 BigInt& BigInt::operator*=( const BigInt& rVal )
674 static const sal_Int32 MY_MAXSHORT = 0x00007fff;
675 static const sal_Int32 MY_MINSHORT = -MY_MAXSHORT;
677 if ( nLen == 0 && rVal.nLen == 0
678 && nVal <= MY_MAXSHORT && rVal.nVal <= MY_MAXSHORT
679 && nVal >= MY_MINSHORT && rVal.nVal >= MY_MINSHORT )
680 // TODO: not optimal !!! W.P.
681 { // No overflows may occur here
682 nVal *= rVal.nVal;
684 else
686 BigInt aTmp1, aTmp2;
687 aTmp1.MakeBigInt( rVal );
688 aTmp2.MakeBigInt( *this );
689 aTmp1.MultLong(aTmp2, *this);
690 Normalize();
692 return *this;
695 BigInt& BigInt::operator/=( const BigInt& rVal )
697 if ( rVal.nLen == 0 )
699 if ( rVal.nVal == 0 )
701 OSL_FAIL( "BigInt::operator/ --> divide by zero" );
702 return *this;
705 if ( nLen == 0 )
707 // No overflows may occur here
708 nVal /= rVal.nVal;
709 return *this;
712 if ( rVal.nVal == 1 )
713 return *this;
715 if ( rVal.nVal == -1 )
717 bIsNeg = !bIsNeg;
718 return *this;
721 if ( rVal.nVal <= 0xFFFF && rVal.nVal >= -0xFFFF )
723 // Divide BigInt with an sal_uInt16
724 sal_uInt16 nTmp;
725 if ( rVal.nVal < 0 )
727 nTmp = static_cast<sal_uInt16>(-rVal.nVal);
728 bIsNeg = !bIsNeg;
730 else
731 nTmp = static_cast<sal_uInt16>(rVal.nVal);
733 Div( nTmp, nTmp );
734 Normalize();
735 return *this;
739 if ( ABS_IsLess( rVal ) )
741 *this = BigInt( 0 );
742 return *this;
745 // Divide BigInt with BigInt
746 BigInt aTmp1, aTmp2;
747 aTmp1.MakeBigInt( *this );
748 aTmp2.MakeBigInt( rVal );
749 aTmp1.DivLong(aTmp2, *this);
750 Normalize();
751 return *this;
754 BigInt& BigInt::operator%=( const BigInt& rVal )
756 if ( rVal.nLen == 0 )
758 if ( rVal.nVal == 0 )
760 OSL_FAIL( "BigInt::operator/ --> divide by zero" );
761 return *this;
764 if ( nLen == 0 )
766 // No overflows may occur here
767 nVal %= rVal.nVal;
768 return *this;
771 if ( rVal.nVal <= 0xFFFF && rVal.nVal >= -0xFFFF )
773 // Divide Bigint by int16
774 sal_uInt16 nTmp;
775 if ( rVal.nVal < 0 )
777 nTmp = static_cast<sal_uInt16>(-rVal.nVal);
778 bIsNeg = !bIsNeg;
780 else
781 nTmp = static_cast<sal_uInt16>(rVal.nVal);
783 Div( nTmp, nTmp );
784 *this = BigInt( nTmp );
785 return *this;
789 if ( ABS_IsLess( rVal ) )
790 return *this;
792 // Divide BigInt with BigInt
793 BigInt aTmp1, aTmp2;
794 aTmp1.MakeBigInt( *this );
795 aTmp2.MakeBigInt( rVal );
796 aTmp1.ModLong(aTmp2, *this);
797 Normalize();
798 return *this;
801 bool operator==( const BigInt& rVal1, const BigInt& rVal2 )
803 if (rVal1.nLen == 0 && rVal2.nLen == 0)
804 return rVal1.nVal == rVal2.nVal;
806 BigInt nA, nB;
807 nA.MakeBigInt(rVal1);
808 nB.MakeBigInt(rVal2);
809 return nA.bIsNeg == nB.bIsNeg && nA.nLen == nB.nLen
810 && std::equal(nA.nNum, nA.nNum + nA.nLen, nB.nNum);
813 bool operator<( const BigInt& rVal1, const BigInt& rVal2 )
815 if (rVal1.nLen == 0 && rVal2.nLen == 0)
816 return rVal1.nVal < rVal2.nVal;
818 BigInt nA, nB;
819 nA.MakeBigInt(rVal1);
820 nB.MakeBigInt(rVal2);
821 if (nA.bIsNeg != nB.bIsNeg)
822 return !nB.bIsNeg;
823 if (nA.nLen != nB.nLen)
824 return nA.bIsNeg ? (nA.nLen > nB.nLen) : (nA.nLen < nB.nLen);
825 int i = nA.nLen - 1;
826 while (i > 0 && nA.nNum[i] == nB.nNum[i])
827 --i;
828 return nA.bIsNeg ? (nA.nNum[i] > nB.nNum[i]) : (nA.nNum[i] < nB.nNum[i]);
831 tools::Long BigInt::Scale( tools::Long nVal, tools::Long nMul, tools::Long nDiv )
833 BigInt aVal( nVal );
835 aVal *= nMul;
837 if ( aVal.IsNeg() != ( nDiv < 0 ) )
838 aVal -= nDiv / 2; // for correct rounding
839 else
840 aVal += nDiv / 2; // for correct rounding
842 aVal /= nDiv;
844 return tools::Long( aVal );
847 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */