how to find the square root of a number in java without using the squrt function

- anonymous

how to find the square root of a number in java without using the squrt function

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- jamiebookeater

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- blurbendy

you'd probably have to write your own method to do it

- whpalmer4

The Babylonian method is one you could easily do. https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method

- anonymous

http://dpaste.com/1259775/

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- eSpeX

You could also try the Newtonian method.
https://en.wikipedia.org/wiki/Newton%27s_method

- whpalmer4

The Babylonian method is very simple to implement and converges much faster than the binary search approach referenced by @bwCA.
>>> def babysqrt2(x,tolerance):
... guess=x/2.0
... while True:
... print "guess = ", guess
... if -tolerance <= (guess*guess)-x < tolerance:
... return guess
... guess = (guess + x/guess)/2
...
>>> babysqrt2(1000,0.00001)
guess = 500.0
guess = 251.0
guess = 127.492031873
guess = 67.6678296579
guess = 41.2229503947
guess = 32.7406409949
guess = 31.6418602354
guess = 31.6227823565
guess = 31.6227766017
31.622776601684315
>>> babysqrt2(1000,0.000001)
guess = 500.0
guess = 251.0
guess = 127.492031873
guess = 67.6678296579
guess = 41.2229503947
guess = 32.7406409949
guess = 31.6418602354
guess = 31.6227823565
guess = 31.6227766017
31.622776601684315
>>> babysqrt2(2,0.001)
guess = 1.0
guess = 1.5
guess = 1.41666666667
guess = 1.41421568627
1.4142156862745097
>>> babysqrt2(2,0.00001)
guess = 1.0
guess = 1.5
guess = 1.41666666667
guess = 1.41421568627
1.4142156862745097
Compare with the hi/lo method:
>>> print sqrt(100)
entering iter_sqrt( 100 , 100 , 0 )
entering iter_sqrt( 100 , 50.0 , 0 )
entering iter_sqrt( 100 , 25.0 , 0 )
entering iter_sqrt( 100 , 12.5 , 0 )
entering iter_sqrt( 100 , 12.5 , 6.25 )
entering iter_sqrt( 100 , 12.5 , 9.375 )
entering iter_sqrt( 100 , 10.9375 , 9.375 )
entering iter_sqrt( 100 , 10.15625 , 9.375 )
entering iter_sqrt( 100 , 10.15625 , 9.765625 )
entering iter_sqrt( 100 , 10.15625 , 9.9609375 )
entering iter_sqrt( 100 , 10.05859375 , 9.9609375 )
entering iter_sqrt( 100 , 10.009765625 , 9.9609375 )
entering iter_sqrt( 100 , 10.009765625 , 9.9853515625 )
entering iter_sqrt( 100 , 10.009765625 , 9.99755859375 )
entering iter_sqrt( 100 , 10.0036621094 , 9.99755859375 )
entering iter_sqrt( 100 , 10.0006103516 , 9.99755859375 )
entering iter_sqrt( 100 , 10.0006103516 , 9.99908447266 )
entering iter_sqrt( 100 , 10.0006103516 , 9.99984741211 )
entering iter_sqrt( 100 , 10.0002288818 , 9.99984741211 )
10.000038147
>>> print sqrt(2)
entering iter_sqrt( 2 , 2 , 0 )
entering iter_sqrt( 2 , 2 , 1.0 )
entering iter_sqrt( 2 , 1.5 , 1.0 )
entering iter_sqrt( 2 , 1.5 , 1.25 )
entering iter_sqrt( 2 , 1.5 , 1.375 )
entering iter_sqrt( 2 , 1.4375 , 1.375 )
entering iter_sqrt( 2 , 1.4375 , 1.40625 )
entering iter_sqrt( 2 , 1.421875 , 1.40625 )
1.4140625

- anonymous

