## 10814 - Simplifying Fractions

Moderator: Board moderators

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

### 10814--TLE how to get gcd faster?

how to get GCD faster....?

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
Should I assume you know Euclid's algorithm?
It computes the GCD of two n-bit numbers in O(log n) iterations.

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai
i use it..

but got tle...
i think the class BigInteger is correct,for i have solved many problems by it...

the class is too long ,so i wont paste here now....

Code: Select all

``````BigInteger gcd(BigInteger a,BigInteger b)
{
BigInteger tmp;
if(a==0)
return b;
while(a!=0)
{
tmp=b%a;
if(tmp==0)
return a;
else
{
a=a%tmp;
b=tmp;
}
}
return b;
}

int main()
{
BigInteger a,b,c;
long testCase;
cin>>testCase;
while(testCase-->=1)
{
char ch;
cin>>a>>ch>>b;
c=gcd(a,b);
a=a/c;
b=b/c;
cout<<a<<" / "<<b<<endl;
}
}``````

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Most likely it's because your BigInteger's division is too slow. Better try to optimize that code first.

As for gcd, there's a so-called "binary gcd" algorithm, which uses only shifts and subtractions. Here's a pseudo-code for it:

Code: Select all

``````gcd(a, b):   /* assumes a >= 0, b >= 0, a*b > 0 */
g = 0
while both a and b are even:
g++, a /= 2, b /= 2;

while a != 0 and b != 0:
while a is even: a /= 2
while b is even: b /= 2

if a > b:
a -= b
else:
b -= a

if a == 0:
return b << g
else:
return a << g
``````

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai
Most likely it's because your BigInteger's division is too slow. Better try to optimize that code first
i have generate a lot of input data to test my code
it works so fast...

how to optimize the BigInteger's division ?can you give me some advise?

[/code]

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Check how fast you can pass this input:

Code: Select all

``````5
36893487443044468898 / 36893487958440542378
999999999999872000000000001287 / 999999999999936000000000000583
999999999999999999999999999999 / 6
30 / 1000000000000000000000000000000
304888344611713860501504000000 / 40729680599249024150621323470``````
The output should be:

Code: Select all

``````4294967231 / 4294967291
999999999999883 / 999999999999947
333333333333333333333333333333 / 2
3 / 100000000000000000000000000000
1366643159020339200000 / 182568275710689562381``````
For division you can use just the usual long division, taught at school. It's quite efficient for this problem.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
How do the copy constructor and assignment operator in your BigInteger work? If they create new arrays all the time, that will take a lot of time. Try to avoid allocating new memory as much as possible.
If only I had as much free time as I did in college...

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai
hi mf my code works ok and fast for your sample input..
so i think i should paste my whole code here......

any suggesstion is welcome...thanks

Code: Select all

``````//10814 Simplifying Fractions
#include <iostream>
#include <cmath>
#include <string>
using namespace std;

class BigInteger
{

private:
enum {MAXNUM=999999999,BASE=1000000000,MAXLENGTH=32};
long val[MAXLENGTH];
long length;
public:
//////////////////////////////////
BigInteger(long n=0);
BigInteger(const string &str);
BigInteger(long *pVal,long len);
//////////////////////////////////
BigInteger(const BigInteger &p);
/////////////////////////////////
BigInteger & operator =(const BigInteger &rval);
BigInteger & operator =(long rval);
BigInteger & operator =(const string &str);
//////////////////////////////////
virtual ~BigInteger(){}
///////////////////////////////////
long Compare(const BigInteger &rval);
long Compare(long rval);
long Compare(const string &rval);
BigInteger Sqrt();

BigInteger operator +(const BigInteger &rval);
BigInteger operator +(long rval);
BigInteger operator +(const string &rval);
BigInteger &operator +=(const BigInteger &rval);
BigInteger &operator +=(long rval);
BigInteger &operator +=(const string &rval);

BigInteger operator -(const BigInteger &rval);
BigInteger operator -(long rval);
BigInteger operator -(const string &rval);
BigInteger &operator -=(const BigInteger &rval);
BigInteger &operator -=(long rval);
BigInteger &operator -=(const string &rval);

BigInteger operator *(const BigInteger &rval);
BigInteger operator *(long rval);
BigInteger operator *(const string &rval);
BigInteger &operator *=(const BigInteger &rval);
BigInteger &operator *=(long rval);
BigInteger &operator *=(const string &rval);

BigInteger operator /(const BigInteger &rval);
BigInteger operator /(long rval);
BigInteger operator /(const string &rval);
BigInteger &operator /=(const BigInteger &rval);
BigInteger &operator /=(long rval);
BigInteger &operator /=(const string &rval);

BigInteger operator %(const BigInteger &rval);
BigInteger operator %(long rval);
BigInteger operator %(const string &rval);
BigInteger &operator %=(const BigInteger &rval);
BigInteger &operator %=(long rval);
BigInteger &operator %=(const string &rval);

BigInteger &operator ++();
BigInteger operator ++(int);
BigInteger &operator --();
BigInteger operator --(int);

bool operator >(const BigInteger &rval);
bool operator >(long rval);
bool operator >(const string &rval);

bool operator <(const BigInteger &rval);
bool operator <(long rval);
bool operator <(const string &rval);

bool operator >=(const BigInteger &rval);
bool operator >=(long rval);
bool operator >=(const string &rval);

bool operator <=(const BigInteger &rval);
bool operator <=(long rval);
bool operator <=(const string &rval);

bool operator ==(const BigInteger &rval);
bool operator ==(long rval);
bool operator ==(const string &rval);

bool operator !=(const BigInteger &rval);
bool operator !=(long rval);
bool operator !=(const string &rval);

friend ostream & operator<<(ostream &out,const BigInteger &p);
friend istream & operator>>(istream &in,BigInteger &p);

};

