25 string Bigint::BLANK =
"";
26 string Bigint::MINUS =
"-";
27 string Bigint::ZERO =
"0";
28 int Bigint::ZERO_INT = 0L;
29 int Bigint::NUM_LENGTH = 8;
30 int Bigint::NUM_MAX = 99999999;
31 int Bigint::NUM_MAX_THRESHOLD = 100000000;
36 this->parts.push_back(ZERO_INT);
42 Bigint::Bigint(
string value)
47 void Bigint::create(
string value)
51 string temp = StringUtil::trimCopy(value);
52 int minusSign = temp.find_last_of(
"-");
58 temp = temp.substr(1);
60 if(temp.find_first_not_of(
"0")==string::npos)
64 this->parts.push_back(ZERO_INT);
67 temp = temp.substr(temp.find_first_not_of(
"0"));
68 while((
int)temp.length()>NUM_LENGTH)
71 int x = CastUtil::lexical_cast<
int>(temp.substr(temp.length()-NUM_LENGTH));
72 temp = temp.substr(0, temp.length()-NUM_LENGTH);
75 throw "Invalid Bigint value";
81 int x = CastUtil::lexical_cast<
int>(temp);
84 throw "Invalid Bigint value";
87 if(parts.at(parts.size()-1)==0)
88 parts.erase(parts.begin()+(parts.size()-1));
92 void Bigint::add(
Bigint number)
94 if(isPositive!=number.isPositive)
112 temp.subtract(number);
119 temp.multiply(number);
130 Bigint& Bigint::operator++()
143 Bigint& Bigint::operator--()
146 this->subtract(temp);
152 this->subtract(number);
158 if(lhs.compare(rhs)==0)
165 if(lhs.compare(rhs)!=0)
172 if(lhs.compare(rhs)==-1)
179 if(lhs.compare(rhs)<=0)
186 if(lhs.compare(rhs)==1)
193 if(lhs.compare(rhs)>=0)
198 void Bigint::internalAdd(
Bigint number)
201 if(parts.size()>0 && number.parts.size()>0)
203 int eqprtssiz = parts.size();
204 if(eqprtssiz<(
int)number.parts.size())
205 eqprtssiz = number.parts.size();
206 bool carryOver =
false;
207 for (
int i = 0; i < eqprtssiz; i++)
209 int res = ((int)parts.size()>i?parts.at(i):0) + ( (
int)number.parts.size()>i? number.parts.at(i):0) + (carryOver?1:0);
212 res -= NUM_MAX_THRESHOLD;
219 nparts.push_back(res);
225 void Bigint::subtract(
Bigint number)
227 if(isPositive!=number.isPositive)
233 if(parts.size()>0 && number.parts.size()>0)
235 int eqprtssiz = parts.size();
236 if(eqprtssiz<(
int)number.parts.size())
237 eqprtssiz = number.parts.size();
238 bool carryOver =
false;
239 int compValue = compare(number);
240 vector<int> fparts, sparts;
244 sparts = number.parts;
249 fparts = number.parts;
251 for (
int i = 0; i < eqprtssiz; i++)
253 int res = ((int)fparts.size()>i?fparts.at(i) - (carryOver?1:0):0) - ((int)sparts.size()>i?sparts.at(i):0);
256 res = NUM_MAX_THRESHOLD - ((int)sparts.size()>i?sparts.at(i):0) + (((
int)fparts.size()>i?fparts.at(i) - (carryOver?1:0):0));
263 nparts.push_back(res);
274 void Bigint::multiply(
Bigint number)
279 string fnvalue = toString();
280 string snvalue = number.toString();
281 if(fnvalue.length()>snvalue.length())
283 if(!number.isPositive)
284 mstring = snvalue.substr(1);
291 if(!number.isPositive)
292 mstring = fnvalue.substr(1);
295 mparts = number.parts;
297 if(mstring!=
"" && mparts.size()>0)
300 for (
int i = mstring.length(); i > 0 ; i--, position++) {
301 string numstr = BLANK;
302 int mult = mstring.at(i-1) -
'0';
304 for (
int j=0;j<(int)mparts.size();j++) {
305 string res = CastUtil::lexical_cast<
string>(mparts.at(j)*mult);
306 if(j!=(
int)mparts.size()-1)
309 string mrtn = CastUtil::lexical_cast<
string>(mparts.at(j));
310 if(res.length()>mrtn.length())
312 int numm = CastUtil::lexical_cast<
int>(res.substr(1)) + carryOver;
313 numstr = CastUtil::lexical_cast<
string>(numm) + numstr;
314 carryOver = res.at(0) -
'0';
318 int numm = CastUtil::lexical_cast<
int>(res) + carryOver;
319 numstr = CastUtil::lexical_cast<
string>(numm) + numstr;
324 int nl = numstr.length();
325 for (
int jj = 0; jj < NUM_LENGTH-nl; jj++) {
326 numstr = ZERO + numstr;
332 int numm = CastUtil::lexical_cast<
int>(res) + carryOver;
333 numstr = CastUtil::lexical_cast<
string>(numm) + numstr;
337 for (
int j = 0; j < position; j++) {
342 mulResult.internalAdd(num);
347 this->parts = mulResult.parts;
348 if(isPositive!=number.isPositive)
352 else if(isPositive==number.isPositive)
358 void Bigint::divide(
Bigint number)
360 internalDivide(number,
false, 1);
363 void Bigint::internalDivide(
Bigint number,
bool isDecimal,
int precision)
367 string fnvalue = toString();
368 string snvalue = number.toString();
369 if(fnvalue.length()>snvalue.length())
371 if(!number.isPositive)
372 mstring = snvalue.substr(1);
379 if(!number.isPositive)
380 mstring = fnvalue.substr(1);
383 mparts = number.parts;
385 if(mstring!=
"" && mparts.size()>0)
389 decompose(fnvalue, snvalue, number, recurse, build, isDecimal, precision);
397 int Bigint::decompose(
string fnvalue,
string snvalue,
Bigint number,
int recurse,
string& build,
bool isDecimal,
int precision)
399 if(recurse>=precision || fnvalue==BLANK)
return recurse;
401 int diff = fnvalue.length() - snvalue.length();
404 fntemp = fnvalue.substr(0, snvalue.length());
405 int len = snvalue.length();
408 while(fntmp.compare(number)==-1)
411 fntemp = fnvalue.substr(0, len);
412 fntmp.create(fntemp);
420 for (
int i = 0; i < diff+1; i++) {
422 if(recurse==0 || (recurse>0 && i>0))
435 decimalStartsAt = build.length();
442 if(fntmp.compare(number)==1)
450 if(fntmp.compare(number)==-1)
463 decimalStartsAt = build.length();
472 fnvalue = fnvalue.substr(snvalue.length());
476 while(fbtemp.compare(number)>=0)
479 fbtemp.subtract(number);
483 build.append(CastUtil::lexical_cast<string>(quotient));
491 decimalStartsAt = build.length();
502 recurse = decompose((fbtemp.toString()==ZERO?
"":fbtemp.toString()) + fnvalue, snvalue, number, recurse, build, isDecimal, precision);
509 void Bigint::checkAndSetIfZero()
512 for (
int i=0;i<(int)parts.size();i++) {
519 if(!flag || parts.size()==0)
522 this->parts.push_back(ZERO_INT);
529 return number1.compare(number2);
532 int Bigint::compare(
Bigint number)
534 if(isPositive==number.isPositive)
536 if(parts.size()==number.parts.size())
538 if(parts.at(parts.size()-1)==number.parts.at(parts.size()-1))
542 else if(parts.at(parts.size()-1)>number.parts.at(parts.size()-1))
551 else if(parts.size()>number.parts.size())
560 else if(isPositive && !number.isPositive)
570 string Bigint::toString()
575 vector<int> nparts = parts;
576 std::reverse(nparts.begin(),nparts.end());
581 for (
int i=0;i<(int)nparts.size();i++) {
584 string numstr = CastUtil::lexical_cast<
string>(nparts.at(i));
585 for (
int j = 0; j < NUM_LENGTH-(int)numstr.length(); j++) {
588 build.append(numstr);
592 build.append(CastUtil::lexical_cast<string>(nparts.at(i)));