Actually, the Babylonian method is equivalent to Newton's method, so you could use either one. Proof:
Newton's method: NewGuess = Guess - (f(Guess) - f(x_final))/f'(Guess) where f(x) is the inverse function of the function you are calculating.
So:
f(x) = x^2
f'(x) = 2x
f(x_final) = Whatever you're trying to find the square root of... Let's call it A, for answer
That gives us...
NewGuess = Guess - (Guess^2 - A)/(2*Guess)
Simplify:
NewGuess = Guess - Guess^2/(2*Guess) - A/(2*Guess)
NewGuess = Guess - 1/2*Guess + 1/2 * A/Guess
NewGuess = (Guess + A/Guess)/2
^ The Babylonian Method

- anonymous

Oh, so if you want it in java (even though the course is in python...) I'd write the method:
public static double sqrt(double x) {
double guess = 0.5 * x;
double oldGuess = 0.0;
while (guess != oldGuess) {
oldGuess = guess;
guess = (guess + x/guess) / 2.0;
}
return guess;
}
That should do it. If you want the method in python:
def sqrt(x):
guess = 0.5 * x
oldGuess = 0.0
while guess != oldGuess:
oldGuess = guess
guess = (guess + x/guess) / 2.0
return guess

- whpalmer4

Numerical code like this:
while guess != oldGuess:
oldGuess = guess
guess = (guess + x/guess) / 2.0
return guess
is not necessarily a good idea. I'm not saying it will happen here, but you can get into states with some computations where the result bounces back and forth, never quite giving you a true equality. Numerical analysis is a decidedly non-trivial area of research. Just because an algorithm looks good on paper doesn't mean that implementing it on a computer will be a happy experience.

- anonymous

....but it's essentially your code with tolerance set at the most precise digit of the float... (or double, in the case of the java code). I'm fairly certain that newton's method almost always reaches equilibrium.

- whpalmer4

Newton's method isn't the issue — it's numerical methods implemented to limited precision. If for some reason you get values that oscillate back and forth in the last digit or two and never give an exact equality, termination tests written like your proposed version don't ever return. I hope you understand that is unexpected and generally unacceptable behavior for a math library routine.

- anonymous

Yes, but my point is that with the algorithm I used, that oscillation shouldn't occur. I get what your saying though for algorithms in general. At the same time, I think your method has the potential to hang if the user of the method puts in a very low tolerance in an attempt to be more precise. If you end up getting a square that's 48.9999998, which we interpret as 49 (granted, I don't know if it would happen for this value, but I think you know about the discrepancy which I'm talking about concerning the conversion between binary and decimal values), but your user-set tolerance is set at 0.000001, your method will become stuck in an infinite loop. Correct me if I'm wrong, but I see slight room for error in both of our approaches.

- anonymous

Also, if all of the actual math library functions were programmed with tolerance values, like your method, wouldn't there be error bounds associated with each function?

- anonymous

@whpalmer4
What do you think about this compromise? I tried to incorporate the ideas of both of our solutions into one:
def sqrt(x,tolerance):
guess = 0.5 * x # Initial guess is 1/2 of x
oldGuess = 0.0 # initializes oldGuess
# While consistant guesses have yet to be reached
# (to prevent against tolerance bounds which are too small)
# AND outside the tolerance bound...
while guess != oldGuess and -tolerance <= guess*guess-x and tolerance > guess*guess-x:
# Iterate based on Newton's/the Babylonian Method:
oldGuess = guess
guess = (guess + x/guess)/2.0
# After it's finished, if within the tolerance bound, but not yet consistant guessing...
iterator = 0
iteratorLimit = 10
# guess 10 more times to attempt to achieve consistant guessing without looping to infinity
# if the most precise guess oscillates
while iterator < iteratorLimit and guess != oldGuess:
oldGuess=guess
guess=(guess+x/guess)/2.0
# Return the most precise guess found
return guess

Looking for something else?

Not the answer you are looking for? Search for more explanations.