10023 - Square Root

Moderator: Board moderators

The input numbers are very large, traditional data types can't handle it.

shamim
A great helper

Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Dhaka

But my bignum algo is getting TLE
New poster

Posts: 42
Joined: Sun Jul 31, 2005 2:07 am

My Big number function also get TLE...!
Can any body explain an efficient algorithm..?
That help me...very much.

THANKS

J&Jewel
New poster

Posts: 50
Joined: Thu Jul 31, 2003 10:43 am

Take a look at http://en.wikipedia.org/wiki/Square_root; there's plenty of information.
I used Pell's equation for this problem for a reasonable time.

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

I want to request the judge to reduce it's input so that more people can solve it in different method, (not only in the way that the problem setter have

There's more than one way to do it,
I, for one, just got accepted with binary search + newton's, and with a pretty good time.
mf
Guru

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

Thanks Little joey, I think it will help me...thanks again..[/b]

J&Jewel
New poster

Posts: 50
Joined: Thu Jul 31, 2003 10:43 am

I think for binary search and newton's method it need big integer division, which is very slow(i try to solve it by another method).

A1
Experienced poster

Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm

First, I use binary search to get a good approximation of the root (within a factor of 2 of its real value.)
And then just Newton's method. Of course, it needs long division, but the good thing is that starting with a good approximation you'll need quite a few of them, for example, to compute sqrt(123^450) my program needs only 8 divisions.
Binary search needs just addition and shifts.

Here's how my algorithm looks:
Code: Select all
`/* a = input number */for (l = 0, u = a; l < u;) {        x = (l + u) >> 1;        /* break, if the following check can't be done in O(1) */        if (x * x > a) u = x; else l = x;}for (x = u;; x = y)        if ((y = (x + a / x) >> 1) >= x) break;/* now x = root */`
mf
Guru

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

mf wrote:Here's how my algorithm looks:
Code: Select all
`/* a = input number */for (l = 0, u = a; l < u;) {        x = (l + u) >> 1;        /* break, if the following check can't be done in O(1) */        if (x * x > a) u = x; else l = x;}for (x = u;; x = y)        if ((y = (x + a / x) >> 1) >= x) break;/* now x = root */`

Excuse me, but how on earth that the check be done in O(1) is possible?
x*x requires O(n^2) operations.
x > a, u = x, l = x all require O(n) operations.

And by the way, you can't just shift the bits, it's BIG numbers...
right shift is not O(1), but O(n)...

Or did I get something wrong?
zhenh
New poster

Posts: 10
Joined: Mon Oct 18, 2004 3:52 pm

Excuse me, but how on earth that the check be done in O(1) is possible?

Of course, it can't always be done in O(1), but there are a few cases, when you can immediately determine, if x^2 > a.
For example, if d(n) denotes the number of digits (in some base) of n, and 2*d(x)-1 > d(a), then x^2 > a.
In some cases, the first significant digits of x and a also can tell, if x^2 > a.

The point of my algorithm was to use binary search just to get a (quick and cheap) approximation of the answer. When my program starts needing O(n^2) time to check if x^2 > a, I switch to Newton's method.
mf
Guru

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

mf wrote:First, I use binary search to get a good approximation of the root (within a factor of 2 of its real value.)
And then just Newton's method. Of course, it needs long division, but the good thing is that starting with a good approximation you'll need quite a few of them, for example, to compute sqrt(123^450) my program needs only 8 divisions.
Binary search needs just addition and shifts.

Here's how my algorithm looks:
Code: Select all
`/* a = input number */for (l = 0, u = a; l < u;) {        x = (l + u) >> 1;        /* break, if the following check can't be done in O(1) */        if (x * x > a) u = x; else l = x;}for (x = u;; x = y)        if ((y = (x + a / x) >> 1) >= x) break;/* now x = root */`

yesterday I again sat for this ( Bad for me ) square root problem and tried to implement your method by little simplifying and the code looks like:
Code: Select all
`for (l = 0, u = a; ;) {        x = (l + u) /2;        /* break, if the following check can't be done in O(1) */        if (x.length/2 > a.length) u = x;         else break;}for (x = u;; x = y)        if ((y = (x + a / x)/2) >= x) break;return x;`

