Got Homework?
Connect with other students for help. It's a free community.
Here's the question you clicked on:
 0 viewing
dhemmy
Group Title
how to find the square root of a number in java without using the squrt function
 one year ago
 one year ago
dhemmy Group Title
how to find the square root of a number in java without using the squrt function
 one year ago
 one year ago

This Question is Closed

blurbendy Group TitleBest ResponseYou've already chosen the best response.0
you'd probably have to write your own method to do it
 one year ago

whpalmer4 Group TitleBest ResponseYou've already chosen the best response.1
The Babylonian method is one you could easily do. https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method
 one year ago

eSpeX Group TitleBest ResponseYou've already chosen the best response.0
You could also try the Newtonian method. https://en.wikipedia.org/wiki/Newton%27s_method
 one year ago

whpalmer4 Group TitleBest ResponseYou've already chosen the best response.1
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
 one year ago

kkleidal Group TitleBest ResponseYou've already chosen the best response.0
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
 one year ago

kkleidal Group TitleBest ResponseYou've already chosen the best response.0
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
 one year ago

whpalmer4 Group TitleBest ResponseYou've already chosen the best response.1
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 nontrivial 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.
 one year ago

kkleidal Group TitleBest ResponseYou've already chosen the best response.0
....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.
 one year ago

whpalmer4 Group TitleBest ResponseYou've already chosen the best response.1
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.
 one year ago

kkleidal Group TitleBest ResponseYou've already chosen the best response.0
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 userset 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.
 one year ago

kkleidal Group TitleBest ResponseYou've already chosen the best response.0
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?
 one year ago

kkleidal Group TitleBest ResponseYou've already chosen the best response.0
@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*guessx and tolerance > guess*guessx: # 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
 one year ago
See more questions >>>
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.