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
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
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
@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
@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
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
@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
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.
@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.
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
--
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)
11 matches
Mail list logo