ffead.server.doc
Bigint.cpp
1 /*
2  Copyright 2009-2012, Sumeet Chhetri
3 
4  Licensed under the Apache License, Version 2.0 (the "License");
5  you may not use this file except in compliance with the License.
6  You may obtain a copy of the License at
7 
8  http://www.apache.org/licenses/LICENSE-2.0
9 
10  Unless required by applicable law or agreed to in writing, software
11  distributed under the License is distributed on an "AS IS" BASIS,
12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  See the License for the specific language governing permissions and
14  limitations under the License.
15 */
16 /*
17  * Bigint.cpp
18  *
19  * Created on: 04-Mar-2013
20  * Author: sumeetc
21  */
22 
23 #include "Bigint.h"
24 
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;
32 
33 Bigint::Bigint() {
34  isPositive = true;
35  decimalStartsAt = 0;
36  this->parts.push_back(ZERO_INT);
37 }
38 
39 Bigint::~Bigint() {
40 }
41 
42 Bigint::Bigint(string value)
43 {
44  create(value);
45 }
46 
47 void Bigint::create(string value)
48 {
49  isPositive = true;
50  parts.clear();
51  string temp = StringUtil::trimCopy(value);
52  int minusSign = temp.find_last_of("-");
53  if(minusSign>0)
54  throw "Invalid -";
55  else if(minusSign==0)
56  {
57  isPositive = false;
58  temp = temp.substr(1);
59  }
60  if(temp.find_first_not_of("0")==string::npos)
61  {
62  decimalStartsAt = 0;
63  isPositive = true;
64  this->parts.push_back(ZERO_INT);
65  return;
66  }
67  temp = temp.substr(temp.find_first_not_of("0"));
68  while((int)temp.length()>NUM_LENGTH)
69  {
70  try {
71  int x = CastUtil::lexical_cast<int>(temp.substr(temp.length()-NUM_LENGTH));
72  temp = temp.substr(0, temp.length()-NUM_LENGTH);
73  parts.push_back(x);
74  } catch(...) {
75  throw "Invalid Bigint value";
76  }
77  }
78  if(temp.length()>0)
79  {
80  try {
81  int x = CastUtil::lexical_cast<int>(temp);
82  parts.push_back(x);
83  } catch(...) {
84  throw "Invalid Bigint value";
85  }
86  }
87  if(parts.at(parts.size()-1)==0)
88  parts.erase(parts.begin()+(parts.size()-1));
89  checkAndSetIfZero();
90 }
91 
92 void Bigint::add(Bigint number)
93 {
94  if(isPositive!=number.isPositive)
95  {
96  subtract(number);
97  return;
98  }
99  internalAdd(number);
100 }
101 
102 Bigint Bigint::operator+(Bigint number)
103 {
104  Bigint temp = *this;
105  temp.add(number);
106  return temp;
107 }
108 
109 Bigint Bigint::operator-(Bigint number)
110 {
111  Bigint temp = *this;
112  temp.subtract(number);
113  return temp;
114 }
115 
116 Bigint Bigint::operator*(Bigint number)
117 {
118  Bigint temp = *this;
119  temp.multiply(number);
120  return temp;
121 }
122 
123 Bigint Bigint::operator/(Bigint number)
124 {
125  Bigint temp = *this;
126  temp.divide(number);
127  return temp;
128 }
129 
130 Bigint& Bigint::operator++()
131 {
132  Bigint temp("1");
133  this->add(temp);
134  return *this;
135 }
136 
137 Bigint& Bigint::operator+=(Bigint number)
138 {
139  this->add(number);
140  return *this;
141 }
142 
143 Bigint& Bigint::operator--()
144 {
145  Bigint temp("1");
146  this->subtract(temp);
147  return *this;
148 }
149 
150 Bigint& Bigint::operator-=(Bigint number)
151 {
152  this->subtract(number);
153  return *this;
154 }
155 
156 bool operator==(Bigint &lhs, Bigint &rhs)
157 {
158  if(lhs.compare(rhs)==0)
159  return true;
160  return false;
161 }
162 
163 bool operator!=(Bigint &lhs, Bigint &rhs)
164 {
165  if(lhs.compare(rhs)!=0)
166  return true;
167  return false;
168 }
169 
170 bool operator<(Bigint &lhs, Bigint &rhs)
171 {
172  if(lhs.compare(rhs)==-1)
173  return true;
174  return false;
175 }
176 
177 bool operator<=(Bigint &lhs, Bigint &rhs)
178 {
179  if(lhs.compare(rhs)<=0)
180  return true;
181  return false;
182 }
183 
184 bool operator>(Bigint &lhs, Bigint &rhs)
185 {
186  if(lhs.compare(rhs)==1)
187  return true;
188  return false;
189 }
190 
191 bool operator>=(Bigint &lhs, Bigint &rhs)
192 {
193  if(lhs.compare(rhs)>=0)
194  return true;
195  return false;
196 }
197 
198 void Bigint::internalAdd(Bigint number)
199 {
200  vector<int> nparts;
201  if(parts.size()>0 && number.parts.size()>0)
202  {
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++)
208  {
209  int res = ((int)parts.size()>i?parts.at(i):0) + ( (int)number.parts.size()>i? number.parts.at(i):0) + (carryOver?1:0);
210  if(res>NUM_MAX)
211  {
212  res -= NUM_MAX_THRESHOLD;
213  carryOver = true;
214  }
215  else
216  {
217  carryOver = false;
218  }
219  nparts.push_back(res);
220  }
221  parts = nparts;
222  }
223 }
224 
225 void Bigint::subtract(Bigint number)
226 {
227  if(isPositive!=number.isPositive)
228  {
229  add(number);
230  return;
231  }
232  vector<int> nparts;
233  if(parts.size()>0 && number.parts.size()>0)
234  {
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;
241  if(compValue>=0)
242  {
243  fparts = parts;
244  sparts = number.parts;
245  }
246  else
247  {
248  sparts = parts;
249  fparts = number.parts;
250  }
251  for (int i = 0; i < eqprtssiz; i++)
252  {
253  int res = ((int)fparts.size()>i?fparts.at(i) - (carryOver?1:0):0) - ((int)sparts.size()>i?sparts.at(i):0);
254  if(res<0)
255  {
256  res = NUM_MAX_THRESHOLD - ((int)sparts.size()>i?sparts.at(i):0) + (((int)fparts.size()>i?fparts.at(i) - (carryOver?1:0):0));
257  carryOver = true;
258  }
259  else
260  {
261  carryOver = false;
262  }
263  nparts.push_back(res);
264  }
265  parts = nparts;
266  checkAndSetIfZero();
267  if(compValue<0)
268  {
269  isPositive = false;
270  }
271  }
272 }
273 
274 void Bigint::multiply(Bigint number)
275 {
276  Bigint mulResult;
277  string mstring;
278  vector<int> mparts;
279  string fnvalue = toString();
280  string snvalue = number.toString();
281  if(fnvalue.length()>snvalue.length())
282  {
283  if(!number.isPositive)
284  mstring = snvalue.substr(1);
285  else
286  mstring = snvalue;
287  mparts = parts;
288  }
289  else
290  {
291  if(!number.isPositive)
292  mstring = fnvalue.substr(1);
293  else
294  mstring = fnvalue;
295  mparts = number.parts;
296  }
297  if(mstring!="" && mparts.size()>0)
298  {
299  int position = 0;
300  for (int i = mstring.length(); i > 0 ; i--, position++) {
301  string numstr = BLANK;
302  int mult = mstring.at(i-1) - '0';
303  int carryOver = 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)
307  {
308 
309  string mrtn = CastUtil::lexical_cast<string>(mparts.at(j));
310  if(res.length()>mrtn.length())
311  {
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';
315  }
316  else
317  {
318  int numm = CastUtil::lexical_cast<int>(res) + carryOver;
319  numstr = CastUtil::lexical_cast<string>(numm) + numstr;
320  carryOver = 0;
321  }
322  if(j==0)
323  {
324  int nl = numstr.length();
325  for (int jj = 0; jj < NUM_LENGTH-nl; jj++) {
326  numstr = ZERO + numstr;
327  }
328  }
329  }
330  else
331  {
332  int numm = CastUtil::lexical_cast<int>(res) + carryOver;
333  numstr = CastUtil::lexical_cast<string>(numm) + numstr;
334  carryOver = 0;
335  }
336  }
337  for (int j = 0; j < position; j++) {
338  numstr += ZERO;
339  }
340  try {
341  Bigint num(numstr);
342  mulResult.internalAdd(num);
343  } catch (...) {
344  }
345  }
346  }
347  this->parts = mulResult.parts;
348  if(isPositive!=number.isPositive)
349  {
350  isPositive = false;
351  }
352  else if(isPositive==number.isPositive)
353  {
354  isPositive = true;
355  }
356 }
357 
358 void Bigint::divide(Bigint number)
359 {
360  internalDivide(number, false, 1);
361 }
362 
363 void Bigint::internalDivide(Bigint number, bool isDecimal, int precision)
364 {
365  string mstring;
366  vector<int> mparts;
367  string fnvalue = toString();
368  string snvalue = number.toString();
369  if(fnvalue.length()>snvalue.length())
370  {
371  if(!number.isPositive)
372  mstring = snvalue.substr(1);
373  else
374  mstring = snvalue;
375  mparts = parts;
376  }
377  else
378  {
379  if(!number.isPositive)
380  mstring = fnvalue.substr(1);
381  else
382  mstring = fnvalue;
383  mparts = number.parts;
384  }
385  if(mstring!="" && mparts.size()>0)
386  {
387  int recurse = 0;
388  string build;
389  decompose(fnvalue, snvalue, number, recurse, build, isDecimal, precision);
390  try {
391  create(build);
392  } catch (...) {
393  }
394  }
395 }
396 
397 int Bigint::decompose(string fnvalue, string snvalue, Bigint number, int recurse, string& build, bool isDecimal, int precision)
398 {
399  if(recurse>=precision || fnvalue==BLANK)return recurse;
400  string fntemp;
401  int diff = fnvalue.length() - snvalue.length();
402  if(diff>0)
403  {
404  fntemp = fnvalue.substr(0, snvalue.length());
405  int len = snvalue.length();
406  try {
407  Bigint fntmp(fntemp);
408  while(fntmp.compare(number)==-1)
409  {
410  len++;
411  fntemp = fnvalue.substr(0, len);
412  fntmp.create(fntemp);
413  }
414  } catch (...) {
415  }
416  }
417  else if(diff<0)
418  {
419  diff = -diff;
420  for (int i = 0; i < diff+1; i++) {
421  fnvalue += ZERO;
422  if(recurse==0 || (recurse>0 && i>0))
423  {
424  build.append(ZERO);
425  if(recurse==0)
426  {
427  if(!isDecimal)
428  {
429  recurse = 15;
430  return recurse;
431  }
432  else
433  {
434  recurse++;
435  decimalStartsAt = build.length();
436  }
437  }
438  else
439  recurse++;
440  }
441  Bigint fntmp(fnvalue);
442  if(fntmp.compare(number)==1)
443  break;
444  }
445  fntemp = fnvalue;
446  }
447  else
448  {
449  Bigint fntmp(fnvalue);
450  if(fntmp.compare(number)==-1)
451  {
452  fnvalue += ZERO;
453  Bigint fntmp(fnvalue);
454  if(recurse==0)
455  {
456  if(!isDecimal)
457  {
458  recurse = 15;
459  return recurse;
460  }
461  else
462  {
463  decimalStartsAt = build.length();
464  recurse++;
465  }
466  }
467  else
468  recurse++;
469  }
470  fntemp = fnvalue;
471  }
472  fnvalue = fnvalue.substr(snvalue.length());
473  try {
474  Bigint fbtemp(fntemp);
475  int quotient = 0;
476  while(fbtemp.compare(number)>=0)
477  {
478  quotient++;
479  fbtemp.subtract(number);
480  }
481  if(quotient>0)
482  {
483  build.append(CastUtil::lexical_cast<string>(quotient));
484  }
485  if(fnvalue=="")
486  {
487  if(isDecimal)
488  {
489  if(recurse==0)
490  {
491  decimalStartsAt = build.length();
492  recurse++;
493  }
494  else
495  recurse++;
496  }
497  else
498  {
499  recurse = 15;
500  }
501  }
502  recurse = decompose((fbtemp.toString()==ZERO?"":fbtemp.toString()) + fnvalue, snvalue, number, recurse, build, isDecimal, precision);
503  } catch (...) {
504  // TODO Auto-generated catch block
505  }
506  return recurse;
507 }
508 
509 void Bigint::checkAndSetIfZero()
510 {
511  bool flag = false;
512  for (int i=0;i<(int)parts.size();i++) {
513  if(parts.at(i)>0)
514  {
515  flag = true;
516  break;
517  }
518  }
519  if(!flag || parts.size()==0)
520  {
521  parts.clear();
522  this->parts.push_back(ZERO_INT);
523  isPositive = true;
524  }
525 }
526 
527 int Bigint::compare(Bigint number1, Bigint number2)
528 {
529  return number1.compare(number2);
530 }
531 
532 int Bigint::compare(Bigint number)
533 {
534  if(isPositive==number.isPositive)
535  {
536  if(parts.size()==number.parts.size())
537  {
538  if(parts.at(parts.size()-1)==number.parts.at(parts.size()-1))
539  {
540  return 0;
541  }
542  else if(parts.at(parts.size()-1)>number.parts.at(parts.size()-1))
543  {
544  return 1;
545  }
546  else
547  {
548  return -1;
549  }
550  }
551  else if(parts.size()>number.parts.size())
552  {
553  return 1;
554  }
555  else
556  {
557  return -1;
558  }
559  }
560  else if(isPositive && !number.isPositive)
561  {
562  return 1;
563  }
564  else
565  {
566  return -1;
567  }
568 }
569 
570 string Bigint::toString()
571 {
572  if(parts.size()==0)
573  return ZERO;
574  string build;
575  vector<int> nparts = parts;
576  std::reverse(nparts.begin(),nparts.end());
577  if(!isPositive)
578  {
579  build.append(MINUS);
580  }
581  for (int i=0;i<(int)nparts.size();i++) {
582  if(i!=0)
583  {
584  string numstr = CastUtil::lexical_cast<string>(nparts.at(i));
585  for (int j = 0; j < NUM_LENGTH-(int)numstr.length(); j++) {
586  build.append(ZERO);
587  }
588  build.append(numstr);
589  }
590  else
591  {
592  build.append(CastUtil::lexical_cast<string>(nparts.at(i)));
593  }
594  }
595  return build;
596 }