## 10023 - Square root

Moderator: Board moderators

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
The input numbers are very large, traditional data types can't handle it.

New poster
Posts: 42
Joined: Sun Jul 31, 2005 2:07 am
Contact:
But my bignum algo is getting TLE

J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Contact:
My Big number function also get TLE...!
Can any body explain an efficient algorithm..?
That help me...very much.

THANKS

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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:
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
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Contact:
Thanks Little joey, I think it will help me...thanks again..[/b]

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
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:
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
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:
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
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 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 ) 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

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
Contact:

### 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!

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

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