OJ Board

The Online Judge board
https://onlinejudge.org/board/

10023 - Square root

https://onlinejudge.org/board/viewtopic.php?t=11096

Page 4 of 9

Posted: Tue Aug 30, 2005 4:50 pm
by shamim
The input numbers are very large, traditional data types can't handle it.

Posted: Fri Sep 02, 2005 2:45 pm
by Nazmul Quader Zinnuree
But my bignum algo is getting TLE

Posted: Sat Sep 10, 2005 2:30 pm
by J&Jewel
My Big number function also get TLE...!
Can any body explain an efficient algorithm..?
That help me...very much.

THANKS

Posted: Sat Sep 10, 2005 3:03 pm
by 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.

Posted: Sun Sep 11, 2005 4:01 pm
by 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.

Posted: Mon Sep 12, 2005 12:26 pm
by J&Jewel
Thanks Little joey, I think it will help me...thanks again..[/b]

Posted: Thu Sep 15, 2005 9:18 am
by 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).

Posted: Fri Sep 16, 2005 9:41 am
by 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 */

Posted: Fri Oct 28, 2005 6:00 pm
by zhenh
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?

Posted: Fri Oct 28, 2005 8:05 pm
by 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.

Posted: Mon Nov 28, 2005 1:59 pm
by A1
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)

10023 - Compile error

Posted: Mon Jan 30, 2006 12:53 pm
by 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");
}
}

Re: 10023 - Compile error

Posted: Mon Jan 30, 2006 1:23 pm
by mamun
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!

10023 - RTE. Why?

Posted: Mon Jan 30, 2006 3:16 pm
by 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");
}
}

10023 TLE

Posted: Mon Jan 30, 2006 7:56 pm
by 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;
}
All times are UTC+02:00
Page 4 of 9

Powered by phpBB® Forum Software © phpBB Limited