I found that you are right as it needs few big division after a good assumption, but the problem is my BigDivision is so slow that i runs around 100 times slower then my old method (http://home.earthlink.net/~usondermann/square.html)

A1
Experienced poster

Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm

10023 - Compile error

Why Complie Error? Can I use classes on UVA?

#include <cstdio>
#include <string>
#include <memory>
#define MAXLENGTH 1001
using namespace std;

class BigInteger{
private:
int m[MAXLENGTH];
int len;

int max(int i, int j)
{
return (i > j) ? i : j;
}

public:
BigInteger(int n=0)
{
memset(m,0,sizeof(m));
len=0;
if (n == 0) len++;
while (n > 0)
{
m[len++] = n % 10;
n = n / 10;
}
}

BigInteger(string s)
{
len = s.length();
memset(m,0,sizeof(m));
for(int i=0;i<len;i++)
m[i] = s[len-i-1]-'0';
}

void print(void)
{
int temp = len-1;
while(temp>=0) printf("%d",m[temp--]);
}

BigInteger operator+ (const BigInteger &a)
{
BigInteger Temp(0);
int t,carry = 0;
Temp.len = max(len,a.len);
for(int i=0;i<Temp.len;i++)
{
t = m[i] + a.m[i] + carry;
Temp.m[i] = t % 10;
carry = t / 10;
}
if (carry > 0) {Temp.m[i] = carry; Temp.len++;}
return Temp;
}

BigInteger operator+ (int a)
{
BigInteger Temp(*this);
int carry = a;
for(int i=0;i<Temp.len;i++)
{
Temp.m[i] = Temp.m[i] + carry;
carry = Temp.m[i] / 10;
Temp.m[i] = Temp.m[i] % 10;
}
while (carry > 0)
{
Temp.m[i++] = carry % 10;
carry /= 10;
Temp.len++;
}
return Temp;
}

BigInteger operator* (const BigInteger &a)
{
BigInteger Temp(0);
int t,carry;
for(int i=0;i<len;i++)
{
carry = 0;
for(int j=0;j<a.len;j++)
{
t = Temp.m[i+j] + m[i] * a.m[j] + carry;
Temp.m[i+j] = t % 10;
carry = t / 10;
}
Temp.m[i+a.len] = carry;
}
Temp.len = len + a.len;
if (Temp.m[Temp.len-1] == 0) Temp.len--;
return Temp;
}

BigInteger operator/ (int a)
{
BigInteger Temp(0);
int ost = 0;
for(int i=len-1;i>=0;i--)
{
ost = ost*10+m[i];
Temp.m[i] = ost/a;
ost = ost % a;
}
Temp.len = len;
while(Temp.m[Temp.len-1] == 0) Temp.len--;
return Temp;
}

int operator== (const BigInteger &a)
{
if (len != a.len) return 0;
for(int i = len-1;i>=0;i--)
if (m[i] != a.m[i]) return 0;
return 1;
}

int operator< (const BigInteger &a)
{
if (len < a.len) return 1;
if (len > a.len) return 0;
for(int i =len-1;(m[i] == a.m[i]) && (i>=0);i--);
if (m[i] < a.m[i]) return 1;
return 0;
}

BigInteger Sqrt()
{
BigInteger a(0),b(*this),t;
while (a < b)
{
t = (a + b) / 2;
if (t == a) break;
if (*this < t*t) b = t; else a = t;
}
return a;
}

};

void main(void)
{
int i,n;
char num[MAXLENGTH];
BigInteger a;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s",num);
a = BigInteger(num);
a.Sqrt().print();printf("\n");
if (i < n-1) printf("\n");
}
}
medv
Learning poster

Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

Re: 10023 - Compile error

medv wrote:Why Complie Error?

In several places you're using variable like i whose scope is actually in previous for loop only (according to your coding).

medv wrote:Can I use classes on UVA?

Definately!
mamun
A great helper

Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm

10023 - RTE. Why?

Thank you. But now I have Run Time Error.
I don't know why.
I corrected my sqrt function - previous program didn't count sqrt(1)
Now I have tested a lot - and all seems fine.

