API tools faq
paste
Advertisement
najim

BigInteger Library_update2

najim
Mar 17th, 2014
186
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 12.42 KB | None | 0 0
raw download clone embed print report
  1. /****************** BIG INT LIBRARY *****************************
  2. getint()               : makes a new Biginteger from a int
  3. Bigint()               : Constructor
  4. Bigint(string b)       : Constructs a Biginteger from a string
  5. size()                 : returns length of Biginteger
  6. inverseSign()          : return the inverse of Biginteger
  7. normalize()            : removes leading 0 and changes the sign
  8. operator=              : available for int/Biginteger
  9. operator<              : available for int/Biginteger
  10. operator==             : available for int/Biginteger
  11. operator+              : available for int/Biginteger
  12. operator-              : available for int/Biginteger
  13. operator*              : available for int/Biginteger
  14. operator/              : available for int/Biginteger
  15. operator%              : available for int/Biginteger
  16. print()                : prints the Biginteger
  17. sqrt()                 : returns the sqrt in the neares int
  18. ******************************************************************/
  19. #include <cstdio>
  20. #include <cstdlib>
  21. #include <cstring>
  22. #include <cmath>
  23. #include <cassert>
  24. #include <algorithm>
  25. #include <vector>
  26. #include <iostream>
  27. #include <complex>
  28. using namespace std;
  29. #define BIT 10009
  30. #define GRP     5
  31. #define RADIX   100000  // 10^GRP
  32. #define PI         2.0*acos(0.0)
  33. typedef complex<long double> Complex;
  34.  
  35. unsigned revtab[65536];
  36. char mid_man[4000000];  //modify this in case of mle
  37. void init(){
  38.     for (int x = 0; x < 65536; x++){
  39.         int y = 0;
  40.         for (int i = 0; i < 16; i++)y |= ((x >> i) & 1) << (15 - i);
  41.         revtab[x] = y;
  42.     }
  43. }
  44. void FFT(Complex *a, int N, int dir){
  45.     int lgN;
  46.     for (lgN = 1; (1 << lgN) < N; lgN++);
  47.     assert((1 << lgN) == N);
  48.     for (unsigned i = 0; i < N; i++){
  49.         unsigned j = ((revtab[i & 65535] << 16) | revtab[i >> 16]) >> (32 - lgN);
  50.         if (i < j) swap(a[i], a[j]);
  51.     }
  52.     for (int s = 1; s <= lgN; s++){
  53.         int m = 1 << s, h = m/2;
  54.         Complex w, w_m = exp(Complex(0, dir*2*PI/m));
  55.         for (int k = 0; k < N; k += m){
  56.             w = 1;
  57.             for (int j = 0; j < h; j++){
  58.                 Complex t = w * a[k+h+j];
  59.                 a[k+h+j] = a[k+j] - t;
  60.                 a[k+j] += t;
  61.                 w *= w_m;
  62.             }
  63.         }
  64.     }
  65. }
  66. void parse(vector<Complex> &v, const char *s){
  67.     int n = strlen(s);
  68.     int m = (n + GRP-1) / GRP;
  69.     v.resize(m);
  70.     for (int i = 0; i < m; i++){
  71.         int b = n - GRP * i, x = 0;
  72.         for (int a = max(0, b - GRP); a < b; a++)x = x * 10 + s[a] - '0';
  73.         v[i] = x;
  74.     }
  75. }
  76. void Extract(const vector<Complex> &v,int signa,int signb){
  77.     int i, N = v.size();
  78.     vector<long long> digits(N + 1, 0);
  79.     long double err = 0;
  80.     for (i = 0; i < N; i++){
  81.         long long x = (long long)(v[i].real() + 0.5);
  82.         err = max(err, abs(x - v[i].real()));
  83.         err = max(err, abs(v[i].imag()));
  84.         digits[i] = x;
  85.     }
  86.     long long c = 0;
  87.     for (i = 0; i < N; i++){
  88.         c += digits[i];
  89.         digits[i] = c % RADIX;
  90.         c /= RADIX;
  91.     }
  92.     assert(c == 0);
  93.     for (i = N - 1; i > 0 && digits[i] == 0; i--);
  94.     int idx = 0,blen = 0;
  95.     char buff[30];
  96.     sprintf(buff, "%lld", digits[i]);
  97.     if(signa != signb) mid_man[idx++] = '-';
  98.     while(buff[blen] != '\0')mid_man[idx++] = buff[blen++];
  99.     for (i--; i >= 0; i--){
  100.         sprintf(buff, "%.*lld", GRP, digits[i]);
  101.         blen=0;
  102.         while(buff[blen] != '\0') mid_man[idx++] = buff[blen++];
  103.     }
  104.     mid_man[idx] = '\0';
  105. }
  106. void mul(string &xx,string &yy,int signa,int signb){
  107.     vector<Complex> A, B;
  108.     parse( A, xx.c_str() );
  109.     parse( B, yy.c_str() );
  110.     int N = 1;
  111.     while (N < max(A.size(), B.size())) N *= 2;
  112.     N *= 2;
  113.     A.resize(N);
  114.     B.resize(N);
  115.     FFT( &A[0], N, +1 );
  116.     FFT( &B[0], N, +1 );
  117.     for (int i = 0; i < N; i++) A[i] *= B[i];
  118.     FFT( &A[0], N, -1);
  119.     for (int i = 0; i < N; i++) A[i] /= N;
  120.     Extract( A, signa, signb );
  121. }
  122. template<class T> string toString(T n){
  123.     ostringstream ost;
  124.     ost << n;
  125.     ost.flush();
  126.     return ost.str();
  127. }
  128. int iniflag;
  129. struct Bigint{
  130.     // representations and structures
  131.     string a; // to store the digits
  132.     int sign; // sign = -1 for negative numbers, sign = 1 otherwise
  133.  
  134.     void getInt(){
  135.         a.clear();
  136.         char ch;
  137.         while(true){
  138.             ch=getchar();
  139.             if(ch=='\n' || ch==' ')break;
  140.             a.push_back(ch);
  141.         }
  142.         (*this) = a;
  143.     }
  144.  
  145.     // constructors
  146.     Bigint() { if(!iniflag) { init();iniflag=1; } } // default constructor
  147.     Bigint( string b ){
  148.         if(!iniflag){init();iniflag=1;}
  149.         (*this) = b;   // constructor for string
  150.     }
  151.  
  152.     // some helpful methods
  153.     int size(){ return a.size(); }
  154.     Bigint inverseSign(){
  155.         Bigint ret;
  156.         ret.a = this->a;
  157.         ret.sign = sign * -1;
  158.         return ret;
  159.     }
  160.     // changes the sign
  161.     Bigint normalize( int newSign ){   // removes leading 0, fixes sign
  162.         for( int i = a.size() - 1; i > 0 && a[i] == '0'; i-- )a.erase(a.begin() + i);
  163.         sign = ( a.size() == 1 && a[0] == '0' ) ? 1 : newSign;
  164.         return (*this);
  165.     }
  166.  
  167.     void operator = ( int b ){ (*this)=toString(b); }
  168.     // assignment operator
  169.     void operator = ( string b ){
  170.         a = b[0] == '-' ? b.substr(1) : b;
  171.         reverse( a.begin(), a.end() );
  172.         sign = ( b[0] == '-' ) ? -1 : 1;
  173.     }
  174.  
  175.     // conditional operators
  176.     bool operator < ( const Bigint &b ) const {  // less than operator
  177.         if( sign != b.sign ) return sign < b.sign;
  178.         if( a.size() != b.a.size() )return sign == 1 ? a.size() < b.a.size() : a.size() > b.a.size();
  179.         for( int i = a.size() - 1; i >= 0; i-- ) if( a[i] != b.a[i] )return sign == 1 ? a[i] < b.a[i] : a[i] > b.a[i];
  180.         return false;
  181.     }
  182.     bool operator < ( const int &b ) const {
  183.         return (*this) < toString(b);
  184.     }
  185.     bool operator == ( const Bigint &b ) const {  // operator for equality
  186.         return a == b.a && sign == b.sign;
  187.     }
  188.     bool operator == ( const long long &b ) const {
  189.         return (*this) == toString(b);
  190.     }
  191.  
  192.     // mathematical operators
  193.     Bigint operator + ( Bigint b ) {  // addition operator overloading
  194.         if( sign != b.sign ) {
  195.             if((*this) < b)return b - (*this).inverseSign();
  196.             return (*this) - b.inverseSign();
  197.         }
  198.         Bigint c;
  199.         for(int i = 0, carry = 0; i<a.size() || i<b.size() || carry; i++ ){
  200.             carry+=(i<a.size() ? a[i]-48 : 0)+(i<b.a.size() ? b.a[i]-48 : 0);
  201.             c.a += (carry % 10 + 48);
  202.             carry /= 10;
  203.         }
  204.         return c.normalize(sign);
  205.     }
  206.     Bigint operator + ( long long b ) {
  207.         return (*this) + toString(b);
  208.     }
  209.  
  210.     Bigint operator - ( Bigint b ) {  // subtraction operator overloading
  211.         if( sign != b.sign ) return (*this) + b.inverseSign();
  212.         int s = sign;
  213.         sign = b.sign = 1;
  214.         Bigint c;
  215.         if( (*this) < b ){
  216.             c = ((b - (*this)).inverseSign()).normalize(-s);
  217.             sign = b.sign = s;
  218.             return c;
  219.         }
  220.         for( int i = 0, borrow = 0; i < a.size(); i++ ){
  221.             borrow = a[i] - borrow - (i < b.size() ? b.a[i] : 48);
  222.             c.a += borrow >= 0 ? borrow + 48 : borrow + 58;
  223.             borrow = borrow >= 0 ? 0 : 1;
  224.         }
  225.         sign = b.sign = s;
  226.         return c.normalize(s);
  227.     }
  228.     Bigint operator - ( long long  b ) {
  229.         return (*this) - toString(b);
  230.     }
  231.  
  232.     Bigint operator * ( Bigint b ) {  // multiplication operator overloading
  233.         reverse( a.begin(), a.end() );
  234.         reverse( b.a.begin(), b.a.end() );
  235.         mul(a,b.a,this->sign,b.sign);
  236.         reverse( a.begin(), a.end() );
  237.         reverse( b.a.begin(), b.a.end() );
  238.         return Bigint((string)mid_man);
  239.     }
  240.     Bigint operator * ( long long b ){
  241.         return (*this) * toString(b);
  242.     }
  243.  
  244.     Bigint operator / ( Bigint b ) {  // division operator overloading BI/BI
  245.         if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 );
  246.         Bigint c("0"), d;
  247.         for( int j = 0; j < a.size(); j++ ) d.a += "0";
  248.         int dSign = sign * b.sign;
  249.         b.sign = 1;
  250.         for( int i = a.size() - 1; i >= 0; i-- ){
  251.             c.a.insert( c.a.begin(), '0');
  252.             c = c + a.substr( i, 1 );
  253.             while( !( c < b ) ) c = c - b, d.a[i]++;
  254.         }
  255.         return d.normalize(dSign);
  256.     }
  257.     Bigint operator / ( long long n ) {  // division operator overloading BI/BI
  258.         reverse( a.begin(), a.end() );
  259.         long long int rem = 0;
  260.         int f = 1;
  261.         int idx = 0;
  262.         int len = a.length();
  263.         for(int i = 0; i < len; i++){
  264.             rem = a[i]-'0' + rem * 10;
  265.             if(rem/n != 0) f = 0;
  266.             if(f == 0) mid_man[idx++] = ((char)((rem/n)+'0'));
  267.             rem = rem % n;
  268.         }
  269.         if(f == 1) mid_man[idx++] = '0';
  270.         mid_man[idx] = '\0';
  271.         reverse( a.begin(), a.end() );
  272.         return Bigint( (string)mid_man );
  273.     }
  274.     Bigint operator % ( Bigint b ) {  // modulo operator overloading
  275.         if( b.size() == 1 && b.a[0] == '0' ) b.a[0] /= ( b.a[0] - 48 );
  276.         Bigint c("0");
  277.         b.sign = 1;
  278.         for( int i = a.size() - 1; i >= 0; i-- ){
  279.             c.a.insert( c.a.begin(), '0');
  280.             c = c + a.substr( i, 1 );
  281.             while( !( c < b ) ) c = c - b;
  282.         }
  283.         return c.normalize(sign);
  284.     }
  285.     Bigint operator % ( long long n ) { // modulo operator overloading
  286.         reverse( a.begin(), a.end() );
  287.         long long int rem = 0;
  288.         int idx = 0;
  289.         int len = a.length();
  290.         for(int i = 0; i < len; i++){
  291.             rem = a[i]-'0' + rem * 10;
  292.             rem = rem % n;
  293.         }
  294.         reverse( a.begin(), a.end() );
  295.         return Bigint( toString(rem) );
  296.     }
  297.     void print(){
  298.         if( sign == -1 ) putchar('-');
  299.         for( int i = a.size() - 1; i >= 0; i-- ) putchar(a[i]);
  300.     }
  301.     Bigint sqrt(){
  302.         reverse( this->a.begin(), this->a.end() );
  303.         string a=this->a;
  304.         int idx=0;
  305.         int n = a.size();
  306.         bool f = n%2;
  307.         n = (f) ? n+1 : n;
  308.         vector <int> num (n, 0);
  309.         int i;
  310.         if (f)for (i = 0; i < n-1; i++) num[i+1] = a[i] - 48;
  311.         else for (i = 0; i < n; i++) num[i] = a[i] - 48;
  312.         n /= 2;
  313.         vector <int> root(n, 0);
  314.         vector <int> recieve;
  315.         for (i = 0; i < n; i++){
  316.             recieve.push_back ( num[i*2] );
  317.             recieve.push_back ( num[i*2+1] );
  318.             vector <int> cand(i+1, 0);
  319.             int tmp, ac = 0;
  320.             for (int j = i; j > 0; j--){
  321.                 tmp = root[j-1] * 2 + ac;
  322.                 cand[j] = tmp % 10;
  323.                 ac = tmp / 10;
  324.             }
  325.             if (ac) cand[0] += ac;
  326.             int j;
  327.             for (j = 9; j >= 0; j--){
  328.                 int l = 2 * (i+1);
  329.                 vector <int>  m (l, 0);
  330.                 m[l - 1] = j * j;
  331.                 m[l - 2] = m[l - 1] / 10;
  332.                 m[l - 1] %= 10;
  333.                 int k, o;
  334.                 int ac = 0;
  335.                 for (k = l - 2, o = i; o >= 0 && k > 0; k--, o--){
  336.                     m[k] += cand[o] * j;
  337.                     m[k-1] = m[k] / 10;
  338.                     m[k] %= 10;
  339.                 }
  340.                 bool flag = 1;
  341.                 for (k = 0; k < l; k++){
  342.                     if (recieve[k] > m[k]) break;
  343.                     if (recieve[k] < m[k]){
  344.                         flag = 0;
  345.                         break;
  346.                     }
  347.                 }
  348.                 if (flag){
  349.                     ac = 0;
  350.                     for (k = l-1; k >= 0; k--){
  351.                         tmp = recieve[k] - m[k] - ac;
  352.                         if (tmp < 0)recieve[k] = tmp+10,ac = 1;
  353.                         else recieve[k] = tmp;
  354.                         ac = 0;
  355.                     }
  356.                     break;
  357.                 }
  358.             }
  359.             root[i] = j;
  360.             mid_man[idx++] = (j+'0');
  361.         }
  362.         mid_man[idx] = '\0';
  363.         reverse( this->a.begin(), this->a.end() );
  364.         return Bigint( string(mid_man) );
  365.     }
  366. };
  367. istream& operator >> (istream &in, Bigint &x) {
  368.     in >> x.a;
  369.     x=Bigint(x.a);
  370.     return in;
  371. }
  372. ostream& operator << (ostream &out, const Bigint &x) {
  373.     string p=x.a;
  374.     reverse(p.begin(),p.end());
  375.     if(x.sign==-1)p="-"+p;
  376.     out << p;
  377.     return out;
  378. }
  379.  
  380. int main()
  381. {
  382.     return 0;
  383. }
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!