API tools faq
paste
Advertisement
Guest User

Untitled

a guest
May 27th, 2018
70
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 14.18 KB | None | 0 0
raw download clone embed print report
  1. //============================================================================
  2. // Name : BigInteger.cpp
  3. // Author : Oskar Pawica
  4. // Version : 1.0
  5. // Copyright : Your copyright notice
  6. // Description : BigInteger in C++, Ansi-style
  7. //============================================================================
  8.  
  9. #include <iostream>
  10. #include <cmath>
  11. #include <algorithm>
  12. #include <cstdlib>
  13. #include <stdio.h>
  14. #include <string.h>
  15. #include <limits>
  16.  
  17. using namespace std;
  18.  
  19. class Exception {
  20. std::string name;
  21. public:
  22. Exception (std::string n) : name(n){}
  23. virtual ~Exception() {}
  24. virtual std::string get_name () { return name; }
  25. };
  26.  
  27. class DivBy0Exception : public Exception {
  28. public:
  29. DivBy0Exception () : Exception("Nie mozna dzielic przez 0!") {}
  30. virtual ~DivBy0Exception () {}
  31. };
  32.  
  33. class BigInteger
  34. {
  35. private:
  36. long size;
  37. char* e;
  38.  
  39. BigInteger multiply(const char& c, const unsigned int& m) const {
  40. if(c=='0' or e[0] == '0') {
  41. BigInteger temp_null('0');
  42. return temp_null;
  43. }
  44. BigInteger temp(this->size+1+m, true);
  45. temp.e = new char[this->size+1+m];
  46. memcpy(temp.e+1+m, this->e+1, size-1);
  47. temp.e[0] = '+';
  48. for(unsigned int j = 1; j<=m; ++j) {
  49. temp.e[j] = '0';
  50. }
  51. temp.e[temp.size-1] = '0';
  52. unsigned int r=0, temp_res;
  53. for(unsigned int i = 1; i<size; ++i) {
  54. temp_res = (e[i]-48)*(c-48)+r;
  55. temp.e[i+m] = (temp_res%10)+48;
  56. r = temp_res/10;
  57. }
  58. if(r == 0)
  59. temp = temp.check_zeros();
  60. else
  61. temp.e[temp.size-1] = r+48;
  62. temp = temp.check_zeros();
  63. return temp;
  64. }
  65.  
  66. public:
  67. BigInteger() : size(0), e(NULL) {}
  68. BigInteger(long a){
  69. size = 1;
  70. if(a == 0)
  71. {
  72. e = new char[size];
  73. *e = '0';
  74. }
  75. else
  76. {
  77. size += numberOfDigits(abs(a));
  78. e = new char [size];
  79. if(a > 0)
  80. *e = '+';
  81. else {
  82. *e = '-';
  83. a = -a;
  84. }
  85. int i = 1;
  86. while(a >= 1)
  87. {
  88. sprintf(e+i, "%ld", a%10);
  89. a/=10;
  90. i++;
  91. }
  92. }
  93. }
  94. BigInteger(long ssize, bool): size(ssize), e(NULL) {}
  95.  
  96. BigInteger(const char* a){
  97. size = 1;
  98. if(*a == '0'){
  99. e = new char [size];
  100. *e = '0';
  101. }
  102. else
  103. {
  104. char j;
  105. int i = 0;
  106. if(*a == '+' or *a == '-') {
  107. j = *a;
  108. i++;
  109. }
  110. else {
  111. j = '+';
  112. }
  113. while(*(a+i)>=48 and *(a+i)<=57) {
  114. size++;
  115. i++;
  116. }
  117. e = new char [size];
  118. *e = j;
  119. i--;
  120. int k = 1;
  121. while(*(a+i)>=48 and *(a+i)<=57) {
  122. *(e+k) = *(a+i);
  123. i--;
  124. k++;
  125. }
  126. }
  127.  
  128. }
  129.  
  130. virtual ~BigInteger()
  131. {
  132. delete [] e;
  133. }
  134.  
  135. BigInteger (const BigInteger &b):size(b.size)
  136. {
  137. e = new char[b.size];
  138. strcpy(e, b.e);
  139. }
  140.  
  141. BigInteger &operator =(const BigInteger &b)
  142. {
  143. size = b.size;
  144. if (e!=NULL)
  145. delete [] e;
  146. e = new char [size];
  147. memcpy(e,b.e,size*sizeof(char));
  148. return *this;
  149. }
  150.  
  151. BigInteger &operator =(long a)
  152. {
  153. size = 1;
  154. if (e!=NULL)
  155. delete [] e;
  156. if(a == 0)
  157. {
  158. e = new char[size];
  159. *e = '0';
  160. }
  161. else
  162. {
  163. size += numberOfDigits(abs(a));
  164. e = new char [size];
  165. if(a > 0)
  166. *e = '+';
  167. else {
  168. *e = '-';
  169. a = -a;
  170. }
  171. int i = 1;
  172. while(a >= 1)
  173. {
  174. sprintf(e+i, "%ld", a%10);
  175. a/=10;
  176. i++;
  177. }
  178. }
  179. return *this;
  180. }
  181.  
  182. bool operator ==(const BigInteger &b) const
  183. {
  184. if(this->size != b.size)
  185. return 0;
  186. for (int i = 0; i < size; i++)
  187. if(this->e[i]!=b.e[i])
  188. return 0;
  189. return 1;
  190. }
  191.  
  192. bool operator !=(const BigInteger &b) const
  193. {
  194. if(this->size != b.size)
  195. return 1;
  196. for (int i = 0; i < size; i++)
  197. if(this->e[i]!=b.e[i])
  198. return 1;
  199. return 0;
  200. }
  201.  
  202. bool operator >(const BigInteger &b) const
  203. {
  204. if(*this == b)
  205. return 0;
  206. if(this->e[0]!=b.e[0]) {
  207.  
  208. if(this->e[0] == '+')
  209. return 1;
  210. else
  211. return 0;
  212. }
  213. if(this->size > b.size)
  214. if(this->e[0] == '+')
  215. return 1;
  216. else
  217. return 0;
  218. else if (this->size < b.size)
  219. if(this->e[0] == '+')
  220. return 0;
  221. else
  222. return 1;
  223. else
  224. {
  225. bool left = false;
  226. int s = size-1;
  227. for (int i = s; i > 0; --i) {
  228. if (this->e[i] == b.e[i])
  229. continue;
  230. if(this->e[i] > b.e[i])
  231. {
  232. left = true;
  233. break;
  234. }
  235. else
  236. break;
  237. }
  238. if(left)
  239. {
  240. if(this->e[0] == '+')
  241. return 1;
  242. else
  243. return 0;
  244. }
  245. else
  246. {
  247. if(this->e[0] == '+')
  248. return 0;
  249. else
  250. return 1;
  251. }
  252.  
  253. }
  254. }
  255.  
  256. bool operator <(const BigInteger &b) const
  257. {
  258. return b > (*this);
  259. }
  260.  
  261. bool operator >=(const BigInteger &b) const
  262. {
  263. if(*this==b)
  264. return 1;
  265. if(*this>b)
  266. return 1;
  267. return 0;
  268. }
  269.  
  270. bool operator <=(const BigInteger &b) const
  271. {
  272. if(*this==b) {
  273. return 1;
  274. }
  275. if(*this<b){
  276. return 1;}
  277. return 0;
  278. }
  279.  
  280. BigInteger operator +(const BigInteger &b) const
  281. {
  282. if(e[0] == '0')
  283. return b;
  284. if(b.e[0] == '0')
  285. return *this;
  286. if(e[0] == '-' and b.e[0] != '-')
  287. return b - (-(*this));
  288. if(b.e[0] == '-' and e[0] != '-')
  289. return (*this)-(-b);
  290. if(size<b.size)
  291. return b+(*this);
  292.  
  293. BigInteger temp(this->size, true);
  294. temp.e = new char [this->size];
  295. temp.e[0] = '+';
  296. unsigned int i = 1;
  297. char temp_c;
  298. bool t = false;
  299. while (i<strlen(b.e)) {
  300. temp_c = this->e[i]+b.e[i]-48;
  301. if(t) {
  302. temp_c+=1;
  303. t = false;
  304. }
  305. if(temp_c-48 >= 10) {
  306. temp_c = (temp_c-48)%10+48;
  307. t = true;
  308. }
  309. temp.e[i] = temp_c;
  310. ++i;
  311. }
  312. if (i<strlen(this->e)) {
  313. memcpy(temp.e+i, e+i, strlen(this->e)-i);
  314. if(t) {
  315. temp.e[i]+=1;
  316. if(temp.e[i]>57) {
  317. temp.e[i] = '0';
  318. }
  319. else
  320. t = false;
  321. }
  322. }
  323. if(b.e[0] == '-' and e[0] == '-') {
  324. temp.e[0] = '-';
  325. temp = temp.check_zeros();
  326. }
  327. if(t) {
  328. BigInteger temp2(temp.size+1, true);
  329. temp2.e = new char [temp.size+1];
  330. memcpy(temp2.e, temp.e, strlen(temp.e));
  331. temp2.e[size] = '1';
  332. return temp2;
  333. }
  334. else
  335. return temp;
  336. }
  337.  
  338. BigInteger operator +(const long &a) const {
  339. BigInteger temp(a);
  340. return *this+temp;
  341. }
  342.  
  343. BigInteger &operator +=(const BigInteger &b)
  344. {
  345. *this = *this+b;
  346. return *this;
  347. }
  348.  
  349. BigInteger &operator *=(const BigInteger &b)
  350. {
  351. *this = *this*b;
  352. return *this;
  353. }
  354.  
  355. BigInteger &operator /=(const BigInteger &b)
  356. {
  357. *this = *this/b;
  358. return *this;
  359. }
  360.  
  361. BigInteger &operator %=(const BigInteger &b)
  362. {
  363. *this = *this%b;
  364. return *this;
  365. }
  366.  
  367. BigInteger &operator -=(BigInteger &b)
  368. {
  369. *this = *this-b;
  370. return *this;
  371. }
  372.  
  373. BigInteger &operator +=(const long &b)
  374. {
  375. *this = *this+b;
  376. return *this;
  377. }
  378.  
  379. BigInteger &operator *=(const long &b)
  380. {
  381. *this = *this*b;
  382. return *this;
  383. }
  384.  
  385. BigInteger &operator /=(const long &b)
  386. {
  387. *this = *this/b;
  388. return *this;
  389. }
  390.  
  391. BigInteger &operator %=(const long &b)
  392. {
  393. *this = *this%b;
  394. return *this;
  395. }
  396.  
  397. BigInteger &operator -=(const long &b)
  398. {
  399. *this = *this-b;
  400. return *this;
  401. }
  402.  
  403. BigInteger operator -(const BigInteger &b) const
  404. {
  405. if (this->e[0] == '0')
  406. return -b;
  407. if (b.e[0] == '0')
  408. return *this;
  409. if (*this == b)
  410. {
  411. BigInteger temp_null('0');
  412. return temp_null;
  413. }
  414. if(b.e[0] == '-' and e[0] != '-')
  415. return *this+(-b);
  416. if(e[0] == '-' and b.e[0] != '-')
  417. return (*this)+(-b);
  418. if(e[0] == '-' and b.e[0] == '-')
  419. return (-b)+(*this);
  420.  
  421. BigInteger temp;
  422. if(*this < b) {
  423. temp = b - *this;
  424. return -temp;
  425. }
  426. temp = *this;
  427. char temp_c;
  428. unsigned int i;
  429. for(i = 1; i < b.size; ++i) {
  430. temp_c = e[i]-b.e[i]+48;
  431. if (temp_c < 48) {
  432. temp_c+=10;
  433. --e[i+1];
  434. for(unsigned int k = i+1; k < this->size-1; ++k) {
  435. if(e[k]>='0')
  436. break;
  437. else {
  438. e[k] = '9';
  439. --e[k+1];
  440. }
  441. }
  442. }
  443. temp.e[i] = temp_c;
  444. }
  445. while(i<size) {
  446. temp.e[i] = e[i];
  447. ++i;
  448. }
  449. temp = temp.check_zeros();
  450. return temp;
  451. }
  452.  
  453. BigInteger operator/(const BigInteger& b) const {
  454. if(b.e[0] == '0')
  455. throw DivBy0Exception();
  456. bool negative = true;
  457. if(e[0] == b.e[0])
  458. negative = false;
  459. BigInteger origin(*this);
  460. origin.e[0] = '+';
  461. b.e[0] = '+';
  462. BigInteger temp_r(RAND_MAX);
  463. if (temp_r*b<*this) {
  464. return over_rand(b, negative);
  465. }
  466. long long temp_l = rand();
  467. BigInteger temp(temp_l);
  468. bool one, two;
  469. while(1) {
  470. temp = temp_l;
  471. if(temp_l > RAND_MAX)
  472. return over_rand(b, negative);
  473. one = b*temp <= origin;
  474. two = b*(temp+1) > origin;
  475. if(one and two)
  476. break;
  477. if(!one) {
  478. temp_l = rand()%temp_l;
  479. continue;
  480. }
  481. if(one) {
  482. temp_l = temp_l+rand();
  483. continue;
  484. }
  485. }
  486. if(negative)
  487. return -temp;
  488. else return temp;
  489. }
  490.  
  491. BigInteger over_rand(const BigInteger& b, const bool& negative) const {
  492. BigInteger temp(RAND_MAX);
  493. bool one, two;
  494. while(1) {
  495. one = b*temp <= *this;
  496. two = b*(temp+1) > *this;
  497. if(one and two)
  498. break;
  499. else
  500. temp+=1;
  501. }
  502. if (negative)
  503. return -temp;
  504. return temp;
  505. }
  506.  
  507. BigInteger operator%(const BigInteger& b) const {
  508. if(b>*this)
  509. return *this;
  510. BigInteger temp(*this/b);
  511. return *this-(temp*b);
  512. }
  513.  
  514. BigInteger operator%(const long& a) const {
  515. BigInteger temp(a);
  516. return *this%temp;
  517. }
  518.  
  519. BigInteger operator/(const long& a) const {
  520. if(a == 0)
  521. throw DivBy0Exception();
  522. BigInteger temp(a);
  523. return *this/temp;
  524. }
  525.  
  526. BigInteger operator*(const BigInteger& b) const {
  527. if(b.e[0] == '0' or e[0] == '0')
  528. {
  529. BigInteger temp_null('0');
  530. return temp_null;
  531. }
  532. if(b.size > this->size)
  533. return b*(*this);
  534. bool negative = false;
  535. if(b.e[0]!=e[0])
  536. negative = true;
  537. if(b.e[1] == '1' and b.size==2) {
  538. if(negative)
  539. return -(*this);
  540. else
  541. return *this;
  542. }
  543. else if(e[1] == '1' and size==2) {
  544. if(negative)
  545. return -(b);
  546. else return b;
  547. }
  548. BigInteger temp [b.size-1];
  549. for(unsigned int i = 1; i < b.size; ++i) {
  550. temp[i-1] = multiply(b.e[i], i-1);
  551. }
  552. for(unsigned int i = 1; i < b.size-1; ++i)
  553. temp[0] = temp[i] + temp[0];
  554. if(negative)
  555. temp[0].e[0] = '-';
  556. return temp[0];
  557.  
  558. }
  559.  
  560. BigInteger check_zeros() {
  561. if(e[size-1] == '0') {
  562. unsigned int zeros = 1;
  563. for(unsigned int i = size-2; i > 0; --i) {
  564. if(e[i] == '0')
  565. ++zeros;
  566. else
  567. break;
  568. }
  569. BigInteger temp(size-zeros, true);
  570. temp.e = new char [size-zeros];
  571. memcpy(temp.e, this->e, strlen(e)-zeros);
  572. return temp;
  573. }
  574. return *this;
  575. }
  576.  
  577. BigInteger operator -(const long &b) const
  578. {
  579. BigInteger temp(b);
  580. return *this-temp;
  581. }
  582.  
  583. BigInteger operator *(const long &b) const
  584. {
  585. BigInteger temp(b);
  586. return *this*temp;
  587. }
  588.  
  589. BigInteger operator ++(int)
  590. {
  591. BigInteger temp(*this);
  592. *this+=1;
  593. return temp;
  594. }
  595.  
  596. BigInteger &operator ++()
  597. {
  598. *this+=1;
  599. return *this;
  600. }
  601.  
  602. BigInteger operator --(int)
  603. {
  604. BigInteger temp(*this);
  605. *this-=1;
  606. return temp;
  607. }
  608.  
  609. BigInteger &operator --()
  610. {
  611. *this-=1;
  612. return *this;
  613. }
  614.  
  615. BigInteger operator -() const
  616. {
  617. if(e[0]=='0')
  618. return *this;
  619. BigInteger temp = *this;
  620. temp.e[0]=='+' ? temp.e[0] ='-' : temp.e[0] ='+';
  621. return temp;
  622. }
  623. /*
  624. char &operator [] (const int &b) const
  625. {
  626. return e[size-1-b];
  627. }
  628. */
  629. char &operator [] (const int &b) const
  630. {
  631. return e[b+1];
  632. }
  633.  
  634. long numberOfDigits(const long& a) const {
  635.  
  636. if(a<=9){
  637. return 1;
  638. }
  639. return 1 + numberOfDigits(a/10);
  640. }
  641.  
  642. friend ostream& operator <<(ostream& os, const BigInteger& b);
  643. friend istream& operator >>(istream& is, BigInteger& b);
  644. };
  645.  
  646. ostream& operator<<(ostream& os, const BigInteger& b)
  647. {
  648. if (b.e[0] == '0')
  649. os << '0';
  650. else {
  651. if (b.e[0] == '-')
  652. os << '-';
  653. for (int i = b.size-1; i > 0; --i)
  654. os << b.e[i];
  655. }
  656. return os;
  657. }
  658.  
  659. istream& operator>>(istream& is, BigInteger& b)
  660. {
  661. string s;
  662. is >> s;
  663. const char * temp = s.c_str();
  664. BigInteger b_temp(temp);
  665. b = b_temp;
  666. return is;
  667. }
  668.  
  669. BigInteger operator +(const long& a, const BigInteger& b)
  670. {
  671. return b+a;
  672. }
  673.  
  674. BigInteger operator -(const long& a, const BigInteger& b)
  675. {
  676. BigInteger temp(a);
  677. return temp-b;
  678. }
  679.  
  680. BigInteger operator *(const long& a, const BigInteger& b)
  681. {
  682. BigInteger temp(a);
  683. return temp*b;
  684. }
  685.  
  686. BigInteger operator /(const long& a, const BigInteger& b)
  687. {
  688. BigInteger temp(a);
  689. return temp/b;
  690. }
  691.  
  692. BigInteger operator %(const long& a, const BigInteger& b)
  693. {
  694. BigInteger temp(a);
  695. return temp%b;
  696. }
  697.  
  698. int main() {
  699. {
  700. try {
  701. srand(time(NULL));
  702. BigInteger test(5720);
  703. BigInteger test2(715);
  704. std::cout<<test2<<std::endl;
  705. std::cout<<(test<test2)<<std::endl;
  706. std::cout<<test<<std::endl;
  707. test = test+test2;;
  708. std::cout<<test<<std::endl;
  709.  
  710. std::cout<<"----"<<std::endl;
  711. long a = -1;
  712. char b[] = "-145";
  713. BigInteger x = a;
  714. BigInteger y = b;
  715. std::cout<<x<<" "<<y<<std::endl;
  716. std::cout<<y<<std::endl;
  717. BigInteger z = x+(y++);
  718. std::cout<<y<<std::endl;
  719. std::cout<<z<<std::endl;
  720. z = z+100;
  721. std::cout<<z+z<<std::endl;
  722. std::cout<<y<<std::endl;
  723. std::cout<<2+y<<std::endl;
  724. std::cout<<y<<std::endl;
  725. std::cout<<x<<std::endl;
  726. y = x-y;
  727. std::cout<<y<<std::endl;
  728. std::cout<<y*45<<std::endl;
  729. std::cout<<y/45<<std::endl;
  730. } catch (Exception& e) {
  731. std::cerr<<"Wystapil blad. "<<e.get_name()<<std::endl;
  732. std::abort();
  733. }
  734. }
  735. std::cout<<"End."<<std::endl;
  736. return 0;
  737. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!