What about dimention of array? The problem statement says 1000 is enough. Is it so? I tried to put MAXLENGTH = 10001 and get TLE.
Can smbody help me? To give some input? SQRT is written using binary search - if somebody accepted - did you solve it using some other algorithm? I tried to avoid long division. If smb have long division program - give it to me, please.

Thanks.

#include <cstdio>
#include <string>
#include <memory>
#define MAXLENGTH 1001
using namespace std;

class BigInteger{
private:
int m[MAXLENGTH];
int len;

int max(int i, int j)
{
return (i > j) ? i : j;
}

public:
BigInteger(int n=0)
{
memset(m,0,sizeof(m));
len=0;
if (n == 0) len++;
while (n > 0)
{
m[len++] = n % 10;
n = n / 10;
}
}

BigInteger(string s)
{
int i;
len = s.length();
memset(m,0,sizeof(m));
for(i=0;i<len;i++)
m[i] = s[len-i-1]-'0';
}

void print(void)
{
int temp = len-1;
while(temp>=0) printf("%d",m[temp--]);
}

BigInteger operator+ (const BigInteger &a)
{
BigInteger Temp(0);
int i,t,carry = 0;
Temp.len = max(len,a.len);
for(i=0;i<Temp.len;i++)
{
t = m[i] + a.m[i] + carry;
Temp.m[i] = t % 10;
carry = t / 10;
}
if (carry > 0) {Temp.m[i] = carry; Temp.len++;}
return Temp;
}

BigInteger operator+ (int a)
{
BigInteger Temp(*this);
int i,carry = a;
for(i=0;i<Temp.len;i++)
{
Temp.m[i] = Temp.m[i] + carry;
carry = Temp.m[i] / 10;
Temp.m[i] = Temp.m[i] % 10;
}
while (carry > 0)
{
Temp.m[i++] = carry % 10;
carry /= 10;
Temp.len++;
}
return Temp;
}

BigInteger operator* (const BigInteger &a)
{
BigInteger Temp(0);
int i,j,t,carry;
for(i=0;i<len;i++)
{
carry = 0;
for(j=0;j<a.len;j++)
{
t = Temp.m[i+j] + m[i] * a.m[j] + carry;
Temp.m[i+j] = t % 10;
carry = t / 10;
}
Temp.m[i+a.len] = carry;
}
Temp.len = len + a.len;
if (Temp.m[Temp.len-1] == 0) Temp.len--;
return Temp;
}

BigInteger operator/ (int a)
{
BigInteger Temp(0);
int i,ost = 0;
for(i=len-1;i>=0;i--)
{
ost = ost*10+m[i];
Temp.m[i] = ost/a;
ost = ost % a;
}
Temp.len = len;
while(Temp.m[Temp.len-1] == 0) Temp.len--;
return Temp;
}

int operator== (const BigInteger &a)
{
int i;
if (len != a.len) return 0;
for(i = len-1;i>=0;i--)
if (m[i] != a.m[i]) return 0;
return 1;
}

int operator< (const BigInteger &a)
{
int i;
if (len < a.len) return 1;
if (len > a.len) return 0;
for(i =len-1;(m[i] == a.m[i]) && (i>=0);i--);
if (m[i] < a.m[i]) return 1;
return 0;
}

BigInteger Sqrt()
{
BigInteger a(0),b(*this),t;
if ((len == 1) && (m[0] == 1)) return BigInteger(1);
while (a < b)
{
t = (a + b) / 2;
if (t == a) break;
if (*this < t*t) b = t; else a = t;
}
return a;
}

};

void main(void)
{
int i,n;
char num[MAXLENGTH];
BigInteger a;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%s",num);
a = BigInteger(num);
a.Sqrt().print();printf("\n");
if (i < n-1) printf("\n");
}
}
medv
Learning poster

Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

10023 TLE

