[algogeeks] Re: perfect square condition checking....
On Sunday, December 23, 2012 9:07:53 PM UTC+5:30, Anil Sharma wrote: please suggest some efficient solution to check perfect square condition . no matter how much large number is... eg..i/p-8949 o/p-93 there is no specific algorithm for it but yeah you can use binary search for (bisection method )... or use the property that number of divisor of a perfect square is always odd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: perfect square condition checking....
Yea Dave .. I was actually looking for your response.. Coz it generally
have some mathematical background. So, Could U provide us some least
Complexity Algo for this same old general and basic problem.
On Thu, Feb 7, 2013 at 11:08 AM, Dave dave_and_da...@juno.com wrote:
@Gaurav: Does it work for n = 25 or for n = 8? I think you've confused
perfect square with power of two.
Dave
On Wednesday, February 6, 2013 11:32:55 PM UTC-6, Gaurav Rana wrote:
if(n(n-1)==0)
//perfect square
On Thu, Feb 7, 2013 at 3:01 AM, Don dond...@gmail.com wrote:
The following is a bit faster than the Newton's Method solution I
suggest above. It uses a binary square root algorithm as seen here:
http://en.wikipedia.org/wiki/**Methods_of_computing_square_**
roots#Binary_numeral_system_.**28base_2.29http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_.28base_2.29
The value is a perfect square if x ends up being zero.
bool isSqr(unsigned int x)
{
unsigned int res = 0;
unsigned int bit = 1 30;
while(bit x) bit = 2;
while(bit)
{
if (x = res + bit)
{
x -= res + bit;
res = (res 1) + bit;
}
else
{
res = 1;
}
bit = 2;
}
return (x == 0);
}
On Dec 23 2012, 10:37 am, Anil Sharma anilsharmau...@gmail.com
wrote:
please suggest some efficient solution to check perfect square
condition .
no matter how much large number is... eg..i/p-8949 o/p-93
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+...@**googlegroups.com.
For more options, visit
https://groups.google.com/**groups/opt_outhttps://groups.google.com/groups/opt_out
.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: perfect square condition checking....
The following is a bit faster than the Newton's Method solution I
suggest above. It uses a binary square root algorithm as seen here:
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_.28base_2.29
The value is a perfect square if x ends up being zero.
bool isSqr(unsigned int x)
{
unsigned int res = 0;
unsigned int bit = 1 30;
while(bit x) bit = 2;
while(bit)
{
if (x = res + bit)
{
x -= res + bit;
res = (res 1) + bit;
}
else
{
res = 1;
}
bit = 2;
}
return (x == 0);
}
On Dec 23 2012, 10:37 am, Anil Sharma anilsharmau...@gmail.com
wrote:
please suggest some efficient solution to check perfect square condition .
no matter how much large number is... eg..i/p-8949 o/p-93
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: perfect square condition checking....
@Gaurav: Does it work for n = 25 or for n = 8? I think you've confused
perfect square with power of two.
Dave
On Wednesday, February 6, 2013 11:32:55 PM UTC-6, Gaurav Rana wrote:
if(n(n-1)==0)
//perfect square
On Thu, Feb 7, 2013 at 3:01 AM, Don dond...@gmail.com javascript:wrote:
The following is a bit faster than the Newton's Method solution I
suggest above. It uses a binary square root algorithm as seen here:
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_.28base_2.29
The value is a perfect square if x ends up being zero.
bool isSqr(unsigned int x)
{
unsigned int res = 0;
unsigned int bit = 1 30;
while(bit x) bit = 2;
while(bit)
{
if (x = res + bit)
{
x -= res + bit;
res = (res 1) + bit;
}
else
{
res = 1;
}
bit = 2;
}
return (x == 0);
}
On Dec 23 2012, 10:37 am, Anil Sharma anilsharmau...@gmail.com
wrote:
please suggest some efficient solution to check perfect square
condition .
no matter how much large number is... eg..i/p-8949 o/p-93
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+...@googlegroups.com javascript:.
For more options, visit https://groups.google.com/groups/opt_out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: perfect square condition checking....
@Don : But, newton's formulae doesn't always converge.. if our guess is bad enough, it may diverge also. On Tue, Jan 8, 2013 at 8:30 PM, Don dondod...@gmail.com wrote: Sure, Let's try two examples: x=1,038,381,081 The last digit is 1, so continue Now start with y=10,000 because that is half as many digits as x. y0 = 10,000 y1 = 56919 y2 = 37581 y3 = 32605 y4 = 32226 y5 = 32226 y6 = 32223 y7 = 32223 Y6=Y7 so you are done. Now square y7 giving 1,038,321,729. That is not equal to x, so x is not a perfect square. Second case x=1,038,579,529 Last digit is 9, so continue. y1 = 1 y2 = 56928 y3 = 37585 y4 = 32608 y5 = 32229 y6 = 32227 y7 = 32227 32227^2 = x, so x is a perfect square. Don On Jan 5, 8:08 am, bala bharath bagop...@gmail.com wrote: @Don, Can u explain with an Example...? With regards, Balasubramanian Naagarajan, Chettinad College of Engg Tech. On Sat, Jan 5, 2013 at 1:48 PM, Malathi malu@gmail.com wrote: Check this. It might help. http://www.johndcook.com/blog/2008/11/17/fast-way-to-test-whether-a-n. .. On Sat, Jan 5, 2013 at 1:47 AM, Don dondod...@gmail.com wrote: start with a guess y. If you can arrange for y to be about half the -- With Regards, Malathi -- -- --
[algogeeks] Re: perfect square condition checking....
Can you show me a case where it diverges if the initial guess is half the digits of X? Don On Jan 14, 3:09 am, bharat b bagana.bharatku...@gmail.com wrote: @Don : But, newton's formulae doesn't always converge.. if our guess is bad enough, it may diverge also. On Tue, Jan 8, 2013 at 8:30 PM, Don dondod...@gmail.com wrote: Sure, Let's try two examples: x=1,038,381,081 The last digit is 1, so continue Now start with y=10,000 because that is half as many digits as x. y0 = 10,000 y1 = 56919 y2 = 37581 y3 = 32605 y4 = 32226 y5 = 32226 y6 = 32223 y7 = 32223 Y6=Y7 so you are done. Now square y7 giving 1,038,321,729. That is not equal to x, so x is not a perfect square. Second case x=1,038,579,529 Last digit is 9, so continue. y1 = 1 y2 = 56928 y3 = 37585 y4 = 32608 y5 = 32229 y6 = 32227 y7 = 32227 32227^2 = x, so x is a perfect square. Don On Jan 5, 8:08 am, bala bharath bagop...@gmail.com wrote: @Don, Can u explain with an Example...? With regards, Balasubramanian Naagarajan, Chettinad College of Engg Tech. On Sat, Jan 5, 2013 at 1:48 PM, Malathi malu@gmail.com wrote: Check this. It might help. http://www.johndcook.com/blog/2008/11/17/fast-way-to-test-whether-a-n. .. On Sat, Jan 5, 2013 at 1:47 AM, Don dondod...@gmail.com wrote: start with a guess y. If you can arrange for y to be about half the -- With Regards, Malathi -- -- --
Re: [algogeeks] Re: perfect square condition checking....
@Bharat: It can be proven that Newton's method for square root, x(n+1) = (x(n) + a / x(n))/2, always converges to sqrt(a) if a 0 and x(0) 0. It is not difficult, so let e(n) = x(n) - sqrt(a), the error in the n-th iteration, and find the recurrence for e(n+1) in terms of e(n) and a. You should get e(n+1) = e(n)^2 / (2*(e(n) + sqrt(a))). You can then observe that if x(0) 0, then e(1) = 0, and if e(n) 0 then 0 e(n+1) e(n) / 2, proving convergence. You can further observe that if e(n) is small, then convergence is quadratic: e(n+1) = O(e(n)^2). Dave On Monday, January 14, 2013 2:09:22 AM UTC-6, bharat wrote: @Don : But, newton's formulae doesn't always converge.. if our guess is bad enough, it may diverge also. On Tue, Jan 8, 2013 at 8:30 PM, Don dond...@gmail.com javascript:wrote: Sure, Let's try two examples: x=1,038,381,081 The last digit is 1, so continue Now start with y=10,000 because that is half as many digits as x. y0 = 10,000 y1 = 56919 y2 = 37581 y3 = 32605 y4 = 32226 y5 = 32226 y6 = 32223 y7 = 32223 Y6=Y7 so you are done. Now square y7 giving 1,038,321,729. That is not equal to x, so x is not a perfect square. Second case x=1,038,579,529 Last digit is 9, so continue. y1 = 1 y2 = 56928 y3 = 37585 y4 = 32608 y5 = 32229 y6 = 32227 y7 = 32227 32227^2 = x, so x is a perfect square. Don On Jan 5, 8:08 am, bala bharath bagop...@gmail.com wrote: @Don, Can u explain with an Example...? With regards, Balasubramanian Naagarajan, Chettinad College of Engg Tech. On Sat, Jan 5, 2013 at 1:48 PM, Malathi malu@gmail.com wrote: Check this. It might help. http://www.johndcook.com/blog/2008/11/17/fast-way-to-test-whether-a-n. .. On Sat, Jan 5, 2013 at 1:47 AM, Don dondod...@gmail.com wrote: start with a guess y. If you can arrange for y to be about half the -- With Regards, Malathi -- -- --
[algogeeks] Re: perfect square condition checking....
Sure, Let's try two examples: x=1,038,381,081 The last digit is 1, so continue Now start with y=10,000 because that is half as many digits as x. y0 = 10,000 y1 = 56919 y2 = 37581 y3 = 32605 y4 = 32226 y5 = 32226 y6 = 32223 y7 = 32223 Y6=Y7 so you are done. Now square y7 giving 1,038,321,729. That is not equal to x, so x is not a perfect square. Second case x=1,038,579,529 Last digit is 9, so continue. y1 = 1 y2 = 56928 y3 = 37585 y4 = 32608 y5 = 32229 y6 = 32227 y7 = 32227 32227^2 = x, so x is a perfect square. Don On Jan 5, 8:08 am, bala bharath bagop...@gmail.com wrote: @Don, Can u explain with an Example...? With regards, Balasubramanian Naagarajan, Chettinad College of Engg Tech. On Sat, Jan 5, 2013 at 1:48 PM, Malathi malu@gmail.com wrote: Check this. It might help. http://www.johndcook.com/blog/2008/11/17/fast-way-to-test-whether-a-n... On Sat, Jan 5, 2013 at 1:47 AM, Don dondod...@gmail.com wrote: start with a guess y. If you can arrange for y to be about half the -- With Regards, Malathi -- --
Re: [algogeeks] Re: perfect square condition checking....
@Don, Can u explain with an Example...? With regards, Balasubramanian Naagarajan, Chettinad College of Engg Tech. On Sat, Jan 5, 2013 at 1:48 PM, Malathi malu@gmail.com wrote: Check this. It might help. http://www.johndcook.com/blog/2008/11/17/fast-way-to-test-whether-a-number-is-a-square/ On Sat, Jan 5, 2013 at 1:47 AM, Don dondod...@gmail.com wrote: start with a guess y. If you can arrange for y to be about half the -- With Regards, Malathi -- --
Re: [algogeeks] Re: perfect square condition checking....
Check this. It might help. http://www.johndcook.com/blog/2008/11/17/fast-way-to-test-whether-a-number-is-a-square/ On Sat, Jan 5, 2013 at 1:47 AM, Don dondod...@gmail.com wrote: start with a guess y. If you can arrange for y to be about half the -- With Regards, Malathi --
[algogeeks] Re: perfect square condition checking....
First look at the last digit. If it is 2,3,7, or 8 the number is not a perfect square. Then use an integer formulation of Newton's method. For input value x, start with a guess y. If you can arrange for y to be about half the number of digits in x, that is good. Then repeatedly set y=(y*y+x)/(2*y) When y converges, if y*y=x, x is a perfect square. Don On Dec 23 2012, 10:37 am, Anil Sharma anilsharmau...@gmail.com wrote: please suggest some efficient solution to check perfect square condition . no matter how much large number is... eg..i/p-8949 o/p-93 --