BigInteger::BigInteger(long n)
{
val[0]=n;
length=1;
}
BigInteger::BigInteger(const string &str)
{
long tab[10]={1,10,100,1000,10000,100000,1000000,
10000000,100000000,1000000000};
long i,j,k,l;
long tmp;
l=str.length();
length=(l-1)/9+1;
for(i=0;i<length;i++)
{
tmp=0;
for(j=l-i*9-1,k=0;j>l-1-(i+1)*9&&j>=0;j--,k++)
{

tmp+=tab[k]*(str[j]-'0');
}
val[i]=tmp;
}
}
BigInteger::BigInteger(long *pVal,long len)
{
long i;
length=len;
for(i=0;i<len;i++)
val[i]=pVal[i];
}

BigInteger::BigInteger(const BigInteger &p)
{
length=p.length;
long i=0;
while(i<length)
{
val[i]=p.val[i];
++i;
}
}
BigInteger & BigInteger:: operator =(const BigInteger &rval)
{
length=rval.length;
long i=0;
for(;i<length;++i)
val[i]=rval.val[i];
}
BigInteger & BigInteger::operator =(long rval)
{
length=1;
val[0]=rval;
}
BigInteger & BigInteger::operator =(const string &str)
{
long tab[10]={1,10,100,1000,10000,100000,1000000,
10000000,100000000,1000000000};
long i,j,k,l;
long tmp;
l=str.length();
length=(l-1)/9+1;
for(i=0;i<length;i++)
{
tmp=0;
for(j=l-i*9-1,k=0;j>l-1-(i+1)*9&&j>=0;j--,k++)
{

tmp+=tab[k]*(str[j]-'0');
}
val[i]=tmp;
}
}
long BigInteger::Compare(const BigInteger &rval)
{
//this==rval return 0;
//this>rval return 1;
//this<rval return -1;
long i;
if(length>rval.length)
return 1;
else
{
if(length<rval.length)
return -1;
else
{
for(i=length-1;i>=0;i--)
{
if(val[i]>rval.val[i])
return 1;
else
if(val[i]<rval.val[i])
return -1;
}
return 0;
}
}

}
long BigInteger::Compare(long rval)
{
BigInteger tmp(rval);
return Compare(tmp);
}
long BigInteger::Compare(const string &rval)
{
BigInteger tmp(rval);
return Compare(tmp);
}
BigInteger BigInteger::Sqrt()
{
BigInteger x;
if(length==1)
{
x.length=1;
x.val[0]=(long)sqrt((double)val[0]);
}
else
{
BigInteger m,dx,t;
long cmp;
x.length=(length-1)/2+1;
x.val[x.length-1]=(long)sqrt((double)val[length-1]);
if(length%2==0)
x.val[x.length-1]*=31622;
while(1)
{
m=operator/(x);
cmp=m.Compare(x);
if(cmp==0)
break;
else
{
if(cmp==1)
{
dx=(m-x)/2;
x+=dx;
}
else
{
dx=(x-m)/2;
x-=dx;
}
}
}
}
return x;
}
BigInteger BigInteger::operator +(const BigInteger &rval)
{
BigInteger sum;
long tmp;
long n=0;
if(length>rval.length)
tmp=rval.length;
else
tmp=length;
long i;
long carry=0;
for(i=0;i<tmp;++i)
{
sum.val[i]=val[i]+rval.val[i]+carry;
if(sum.val[i]>MAXNUM)
{
sum.val[i]-=MAXNUM+1;
carry=1;
}
else
carry=0;
}
n=tmp;
for(;i<length;++i)
{
sum.val[i]=val[i]+carry;
if(sum.val[i]>MAXNUM)
{
sum.val[i]-=MAXNUM+1;
carry=1;
}
else
{
carry=0;
}
++n;
}
for(;i<rval.length;++i)
{
sum.val[i]=rval.val[i]+carry;
if(sum.val[i]>MAXNUM)
{
sum.val[i]-=MAXNUM+1;
carry=1;
}
else
{
carry=0;
}
n++;
}
if(carry==1)
{
sum.val[i]=1;
n++;
}
sum.length=n;
return sum;

}
BigInteger BigInteger::operator +(long rval)
{
BigInteger tmp(rval);
return operator+(tmp);
}
BigInteger BigInteger::operator +(const string &rval)
{
BigInteger tmp(rval);
return operator+(tmp);
}
BigInteger & BigInteger::operator +=(const BigInteger &rval)
{
BigInteger sum=this->operator+(rval);
this->operator=(sum);
return *this;
}
BigInteger & BigInteger::operator +=(long rval)
{
BigInteger tmp(rval);
BigInteger sum=this->operator+(tmp);
this->operator=(sum);
return *this;
}
BigInteger & BigInteger::operator +=(const string &rval)
{
BigInteger tmp(rval);
BigInteger sum=this->operator+(tmp);
this->operator=(sum);
return *this;
}
BigInteger BigInteger::operator -(const BigInteger &rval)
{
BigInteger sub;
long tmp;
long n=0;
if(Compare(rval)==0)
return BigInteger(0);
if(Compare(rval)==1)
tmp=rval.length;
else
tmp=length;
long i;
long carry=0;
for(i=0;i<tmp;++i)
{
sub.val[i]=val[i]-rval.val[i]-carry;
if(sub.val[i]<0)
{
sub.val[i]+=BASE;
carry=1;
}
else
carry=0;
}
n=tmp;
for(;i<length;++i)
{
sub.val[i]=val[i]-carry;
if(sub.val[i]<0)
{
sub.val[i]+=BASE;
carry=1;
}
else
{
carry=0;
}
n++;
}
for(;i<rval.length;++i)
{
sub.val[i]=rval.val[i]-carry;
if(sub.val[i]<0)
{
sub.val[i]+=BASE;
carry=1;
}
else
{
carry=0;
}
n++;
}
if(sub.val[n-1]==0)
n--;
sub.length=n;
return sub;
}
BigInteger BigInteger::operator -(long rval)
{
BigInteger tmp(rval);
return operator-(tmp);
}
BigInteger BigInteger::operator -(const string &rval)
{
BigInteger tmp(rval);
return operator-(tmp);
}
BigInteger & BigInteger::operator -=(const BigInteger &rval)
{
BigInteger sub=this->operator-(rval);
this->operator=(sub);
return *this;
}
BigInteger & BigInteger::operator -=(long rval)
{
BigInteger tmp(rval);
BigInteger sub=this->operator-(rval);
this->operator=(sub);
return *this;
}
BigInteger & BigInteger::operator -=(const string &rval)
{
BigInteger tmp(rval);
BigInteger sub=this->operator-(rval);
this->operator=(sub);
return *this;
}
BigInteger BigInteger::operator *(const BigInteger &rval)
{
BigInteger mul;
long an=length;
long bn=rval.length;
long i,j;
long long tmp;
for(i=0;i<MAXLENGTH;++i)
mul.val[i]=0;
for(i=0;i<an;++i)
{
mul_carry=0;
for(j=0;j<bn;++j)
{
tmp=(long long)(val[i])*(long long)(rval.val[j])+mul_carry;
if(mul.val[i+j]>=BASE)
{
mul.val[i+j]-=BASE;
}
else
{
}
mul_carry=tmp/BASE;
}
}
for(i=MAXLENGTH-1;i>=0;--i)
if(mul.val[i]!=0)
break;
if(i>=0)
mul.length=i+1;
else
mul.length=1;
return mul;
}
BigInteger BigInteger::operator *(long rval)
{
BigInteger tmp(rval);
return operator*(tmp);
}
BigInteger BigInteger::operator *(const string &rval)
{
BigInteger tmp(rval);
return operator*(tmp);
}
BigInteger & BigInteger::operator *=(const BigInteger &rval)
{
BigInteger mul=this->operator*(rval);
this->operator=(mul);
return *this;
}
BigInteger & BigInteger::operator *=(long rval)
{
BigInteger mul=this->operator*(rval);
this->operator=(mul);
return *this;
}
BigInteger & BigInteger::operator *=(const string &rval)
{
BigInteger mul=this->operator*(rval);
this->operator=(mul);
return *this;
}