I use binary search to get a approximation of the root,but TLE.
Who can give me a hint to speed up the program.
==========================================
Code: Select all
`#include <cstdio>#include <vector>#include <list>using namespace std;vector <char>v;vector <char>s;vector <char>result;int BigInterger_Large(vector <char> & v1,vector <char> & v2){   int len,i;   if(v1.size()>v2.size())      return 1;   if(v2.size()>v1.size())      return 0;   len=v1.size();   for(i=len-1;i>=0;i--)      if(v1[i]<v2[i])         return 0;      else if(v1[i]==v2[i])         ;      else         return 1;   return 2;}int BigInterger_DIV(vector <char> & v1,int mod,vector <char> & v2){   int len,i,flag;   int sum;   list <char>hold;   hold.clear();   v2.clear();   len=v1.size();   flag=sum=0;   for(i=len-1;i>=0;i--)   {      sum+=v1[i];      if(sum<mod)      {         if(flag)            hold.push_back(0);      }      else      {         flag=1;         hold.push_back(sum/mod);         sum=sum%mod;         }      if(i>0)      sum=sum*10;   }   if(hold.size()==0)      v2.push_back(0);      while(hold.size())   {      v2.push_back(hold.back());      hold.pop_back();   }   return sum;}void BigInterger_MUL(vector <char> & v1,vector <char> & v2,vector <char> & v3){   int len,i,a,b,j,s;   int carry=0;   v3.clear();   len=v1.size()-1+v2.size()-1;   if(v1.size()==1&&v1[0]==0)      v3.push_back(0);   else if(v2.size()==1&&v2[0]==0)      v3.push_back(0);   else   for(i=0;i<=len;i++)   {      for(j=0;j<=i;j++)      {         s=i-j;         (v1.size()<=j)?a=0:a=v1[j];         (v2.size()<=s)?b=0:b=v2[s];         carry+=(a*b);      }      if(carry>=10)      {         v3.push_back(carry%10);         carry=carry/10;      }else{         v3.push_back(carry);         carry=0;      }   }      if(carry)      v3.push_back(carry);}void BigInterger_ADD(vector <char> & v1,vector <char> & v2,vector <char> & v3){   int len,i,a,b;   int carry=0;   v3.clear();   (v1.size()>=v2.size())?len=v1.size():len=v2.size();   for(i=0;i<len;i++)   {      (v1.size()<=i)?a=0:a=v1[i];      (v2.size()<=i)?b=0:b=v2[i];      if(a+b+carry>=10)      {         v3.push_back( (a+b+carry)%10 );         carry=(a+b+carry)/10;      }else{         v3.push_back(a+b+carry);         carry=(a+b+carry)/10;      }   }   if(carry)      v3.push_back(carry);}//OK!...int input(vector <char> & v1){   int i=0,len;   int dis;   char sen[100000];   v1.clear();   dis=scanf("%s",sen);   if(dis==-1)      return 0;   len=strlen(sen);   for(i=len-1;i>=0;i--)      v1.push_back(sen[i]-'0');   return 1;}void print(vector <char> & v1){   int i=0;   for(i=v1.size()-1;i>=0;i--)      printf("%d",v1[i]);   printf("\n");}void copyVector(vector <char> & v1,vector <char> & v2){   int i;   v2.clear();   for(i=0;i<v1.size();i++)      v2.push_back(v1[i]);}void BigInterger_SQRT(vector <char> & b,vector <char> & c){   vector <char> a;   vector <char> t;   vector <char> r1;   vector <char> r2;   c.clear();   copyVector(b,r2);   a.push_back(0);   while( BigInterger_Large(r2,a) )  //r2>a   {      BigInterger_ADD(a,r2,r1); //(r1=a+b);      BigInterger_DIV(r1,2,t); //t=(a+b)/2;      BigInterger_MUL(t,t,r1); //r1=t*t;      if( BigInterger_Large(a,t)==2)         break;      if( BigInterger_Large(r1,b) )         copyVector(t,r2);      else         copyVector(t,a);            //print(r2);   //   print(a);   }   copyVector(r2,c);}int main(){   int num,i;      scanf("%d",&num);   for(i=0;i<num;i++)   {      input(s);      BigInterger_SQRT(s,result);      print(result);      printf("\n");   }   return 0;}`
IRA
Learning poster

Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

PreviousNext