10023 - Square root

[shamim]

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

[Nazmul Quader Zinnuree]

But my bignum algo is getting TLE

[J&Jewel]

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

THANKS

[little joey]

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.

[mf]

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.

[J&Jewel]

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

[A1]

Can you explain your procedure?
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).

[mf]

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 */

[zhenh]

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?

[mf]

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.

[A1]

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)

[medv]

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 = 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 + a.m + carry;
Temp.m = t % 10;
carry = t / 10;
}
if (carry > 0) {Temp.m = 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 = Temp.m + carry;
carry = Temp.m / 10;
Temp.m = Temp.m % 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");
}
}

[mamun]

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).

Can I use classes on UVA?

Definately!

[medv]

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 = 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 + a.m + carry;
Temp.m = t % 10;
carry = t / 10;
}
if (carry > 0) {Temp.m = 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 = Temp.m + carry;
carry = Temp.m / 10;
Temp.m = Temp.m % 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");
}
}

[IRA]

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;
}