10023 - Square root

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Aug 30, 2005 4:50 pm

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

Nazmul Quader Zinnuree
New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Location: SUST. Bangladesh
Contact:

Post by Nazmul Quader Zinnuree » Fri Sep 02, 2005 2:45 pm

But my bignum algo is getting TLE

User avatar
J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Location: Daffodil University,Dhaka,Bangladesh
Contact:

Post by J&Jewel » Sat Sep 10, 2005 2:30 pm

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

THANKS
I hate Wrong Answer!

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Sep 10, 2005 3:03 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sun Sep 11, 2005 4:01 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.

User avatar
J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Location: Daffodil University,Dhaka,Bangladesh
Contact:

Post by J&Jewel » Mon Sep 12, 2005 12:26 pm

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

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Thu Sep 15, 2005 9:18 am

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Sep 16, 2005 9:41 am

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
New poster
Posts: 10
Joined: Mon Oct 18, 2004 3:52 pm

Post by zhenh » Fri Oct 28, 2005 6:00 pm

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?

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

Post by mf » Fri Oct 28, 2005 8:05 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.

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Mon Nov 28, 2005 1:59 pm

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 :o ) 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
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

10023 - Compile error

Post by medv » Mon Jan 30, 2006 12:53 pm

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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Re: 10023 - Compile error

Post by mamun » Mon Jan 30, 2006 1:23 pm

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!

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

10023 - RTE. Why?

Post by medv » Mon Jan 30, 2006 3:16 pm

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
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

10023 TLE

Post by IRA » Mon Jan 30, 2006 7:56 pm

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

Post Reply

Return to “Volume 100 (10000-10099)”