HaRiSK's blog

BIG INTEGER WITH C++
By HaRiSK, 10 years ago, In English

NEW UPD :

This morning, I begin with BigInteger in C++ (because I usually use BigInteger in Java). I want to check the correction about my code, so that I post this blog to hope you can check it.

Thank knst, I have more update :

  • I use typedef vector<int> BigInt; to make one BigInteger

  • I use only with positive numbers.

  • In my code have the functioninitialize one BigInt : 

BigInt a = Integer(string);
BigInt a = Integer(char[]);
BigInt a = Integer(int);
BigInt a = Integer(long long);
  • I have function print one BigInt :
Print(BigInt);
  • I have iostream BigInt : NEW
cin >> BigInt;
cout << BigInt;
  • I have operators on BigInt : have NEW
BigInt + BigInt   (the value return is BigInt)
BigInt + int      (the value return is BigInt)
++BigInt          (the value of BigInt set to BigInt+1 and the value return is BigInt)
BigInt += BigInt  (no return value)
BigInt += int     (no return value)

BigInt - BigInt   (the value return is BigInt, that is positive numbers)
BigInt - int      (the value return is BigInt)
--BigInt          (the value of BigInt set to BigInt-1 and the value return is BigInt)
BigInt -= BigInt  (no return value)
BigInt -= int     (no return value)

BigInt * BigInt   (the value return is BigInt)
BigInt * int      (the value return is BigInt)
BigInt *= BigInt  (no return value)
BigInt *= int     (no return value)

BigInt / BigInt   (the value return is BigInt)     (need optimal)
BigInt / int      (the value return is BigInt)     (NEW - quickly)
BigInt /= BigInt  (no return value)
BigInt /= int     (no return value)

BigInt % BigInt   (the value return is BigInt)
BigInt % int      (the value return is int, that is in [0..int-1])
BigInt %= BigInt  (no return value)
BigInt %= int     (no return value)

NEW : Compare 
         BigInt - BigInt
         BigInt - int

> , < , == , >= , <=  (the value return is bool)
  • I have functions on BigInt :
max(BigInt, BigInt) (the value return is BigInt)
min(BigInt, BigInt) (the value return is BigInt)

gcd(BigInt, BigInt) (the value return is BigInt)
lcm(BigInt, BigInt) (the value return is BigInt)