BigInteger BigInteger::operator /(const BigInteger &rval)
{
BigInteger div,mod;
long tmp=Compare(rval);
if(tmp==1)
{
long i,j,k;
div.length=length-rval.length+1;
BigInteger table[32];
table[0]=rval;
for(i=1;i<32;++i)
table[i]=table[i-1]+table[i-1];

for(i=length-1,j=rval.length-2;j>=0;--i,--j)
mod.val[j]=val[i];
mod.length=rval.length-1;

for(i=length-rval.length;i>=0;--i)
{
for(j=mod.length-1;j>=0;--j)
{
mod.val[j+1]=mod.val[j];
}
mod.val[0]=val[i];
if(mod.val[mod.length]!=0)
++mod.length;
for(j=30,div.val[i]=0,k=(1<<30);j>=0;--j,k=(k>>1))
{
if(mod.Compare(table[j])>=0)
{
div.val[i]|=k;
mod-=table[j];

}
}

}
while(div.val[div.length-1]==0)
--div.length;
}
else
{
if(tmp==-1)
{
div=0;
}
else
{
div=1;
}
}
return div;
}
BigInteger BigInteger::operator /(long rval)
{
BigInteger tmp(rval);
return operator/(tmp);
}
BigInteger BigInteger::operator /(const string &rval)
{
BigInteger tmp(rval);
return operator/(tmp);
}
BigInteger & BigInteger::operator /=(const BigInteger &rval)
{
BigInteger div=this->operator/(rval);
this->operator=(div);
return *this;
}
BigInteger & BigInteger::operator /=(long rval)
{
BigInteger div=this->operator/(rval);
this->operator=(div);
return *this;
}
BigInteger & BigInteger::operator /=(const string &rval)
{
BigInteger div=this->operator/(rval);
this->operator=(div);
return *this;
}
BigInteger BigInteger::operator %(const BigInteger &rval)
{
BigInteger div,mod;
long tmp=Compare(rval);
if(tmp==1)
{
long i,j,k;
div.length=length-rval.length+1;
BigInteger table[32];
table[0]=rval;
for(i=1;i<32;++i)
table[i]=table[i-1]+table[i-1];

for(i=length-1,j=rval.length-2;j>=0;--i,--j)
mod.val[j]=val[i];
mod.length=rval.length-1;

for(i=length-rval.length;i>=0;--i)
{
for(j=mod.length-1;j>=0;--j)
{
mod.val[j+1]=mod.val[j];
}
mod.val[0]=val[i];
if(mod.val[mod.length]!=0)
++mod.length;
for(j=30,div.val[i]=0,k=(1<<30);j>=0;--j,k=(k>>1))
{
if(mod.Compare(table[j])>=0)
{
div.val[i]|=k;
mod-=table[j];

}
}

}

}
else
{
if(tmp==-1)
{
mod=*this;
}
else
{
mod=0;
}
}

return mod;

}
BigInteger BigInteger::operator %(long rval)
{
BigInteger tmp(rval);
return operator%(tmp);
}
BigInteger BigInteger::operator %(const string &rval)
{
BigInteger tmp(rval);
return operator%(tmp);
}
BigInteger & BigInteger::operator %=(const BigInteger &rval)
{
BigInteger mod=this->operator%(rval);
this->operator=(mod);
return *this;
}
BigInteger & BigInteger::operator %=(long rval)
{
BigInteger mod=this->operator%(rval);
this->operator=(mod);
return *this;
}
BigInteger & BigInteger::operator %=(const string &rval)
{
BigInteger mod=this->operator%(rval);
this->operator=(mod);
return *this;
}
BigInteger & BigInteger::operator ++()
{
*this+=1;
return *this;
}
BigInteger BigInteger::operator ++(int)
{
BigInteger tmp(*this);
*this+=1;
return tmp;
}
BigInteger & BigInteger::operator --()
{
*this-=1;
return *this;
}
BigInteger BigInteger::operator --(int)
{
BigInteger tmp(*this);
*this-=1;
return tmp;
}
bool BigInteger::operator >(const BigInteger &rval)
{
if(Compare(rval)==1)
return true;
else
return false;
}
bool BigInteger::operator >(long rval)
{
if(Compare(rval)==1)
return true;
else
return false;
}
bool BigInteger::operator >(const string &rval)
{
if(Compare(rval)==1)
return true;
else
return false;
}
bool BigInteger::operator <(const BigInteger &rval)
{
if(Compare(rval)==-1)
return true;
else
return false;
}
bool BigInteger::operator <(long rval)
{
if(Compare(rval)==-1)
return true;
else
return false;
}
bool BigInteger::operator <(const string &rval)
{
if(Compare(rval)==-1)
return true;
else
return false;
}
bool BigInteger::operator >=(const BigInteger &rval)
{
if(Compare(rval)>=0)
return true;
else
return false;
}
bool BigInteger::operator >=(long rval)
{
if(Compare(rval)>=0)
return true;
else
return false;
}
bool BigInteger::operator >=(const string &rval)
{
if(Compare(rval)>=0)
return true;
else
return false;
}
bool BigInteger::operator <=(const BigInteger &rval)
{
if(Compare(rval)<=0)
return true;
else
return false;
}
bool BigInteger::operator <=(long rval)
{
if(Compare(rval)<=0)
return true;
else
return false;
}
bool BigInteger::operator <=(const string &rval)
{
if(Compare(rval)<=0)
return true;
else
return false;
}
bool BigInteger::operator ==(const BigInteger &rval)
{
if(Compare(rval)==0)
return true;
else
return false;
}
bool BigInteger::operator ==(long rval)
{
if(Compare(rval)==0)
return true;
else
return false;
}
bool BigInteger::operator ==(const string &rval)
{
if(Compare(rval)==0)
return true;
else
return false;
}
bool BigInteger::operator !=(const BigInteger &rval)
{
if(Compare(rval)!=0)
return true;
else
return false;
}
bool BigInteger::operator !=(long rval)
{
if(Compare(rval)!=0)
return true;
else
return false;
}
bool BigInteger::operator !=(const string &rval)
{
if(Compare(rval)!=0)
return true;
else
return false;
}
ostream & operator<<(ostream &out,const BigInteger &n)
{
long i=n.length-1;
out<<n.val[i];
for(--i;i>=0;--i)
{
out.width(9);
out.fill('0');
out<<n.val[i];
}
return out;
}
istream & operator>>(istream &in,BigInteger &p)
{
string str;
in>>str;
p=str;
return in;
}

