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 oneBigInteger
I use only with positive numbers.
In my code have the function
initialize 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://mirror.codeforces.com/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 — (BigInt a, BigInt b) {
Set(a);
Set(b);
BigInt ans;
int carry = 0;
FOR(i,0,a.size()-1) {
carry += a[i] — (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 — (BigInt a, int b) {
return a — Integer(b);
}
void operator -- (BigInt &a) { // --a
a = a — 1;
}
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);
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 — 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 — 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;
}
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.
Can you guide me optimal
division
andsqrt
?Thanks for your contribution. I will try improve my code.
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++.
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)I think
should be written as
to follow C traditions.
P.S. Btw, fix this in the post:
this is a good bignum http://mirror.codeforces.com/contest/98/submission/3856625
Thanks Reyna about the problem have
BigInteger
There's issue with defining operators for IO streams:
should be
Even though it does not fix problems with following code:
Thanks
I think that lines 201-203 in the Ubuntu code as well as in this blog
should be changed to
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.what is — for ? My compiler shows mdash not declared in the scope
Your code can be improved
Since bignum is an array of digits, you should use
const bignum &x
when you dont changex
because it wont make a new cloneYou 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;
andvector<int> value{1};
so that you can improve negative calculationCreate
void operator ?(bignum &a, const bignum &b) { ... }
beforebignum operator ?(const bignum &a, const bignum &b) { ... }
is better because we dont have to make clone in first operator