sqrt(BigInt)        (the value return is BigInt)  
NEW : quickly : knst comment (http://codeforces.net/blog/entry/16380#comment-213120)

log(int, BigInt)    (the value return is int, log(int, BigInt) is small)

I hope you can check the correction of this code

Sorry for my bad English.

Hope have more comments to improve BigInt perfectly.

This is my code :

https://github.com/Stupid-Dog/BigInteger/blob/stupid/BigInteger.cpp

http://paste.ubuntu.com/10270983/

#include <bits/stdc++.h>

using namespace std;

typedef int64_t ll;
typedef long long ll;

#define EL printf("\n")
#define pb push_back
#define FOR(i,l,r) for (int i=l;i<=r;i++)
#define FORD(i,r,l) for (int i=r;i>=l;i--)

const int base = 1e9;
typedef vector<int> BigInt;

void Set(BigInt &a) {
    while (a.size() > 1 && a.back() == 0) a.pop_back();
}

void Print(BigInt a) {
    Set(a);
    printf("%d", (a.size() == 0) ? 0 : a.back());
    FORD(i,a.size()-2,0) printf("%09d", a[i]); EL;
}

BigInt Integer(string s) {
    BigInt ans;
    if (s[0] == '-') return ans;
    if (s.size() == 0) {ans.pb(0); return ans;}
    while (s.size()%9 != 0) s = '0'+s;
    for (int i=0;i<s.size();i+=9) {
        int v = 0;
        for (int j=i;j<i+9;j++) v = v*10+(s[j]-'0');
        ans.insert(ans.begin(),v);
    }
    Set(ans);
    return ans;
}

BigInt Integer(char c[]) {
    string s = "";
    FOR(i,0,strlen(c)-1) s = s + c[i];
    return Integer(s);
}

BigInt Integer(ll x) {
    string s = "";
    while (x > 0) s = char(x%10+'0') + s, x /= 10;
    return Integer(s);
}

BigInt Integer(int x) {
    return Integer((ll) x);
}

void operator >> (istream &in, BigInt &a) {
    string s;
    getline(cin, s);
    a = Integer(s);
}

void operator << (ostream &out, BigInt a) {
    Print(a);
}

bool operator < (BigInt a, BigInt b) {
    Set(a);
    Set(b);
    if (a.size() != b.size()) return (a.size() < b.size());
    FORD(i,a.size()-1,0)
        if (a[i] != b[i]) return (a[i] < b[i]);
    return false;
}

bool operator > (BigInt a, BigInt b) {
    return (b < a);
}

bool operator == (BigInt a, BigInt b) {
    return (!(a < b) && !(b < a));
}

bool operator <= (BigInt a, BigInt b) {
    return (a < b || a == b);
}

bool operator >= (BigInt a, BigInt b) {
    return (b < a || b == a);
}

bool operator < (BigInt a, int b) {
    return (a < Integer(b));
}

bool operator > (BigInt a, int b) {
    return (a > Integer(b));
}

bool operator == (BigInt a, int b) {
    return (a == Integer(b));
}

bool operator >= (BigInt a, int b) {
    return (a >= Integer(b));
}

bool operator <= (BigInt a, int b) {
    return (a <= Integer(b));
}

BigInt max(BigInt a, BigInt b) {
    if (a > b) return a;
    return b;
}

BigInt min(BigInt a, BigInt b) {
    if (a < b) return a;
    return b;
}

BigInt operator + (BigInt a, BigInt b) {
    Set(a);
    Set(b);
    BigInt ans;
    int carry = 0;
    FOR(i,0,max(a.size(), b.size())-1) {
        if (i < a.size()) carry += a[i];
        if (i < b.size()) carry += b[i];
        ans.pb(carry%base);
        carry /= base;
    }
    if (carry) ans.pb(carry);
    Set(ans);
    return ans;
}

BigInt operator + (BigInt a, int b) {
    return a + Integer(b);
}

BigInt operator ++ (BigInt &a) { // ++a
    a = a + 1;
    return a;
}

void operator += (BigInt &a, BigInt b) {
    a = a + b;
}

void operator += (BigInt &a, int b) {
    a = a + b;
}

BigInt operator &mdash; (BigInt a, BigInt b) {
    Set(a);
    Set(b);
    BigInt ans;
    int carry = 0;
    FOR(i,0,a.size()-1) {
        carry += a[i] &mdash; (i < b.size() ? b[i] : 0);
        if (carry < 0) ans.pb(carry+base), carry = -1;
        else ans.pb(carry), carry = 0;
    }
    Set(ans);
    return ans;
}

BigInt operator &mdash; (BigInt a, int b) {
    return a &mdash; Integer(b);
}

void operator -- (BigInt &a) { // --a
    a = a &mdash; 1;
}

void operator -= (BigInt &a, BigInt b) {
    a = a + b;
}

void operator -= (BigInt &a, int b) {
    a = a &mdash; b;
}

BigInt operator * (BigInt a, BigInt b) {
    Set(a);
    Set(b);
    BigInt ans;
    ans.assign(a.size()+b.size(), 0);
    FOR(i,0,a.size()-1) {
        ll carry = 0ll;
        for (int j=0;j<b.size() || carry > 0;j++) {
            ll s = ans[i+j] + carry + (ll)a[i]*(j<b.size()?(ll)b[j]:0ll);
            ans[i+j] = s%base;
            carry = s/base;
        }
    }
    Set(ans);
    return ans;
}

BigInt operator * (BigInt a, int b) {
    return a * Integer(b);
}

void operator *= (BigInt &a, BigInt b) {
    a = a * b;
}

void operator *= (BigInt &a, int b) {
    a = a * b;
}



BigInt operator / (BigInt a, BigInt b) {
    Set(a);
    Set(b);
    if (b == Integer(0)) return Integer("-1");
    BigInt ans, cur;
    FORD(i,a.size()-1,0) {
        cur.insert(cur.begin(), a[i]);
        int x = 0, L = 0, R = base;
        while (L <= R) {
            int mid = (L+R)>>1;
            if (b*Integer(mid) > cur) {
                x = mid;
                R = mid-1;
            }
            else
                L = mid+1;
        }
        cur = cur &mdash; Integer(x-1)*b;
        ans.insert(ans.begin(),x-1);
    }
    Set(ans);
    return ans;
}

BigInt operator / (BigInt a, int b) {
    Set(a);
    BigInt ans;
    ll cur = 0ll;
    FORD(i,a.size()-1,0) {
        cur = (cur*(ll)base + (ll)a[i]);
        ans.insert(ans.begin(),cur/b);
        cur %= b;
    }
    Set(ans);
    return ans;
}

void operator /= (BigInt &a, BigInt b) {
    a = a / b;
}

void operator /= (BigInt &a, int b) {
    a = a / b;
}

BigInt operator % (BigInt a, BigInt b) {
    Set(a);
    Set(b);
    if (b == Integer(0)) return Integer("-1");
    BigInt ans;
    FORD(i,a.size()-1,0) {
        ans.insert(ans.begin(), a[i]);
        int x = 0, L = 0, R = base;
        while (L <= R) {
            int mid = (L+R)>>1;
            if (b*Integer(mid) > ans) {
                x = mid;
                R = mid-1;
            }
            else
                L = mid+1;
        }
        ans = ans &mdash; Integer(x-1)*b;
    }
    Set(ans);
    return ans;
}

int operator % (BigInt a, int b) {
    Set(a);
    if (b == 0) return -1;
    int ans = 0;
    FORD(i,a.size()-1,0)
        ans = (ans*(base%b) + a[i]%b)%b;
    return ans;
}

void operator %= (BigInt &a, BigInt b) {
    a = a % b;
}

void operator %= (BigInt &a, int b) {
    a = a % Integer(b);
}

BigInt gcd(BigInt a, BigInt b) {
    Set(a);
    Set(b);
    while (b > Integer(0)) {
        BigInt r = a%b;
        a = b;
        b = r;
    }
    Set(a);
    return a;
}

BigInt lcm(BigInt a, BigInt b) {
    return (a*b/gcd(a,b));
}


BigInt sqrt(BigInt a) {
    BigInt x0 = a, x1 = (a+1)/2;
    while (x1 < x0) {
        x0 = x1;
        x1 = (x1+a/x1)/2;
    }
    return x0;
}

BigInt pow(BigInt a, BigInt b) {
    if (b == Integer(0)) return Integer(1);
    BigInt tmp = pow(a, b/2);
    if (b%2 == 0) return tmp * tmp;
    return tmp * tmp * a;
}

BigInt pow(BigInt a, int b) {
    return pow(a,(Integer(b)));
}

int log(int n, BigInt a) { // log_n(a)
    Set(a);
    int ans = 0;
    while (a > Integer(1)) {
        ans++;
        a /= n;
    }
    return ans;
}

int main()
{
    BigInt B;  cin >> B;
    BigInt A = Integer("123456789");
    BigInt C = Integer(123456789ll);
    int x; x = 123456789;

    if (B <= A) cout << A - B;
    else {
        cout << "-";
        cout << B - A;
    }

    cout << A + B; Print(A + x);
    cout << A * B; Print(A * x);
    cout << A / B; Print(A / x);
    cout << A % B; printf("%d\n", A % x);

    C = ++A; ++B; C += B + x;
    Print(A); Print(B); Print(C);

    cout << max(A,B);
    cout << min(A,B);

    cout << gcd(A,B);
    cout << lcm(A,B);

    cout << sqrt(A);
    printf("%d %d %d\n", log(2,A), log(10,B), log(5,C));

    A = Integer(16); x = 12;
    cout << pow(A,B);
    cout << pow(A,x);

    return 0;
}
  • Vote: I like it
  • +18
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
10 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

Can you publish your code on github repo? Don't forget add a license.

Your division and sqrt is not optimal. But your solution have a good point: code is simple and clear.

UPD: I recommend use a const reference for argument in functions. And I strong recommend implement operator<<(...) for output BigInt with using iostream style.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Can you guide me optimal division and sqrt ?

    Thanks for your contribution. I will try improve my code.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      For Sqrt you can use Newton method for sequence of approximation. https://en.wikipedia.org/wiki/Methods_of_computing_square_roots

      For division you can use division by column. It's described in Knuth's «Art of Programming», vol.2. I think, than good implementation of division is very faster (e.g. in 10 times), but cannot be sure.

      I have some implementation of BigInteger, but this implementation is not easy for understanding and not clearly. I develop it on free time for fun. https://github.com/knst/big_number

      And one hint. If Boost is available, you can use Boost.multipresicion. It's very good and fast implementation of BigInteger for C++.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thank you very much !

        I need improve BigInt / int because it is not complexity as I code, thank for your remind.

        knst , can you help me with (BigInt / BigInt) and (BigInt % BigInt) ? I can't make hard this. Thanks!

        Can you tell me my stupid in implement two problems above ? (I use Binary Search to get the result, as I said log2(BigInt) is very small, so I think it not bad)

        → Reply
»
10 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I think

void operator *= (BigInt &a, BigInt b) {
    a = a * b;
}

should be written as

BigInt& operator *= (BigInt &a, BigInt b) {
    return a = a * b;
}

to follow C traditions.

P.S. Btw, fix this in the post:

BigInt operator &mdash; (BigInt a, BigInt b) {
→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

this is a good bignum http://codeforces.net/contest/98/submission/3856625

→ Reply
»
10 years ago, # |
  Vote: I like it +18 Vote: I do not like it

There's issue with defining operators for IO streams:

void operator >> (istream &in, BigInt &a) {
    string s;
    getline(cin, s);
    a = Integer(s);
}

void operator << (ostream &out, BigInt a) {
    Print(a);
}

should be

istream& operator >> (istream &in, BigInt &a) {
    string s;
    getline(in, s);
    a = Integer(s);
    return in;
}

ostream& operator << (ostream &out, BigInt a) {
    Print(a);
    return out;
}

Even though it does not fix problems with following code:

int main() {
    freopen("out", "w", stdout);
    BigInt A;
    cin >> A;
    cerr << A << endl; // A will be printed to stdout
}
→ Reply
»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

I think that lines 201-203 in the Ubuntu code as well as in this blog

void operator -= (BigInt &a, BigInt b) {
    a = a + b;
}

should be changed to

void operator -= (BigInt &a, BigInt b) {
    a = a - b;
}
→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Add an isProbablePrime() fuction similar to BigInteger in Java, that uses Miller-Rabin primality testing algorithm to determine if a large integer is prime up to a specific probability.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what is — for ? My compiler shows mdash not declared in the scope

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Your code can be improved

  • Since bignum is an array of digits, you should use const bignum &x when you dont change x because it wont make a new clone

  • You can change the base from $$$10^1 -> 10^4$$$ which store 1 digits each number -> 4 digits each number

  • If you want to help negative numbers, you should you struct of bool sign = false; and vector<int> value{1}; so that you can improve negative calculation

  • Create void operator ?(bignum &a, const bignum &b) { ... } before bignum operator ?(const bignum &a, const bignum &b) { ... } is better because we dont have to make clone in first operator

→ Reply