## dhemmy 2 years ago how to find the square root of a number in java without using the squrt function

1. blurbendy

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

2. whpalmer4

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

3. bwCA
4. eSpeX

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

5. 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

6. kkleidal

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

7. kkleidal

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

8. 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.

9. kkleidal

....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.

10. 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.

11. kkleidal

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.

12. kkleidal

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?

13. kkleidal

@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