BigInteger gcd(BigInteger a,BigInteger b)
{
BigInteger tmp;
if(a==0)
return b;
while(a!=0)
{
tmp=b%a;
if(tmp==0)
return a;
else
{
a=a%tmp;
b=tmp;
}
}
return b;
}

int main()
{
BigInteger a,b,c;
long testCase;
cin>>testCase;
while(testCase-->=1)
{
char ch;
cin>>a>>ch>>b;
c=gcd(a,b);
a=a/c;
b=b/c;
cout<<a<<" / "<<b<<endl;
}
}

``````

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:
I had a similar problem, I was sure of the BigInt part, but still got TLE.
And that is when it struck me to tune my input scanning part. I haven't
looked at your BigInt class, call me lazy, if you will! But the input scanning
part -- I did have a look and I do think you need to change it.
It ain't that simple.

HTH

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
sunnycare, I think you have some bugs in your BigInteger.
Try this input:

Code: Select all

``````1
1000000000000000000000000000000 / 999999999999999999999999999999
``````

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai
thanks....you are right ,mf;

but how can you find that? read my code?

i think its more useful for me ...

dovier_antonio
New poster
Posts: 47
Joined: Fri Feb 18, 2005 5:00 am
Location: Havana, Cuba

### Re: Hi Litle

I think that your algorithm looks fine...
Last edited by dovier_antonio on Fri Feb 03, 2012 9:19 am, edited 1 time in total.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### TLE....

This one also got TLE...

Code: Select all

``````#include<stdio.h>
int main()
{
long int i,n,a,b,j,pot;
scanf("%ld",&n);
{
for(i=1;i<=n;i++)
{
if(b>a)
{
pot=a;
a=b;
b=pot;
}
scanf("%ld / %ld",&a,&b);
for(j=a;j>=1;j--)
{
if(a%j==0&&b%j==0)
{
a=a/j;
b=b/j;
}
}
printf("%ld / %ld\n",a,b);
}
}
return 0;
}
``````
try_try_try_try_&&&_try@try.com
This may be the address of success.

CSEDU_1323
New poster
Posts: 10
Joined: Mon Feb 25, 2008 8:22 pm